Closed hash and open hash resolve hash conflicts

Closed hash and open hash solve hash conflicts

Closed hash ：
It's also called open addressing , When a hash conflict occurs , Find the right empty location
The way to find an empty location ：

1. Linear detection method
   Start from where the conflict occurred , Sequential backward detection , Until we find the next empty position

Advantages of linear detection ： Implement a simple
Disadvantages of linear detection ： Hash conflicts tend to accumulate , Making it necessary to compare several times to find a key , Inefficient search

2. Second detection
   Suppose the empty position is H：
   H = (H0 +i ^2)% m
   perhaps ：H = ( H0- i^2)% m
   among ：i = 1,2,3…, H0 Is through the hash function Hash(x) Key to element key The calculated position ,m Is the size of the table

Some hash structures only use H = (H0 +i ^2)% m, Some hash structures H = (H0 +i ^2)% m and H = ( H0- i^2)% m Use alternately

After exceeding the table length, you can return to the header according to the idea of circular queue （ Tail ） Recycle

Secondary detection alleviates the problem of conflict accumulation , But the disadvantage of closed hash is low space utilization

Hashing requires additional storage of the state of each location in the hash table , If you don't do that , Delete the element with hash conflict , It will affect the search of other elements , for example ：

If you remove 4, lookup 44 Think when 44 non-existent

There are three states ： empty , full , deleted

If the status is deleted when searching , It cannot be assumed that elements do not exist
Insert when the status is not full

Find an element in the closed hash , If you find empty, you think it doesn't exist , Therefore, closed hash does not allow the hash table to be full

The solution is to control the load factor through capacity expansion ：

Hash ：
Hash method is also called chain address method ( Open chain method ), First, we use hash function to calculate hash address for key set , Keys with the same address
Belong to the same subset , Each subset is called a bucket , The elements in each bucket are linked by a single chain table , The head nodes of each linked list are stored in the hash table .

As the elements continue to insert , The number of elements in each bucket is increasing , In extreme cases , It may lead to a lot of linked list nodes in a bucket , Will affect the performance of the hash table , therefore Sometimes you need to add capacity to the hash table

The best case for hashing is ： There is just one node in each hash bucket , When the number of elements is just equal to the number of buckets , You can add capacity to the hash table

Because the closed hash must keep a lot of free space to ensure the search efficiency , And the space occupied by the table item is larger than that of the pointer , So using an open hash saves storage space instead of a closed hash .
If all key value pairs are known in advance , It will not change after that , You can design a perfect hash function without conflict , At this point, the performance of closed hash is higher than that of open hash .