Hash table - Review

1. Definition

Generally speaking , Hashes can be condensed into one sentence “ Convert an element to an integer through a function , So that the integer can uniquely represent this element .” The conversion function is called hash function H, in other words , If the element is key, Then the conversion is an integer H(key).

So for key Is an integer , What are the commonly used hash functions ？ Generally speaking, there are the following ：

① direct addressing ： The identity transformation （ namely H(key)=key）

② Linear transformation method ： namely H(key)=a*key+b;

③ Square with the middle method （ Rarely used ）： take key The middle bits of the square of are used as hash value .

④ Division and remainder ： hold key Divide by a number mod The remainder obtained as hash The method of value ：H(key)=key%mod

Through this hash function , You can convert a large number to no more than mod The integer of , So you can use it as a viable array subscript . Obviously mod When it's a prime number ,H(key) Cover as much as possible [0,mod） Each number in the range .

2. Conflicts and solutions

But the division and remainder method may have two different numbers key1 and key2, Their hash The values are the same .key2 You can no longer use this location , Defecation conflict .

There are roughly three ways to resolve conflicts ：

2.1 Linear exploration (Linear Probing)

When you get key Of hash value H(key), But the subscript in the table is H(key) The position of has been used by some other element , Then check the next position H(key)+1 Is it occupied , without , Just use this location ; Otherwise, continue to check the next position （ That is to say hash The value keeps increasing 1）.

If the table length is exceeded during the inspection , So go back to the top of the table and continue the cycle , Until you find a place to use , Or find that all positions in the table have been used .

obviously , This practice tends to lead to clustering , That is, several positions in the table are used , This generation will reduce efficiency to some extent .

2.2 Square detection (Quadratic probing)

Avoid clustering , In the following order ：

If H(key)+k^2 It exceeds the watch length TSize, Then put  H(key)+k^2 For meter length TSize modulus ;

If H(key)+k^2<0, It will be （H(key)+k^2）%TSize + TSize)%TSize As a result （ It is equivalent to H(Key)-k^2 Keep adding one TSize Until a nonnegative number appears ）.

2.3 Chain address ( Zipper method ）

Different from the above two methods , The chain address method does not compute new hash value , It's about putting all the H(key) same key Connect into a single linked list .

This allows you to set an array Link, The scope is Link[0]~Link[mod], among Link[h] Deposit H(Key)=h A single linked list of , So when more Key words key Of hash All are h when , You can put these conflicts directly key straight .

  Connect with a single linked list , At this point, you can traverse the single linked list to find all H(key)=h Of key.

2.4 Double hash

You need to use two hash functions , When passing through the first hash function H1(key) When the obtained address conflicts , Then use the second hash function H2(key) Calculate the address increment of the keyword . Its specific hash function form is as follows ：

Initial detection position  . among i Is the number of conflicts , For the initial 0. In double hashing , At most m-1 This probe will traverse all the positions in the table , go back to Location . 

3. Hash lookup and performance analysis

I won't go into more details here , Relatively simple , Paste above