The hash algorithm

  • Direct addressing: Linear transformation of the key value to obtain the hash address

  • Number analysis: find the most different parts of the data, hash the address

  • Square middle method: take the middle bits after the square of the key value as the hash address

  • Folding method: divide the key value into several parts and overlay these parts to obtain the hash address

  • Mod method: the key mod the length of the hash table, the result as the hash address

Hash conflict handling method

  • Open addressing method:

If a conflict occurs, perform operations such as +1 and +2 on the basis of the original result to find a position that does not conflict. Disadvantages: Nodes cannot be deleted at will, which affects the search of other nodes and can only be marked as deleted nodes. Lookup speed is also affected due to conflicting left-right movement solutions

  • Chain address method:

Link the conflicting sections into a linked list. Simple. However, when the list length is too long, the search speed will be affected to a certain extent.

  • Then the hash method

In case of a conflict, using another hash algorithm to hash keys is slow. And if they collide again, they have to hash again.

  • Public overflow area

If there is a conflict in the overflow zone, it will take some time.