## 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 ``````

https://javamana.com/2021/05/20210504185010736R.html