Hash table~

Commonly used Hash How to construct a function

• direct addressing
• Digital analysis
• Square with the middle method
• Division and remainder

frequently-used Hash Conflict resolution

• Open addressing
  1） Linear exploration
  2） The square probe
• Chain address

eg： Using a keyword sequence {1,9,12,11,25,35,17,29} Create a Hash surface , Loading factor a by 1/2, Try to determine the meter length m, Use division and remainder method to construct Hash function , Use the chain address method to handle conflicts , And calculate the average search length when the search is successful or unsuccessful ASL, and ASL2（ Only comparisons with keywords are counted ).

Loading factor = The number recorded in the table / Length of scattered list
be ： Long table m = 16

Of the division and remainder method Hash The function construction formula is H(key)=key Mod p , among p Is the maximum prime number not greater than the table length
be ：H(key)=key Mod 13

From this Hash The table is shown in the figure
Average search length of successful search ASL
ASL₁=(1+1+1+1+2+1+1+2) / 8=1.25

Average length of unsuccessful lookups ASL
ASL₂=(0+1+0+1+1+0+0+0+0+2+0+1+2) / 13=0.62