Several ways to resolve hash conflicts

1. What is? hash Conflict

The hash function is an image , Put any length of input , adopt Hash The algorithm is transformed into a fixed length output , This output is Hash value ;
When two different inputs , If the same output value is generated, it is a hash conflict

2. Solution

2.1 Open address method

This method is also called rehash , The basic idea is this ： When keyword key The hash address of p=H（key） When there is a conflict , With p Based on , Generates another hash address p1, If p1 Still conflict , And then to p Based on , Generates another hash address p2,…, Until you find a hash address that doesn't conflict pi , Store the corresponding element in it .

Linear detection method ： stay ThreadLocalMap Use in ;

This method detects the next address at a time , Insert until you have a free address , If the whole space can't find a spare address , Then there is overflow ;

advantage ： As long as the hash table has a place , Through constant detection , Always find the right place .
shortcoming ：
1. The number of detections is uncontrollable , Once the number of detections increases dramatically , It will seriously affect the reading and writing performance of the hash table ;
2. Deleting is more cumbersome ;

2.2 Chain address

The hash code corresponds to a linked list , When inserting elements , If the hash code conflicts , Insert the element into the linked list , It can be inserted head or tail .
When inquiring , Traverse the linked list corresponding to the hash code .
HashMap That's how it works .

advantage ： Simple processing , Easy to delete , Simply delete the corresponding node on the linked list ;
shortcoming ： Once there are many hash conflicts , The hash table will degenerate into a linked list , Query efficiency will increase from O(1) Turn into O(n).JDK8 Of HashMap In view of this situation, we have done optimization , Conflict exceeds 8 Will convert the linked list into Red and black trees , Improve query efficiency .

2.3 Then the hash method

Use hash function , Instead of a ;
If the hash code calculated by the first hash function conflicts , Use the second hash function to recalculate the hash code , Until there is no conflict ;
The same is true when querying , Call different hash functions in turn to calculate hash code , until Key equal .

int hash = hash1(key)、hash2(key)、hash3(key)......

shortcoming ： This method will increase the overhead of hash calculation , Affect the efficiency of reading and writing .

2.4 The public overflow area

While creating the hash table , Create an additional public overflow area , It is specially used to store elements with hash conflicts . When looking for , Look up the hash table first , If you can't find it, go to the public overflow area .

shortcoming ： There are many hash conflicts , The public overflow area will swell very much , Query efficiency also has an impact .