This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021
Solutions to hash conflicts:
- Open address method
- Zip method (chain address method)
- Then the hash method
Open address method
The principle is that when a hash conflict occurs, the current address is benchmarking and the next address is searched based on the addressing method (probe addressing). If the conflict persists, addressing continues until an empty location is found. The general hash function form is:
Hi= (key) +di) % m (I = 1,2… , n)
Where H (key) is the hash function, m is the table length, and DI is the incremental sequence. The value method of increment sequence is different, and the corresponding rehash method is also different.
Addressing methods
1. Linear probe
The next cell in the table is searched sequentially until an empty cell is found or the entire table is searched.
That is, when the hash value is 3 and the hash table length is 11, the linear probe process is as follows:
H1 = (3+1)%11 = 4, if 4 still conflicts, hash, i.e
H2 = (3+2)%11 = 5 …. This is a linear series of increments until an empty position is found.
2. Double probe
The characteristic of this method is that, when the hash conflict, the left and right of the table for jump detection, relatively flexible.
Di = 1^2, -1^2, 2^2, -2^2….
Assume that when the hash value is 3 and the hash table length is 11, the process of using the second probe is as follows:
H1 = (3+1^2)%11 = 4
H2 = (3+(-1)^2)%11 = 2 …
This method is used until an empty position is found.
3. Pseudo-random detection
This method is to generate some random series of values, and given a random number as a starting point.
Assume that when the hash value is 3 and the hash table length is 11, the process of using pseudo-random detection is as follows:
Suppose the resulting random series is 2,5,9…. ,
H1 = (3+2)%11 = 5
H2 = (3+5)%11 = 8
This method is used until an empty position is found.
Two, zipper method
The zipper method is applied to the hashMap and hashSet. When a hash conflict occurs, a single linked list is constructed at the location of the hash conflict (that is, all elements with hash address I form a single linked list called a synonym chain), and the head pointer of the single linked list is stored in the ith position of the hash table.
The chained address method is suitable for frequent inserts and deletions.
Third, rehash method
When a hash function is used to calculate a hash position, the hash is used again when different hashes appear at the same position until there is no conflict.