Data structure 09. Hash table -- simplified version of HashMap

Zhao senqing 2021-05-04 18:58:00
data structure hash table simplified


Hash table is an advanced data structure ,java In the standard library HashMap The underlying implementation of hash table is hash table , Specifically, array combines linked list and red black tree ; The hash table implemented in this paper is a simplified version HashMap, Through array and red black tree , But the basic idea is the same ;

Because the underlying implementation of hash table array plus linked list and red black tree is too complex , The implementation of hash table in this article is a simplified version of the underlying implementation , But the underlying idea of hash table is basically the same ;

The hash table in this paper is based on java In the standard library TreeMap Realized , because TreeMap The underlying implementation is the red black tree , This article uses TreeMap[] Array , So it can be considered that the underlying implementation of this paper is array plus red black tree ;

Hash conflict refers to the same array index values calculated by different elements , In this case, you need to store multiple values on an array index , The solution is to make every position of the array a linked list or a binary tree , This solution is also called chain address method ; In this paper, the way to deal with hash conflict is chain address method ;

When calculating the index of an array, a prime number similar to the size of the data , Why is it that a prime number similar to the size of the data is modulo when seeking an array index , This is because mathematical studies have found that the probability of hash collision is less , These underlying implementations will be explained later ;

1、 Basic properties and methods of hash table

int Type capacity An array is a set of prime numbers , As the size of hash table data increases , We just need to take capacity The prime number corresponding to the scale in ;

upperTol and lowerTol Is the coefficient used for expansion and reduction , We'll talk about it later when we expand and shrink ;

capacityIndex yes capacity Index of array , As the size of hash table data increases , We just need to increase the index value , Then use this index value to capacity Array ;

hashtable yes TreeMap An array of types , For storing data ;

size Represents the number of data in the hash table ;

M Express hashtable Size of array ;

Pass... In the constructor capacity Array and capacityIndex Index to M assignment , initialization hashtable Array ;

hash A function is to find the index of an element in an array , Through the first hashcode Find the hash value , And then the mold M, here M Is the prime number corresponding to the data size of the hash table ;

getSize Returns the number of data in the hash table ;

public class HashTable<K extends Comparable<K>, V> {
private final int[] capacity
= {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
private static final int upperTol = 10;
private static final int lowerTol = 2;
private int capacityIndex = 0;
private TreeMap<K, V>[] hashtable;
private int size;
private int M;
public HashTable(){
this.M = capacity[capacityIndex];
size = 0;
hashtable = new TreeMap[M];
for(int i = 0 ; i < M ; i ++)
hashtable[i] = new TreeMap<>();
}
private int hash(K key){
return (key.hashCode() & 0x7fffffff) % M;
}
public int getSize(){
return size;
}
、、、
}
 Copy code 

2、 Add elements to the hash table

adopt hash Function to calculate the array index of an element , Through this index in hashtable Find... In the array TreeMap, If so key Already exists map in , So direct coverage , If it doesn't exist , Add directly to map in ; And this map The underlying implementation is the red black tree , So the underlying implementation of our hash table can be regarded as the implementation of array plus red black tree ;

After adding elements, check whether expansion is needed , The idea of capacity expansion is self increasing capacityIndex Indexes , Then go to capacity Find the corresponding prime number in the array , This ensures that the capacity after each expansion is a prime number corresponding to the hash table data size ;

resize The function is also very simple , Create a new one TreeMap Array , The original map All values in the array are copied to the new array , There are several points to pay attention to in the process of copying , First save the size of the original array , then M Assign to the size of the new array , Why do you need to do this ? Because the first floor for What the loop needs to traverse is the size of the original array , And the second layer foreach Loop to find the element in the new array hash You need to use the size of the new array ; The final will be hashtable The reference points to the new array ;

public void add(K key, V value){
TreeMap<K, V> map = hashtable[hash(key)];
if(map.containsKey(key))
map.put(key, value);
else{
map.put(key, value);
size ++;
if(size >= upperTol * M && capacityIndex + 1 < capacity.length){
capacityIndex ++;
resize(capacity[capacityIndex]);
}
}
}
private void resize(int newM){
TreeMap<K, V>[] newHashTable = new TreeMap[newM];
for(int i = 0 ; i < newM ; i ++)
newHashTable[i] = new TreeMap<>();
int oldM = M;
this.M = newM;
for(int i = 0 ; i < oldM ; i ++){
TreeMap<K, V> map = hashtable[i];
for(K key: map.keySet())
newHashTable[hash(key)].put(key, map.get(key));
}
this.hashtable = newHashTable;
}
 Copy code 

3、 Remove element from hash table

First, through hash Function to calculate the index of an element in an array , Then go through this index to hashtable Find the corresponding in the array map, If map Contains this element , Directly from map You can just delete the elements in the ; Finally, check if you need to reduce the volume , The principle is exactly the same as expansion ;

public V remove(K key){
V ret = null;
TreeMap<K, V> map = hashtable[hash(key)];
if(map.containsKey(key)){
ret = map.remove(key);
size --;
if(size < lowerTol * M && capacityIndex - 1 >= 0){
capacityIndex --;
resize(capacity[capacityIndex]);
}
}
return ret;
}
 Copy code 

4、 Find and modify elements from the hash table

The logic of finding and modifying is basically the same , First, through hash Function to calculate the index of an element in an array , Then go through this index to hashtable Find the corresponding in the array map, Finally through map Of put Function to modify elements ; adopt map Of containsKey perhaps get Function to find elements ;

public void set(K key, V value){
TreeMap<K, V> map = hashtable[hash(key)];
if(!map.containsKey(key))
throw new IllegalArgumentException(key + " doesn't exist!");
map.put(key, value);
}
public boolean contains(K key){
return hashtable[hash(key)].containsKey(key);
}
public V get(K key){
return hashtable[hash(key)].get(key);
}
 Copy code 

5、 Hash table complete code

import java.util.TreeMap;
public class HashTable<K extends Comparable<K>, V> {
private final int[] capacity
= {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
private static final int upperTol = 10;
private static final int lowerTol = 2;
private int capacityIndex = 0;
private TreeMap<K, V>[] hashtable;
private int size;
private int M;
public HashTable(){
this.M = capacity[capacityIndex];
size = 0;
hashtable = new TreeMap[M];
for(int i = 0 ; i < M ; i ++)
hashtable[i] = new TreeMap<>();
}
private int hash(K key){
return (key.hashCode() & 0x7fffffff) % M;
}
public int getSize(){
return size;
}
public void add(K key, V value){
TreeMap<K, V> map = hashtable[hash(key)];
if(map.containsKey(key))
map.put(key, value);
else{
map.put(key, value);
size ++;
if(size >= upperTol * M && capacityIndex + 1 < capacity.length){
capacityIndex ++;
resize(capacity[capacityIndex]);
}
}
}
public V remove(K key){
V ret = null;
TreeMap<K, V> map = hashtable[hash(key)];
if(map.containsKey(key)){
ret = map.remove(key);
size --;
if(size < lowerTol * M && capacityIndex - 1 >= 0){
capacityIndex --;
resize(capacity[capacityIndex]);
}
}
return ret;
}
public void set(K key, V value){
TreeMap<K, V> map = hashtable[hash(key)];
if(!map.containsKey(key))
throw new IllegalArgumentException(key + " doesn't exist!");
map.put(key, value);
}
public boolean contains(K key){
return hashtable[hash(key)].containsKey(key);
}
public V get(K key){
return hashtable[hash(key)].get(key);
}
private void resize(int newM){
TreeMap<K, V>[] newHashTable = new TreeMap[newM];
for(int i = 0 ; i < newM ; i ++)
newHashTable[i] = new TreeMap<>();
int oldM = M;
this.M = newM;
for(int i = 0 ; i < oldM ; i ++){
TreeMap<K, V> map = hashtable[i];
for(K key: map.keySet())
newHashTable[hash(key)].put(key, map.get(key));
}
this.hashtable = newHashTable;
}
}
 Copy code 
版权声明
本文为[Zhao senqing]所创,转载请带上原文链接,感谢
https://javamana.com/2021/05/20210504185010736R.html

  1. Prototype与JQuery对比
  2. Three ways of data transmission between threads in Java and source code display
  3. Jdon causes 99% of CPU and Tomcat dies -- banq replies
  4. docker 原理之 user namespace(下)
  5. Simulating AOP injection with domain events
  6. Spring 3.1 finally adds cache support
  7. Comparison between prototype and jquery
  8. User namespace of docker principle (2)
  9. The way to learn java IO stream and XML
  10. Why does a seemingly correct code cause the Dubbo thread pool to be full
  11. 0 基础 Java 自学之路(2021年最新版)
  12. 0 basic Java self study road (latest version in 2021)
  13. c#—基础拾遗(1) 面向对象
  14. C - basic information (1) object oriented
  15. 技术分享|SQL和 NoSQL数据库之间的差异:MySQL(VS)MongoDB
  16. Technology sharing differences between SQL and NoSQL databases: MySQL (VS) mongodb
  17. PHP教程/面向对象-3~构造函数和析构函数
  18. Spring Cloud的Feign客户端入门
  19. 优化Spring Boot应用的Docker打包速度
  20. PHP tutorial / object oriented - 3 ~ constructor and destructor
  21. Introduction to feign client of spring cloud
  22. Optimizing docker packaging speed of spring boot application
  23. 尚硅谷宋红康Java基础教程2019版
  24. 尚硅谷宋红康Java基础教程2019版
  25. Song Hongkang Java foundation course 2019
  26. Song Hongkang Java foundation course 2019
  27. Redis 6 的多线程
  28. Multithreading of redis 6
  29. SpringCloud-微服务架构编码构建
  30. SpringCloud-微服务架构编码构建
  31. Linux作业控制
  32. Coding construction of springcloud microservice architecture
  33. Java中几个常用并发队列比较 | Baeldung
  34. 为什么Java后端在创业企业中并不流行? -reddit
  35. Coding construction of springcloud microservice architecture
  36. Linux job control
  37. Comparison of several common concurrent queues in Java
  38. Why is java backend not popular in start-ups- reddit
  39. docker 资源限制之 cgroup
  40. 大数据环境: hadoop和jdk部署
  41. CGroup of docker resource limitation
  42. Big data environment: Hadoop and JDK deployment
  43. Spring与Hibernate与JPA的整合(详细配置和源码)
  44. Integration of spring, hibernate and JPA (detailed configuration and source code)
  45. 《精通JPA与Hibernate:Java对象持久化技术详解》的源代码下载
  46. 《精通JPA与Hibernate:Java对象持久化技术详解》的源代码下载
  47. "Proficient in JPA and Hibernate: Java Object Persistence technology" source code download
  48. "Proficient in JPA and Hibernate: Java Object Persistence technology" source code download
  49. Redis、Kafka或RabbitMQ:选择哪个作为微服务消息代理? - otonomo
  50. Java Stream和Collection比较:何时以及如何从Java API返回Stream而不是集合Collection? - TomaszKiełbowicz
  51. 如何在SpringBoot中使用Hibernate @NaturalId?
  52. RPC框架设计----NIO编程通道(Channel)
  53. The use of jquery
  54. Redis, Kafka or rabbitmq: which one to choose as the micro service message broker- otonomo
  55. Comparison of Java stream and collection: when and how to return stream instead of collection from Java API- TomaszKie ł bowicz
  56. How to use hibernate @ naturalid in springboot?
  57. RPC framework design -- NiO programming channel
  58. RPC框架设计----NIO编程Selector (选择器)
  59. RPC framework design -- NiO programming selector
  60. Linux centos重启命令