Average lookup length when hash table lookup fails

Preface :
In the hash table that uses linear detection and hashing to deal with conflicts , Many people are concerned about the average search length when the calculation fails , Divisor should be hash table length , Or hash function :mod The following number is not clear , First, let's solve this problem first .

Question 1 : It is divided by mod The following number is the hash table length ?

answer : Is the hash table length .

First of all, we need to make it clear that every position of the subscript in the hash table may store a keyword data , Therefore, the average search length of failures we require is :

 Average lookup length failed = Add the number of failed searches for each location / Hash table length 

So under what circumstances is every location a search failure ?
The first position encountered is NULL It is a failure when , Because the linear detection hashing method is set , When the hash table is full , We can think that the number stored in all subsequent subscript positions is subscript 0 From constant conflict , such as mod by 6, We need to save the sequence {6,12,18,24,30,36} Isosequence .
So if we want to find the number 30 when , The number of comparisons is 5 Time , That is, we divide numbers by mod Get the hash function value, that is, the subscript is 0, At this time, we compare the value 6 It doesn't match , We wonder if the number we are looking for is subscripted 0 There was a conflict , Will linear detection and hashing be arranged later , So we continue with the subscript 1 Keyword value comparison , At this time, the comparison value is 12, Still don't match , Let's think about it , Will the number we are looking for conflict again , It is hashed by linear detection later , therefore , We can only look back , At this time, we continue to compare , Analogy us in turn when we compare 5 When the time , Finally, it matches the number we are looking for .
Then if what we are looking for is 42 when , Then we can introduce the subscript 0 The number of failures occurred , Keep pushing back , Until the comparison value is NULL, We just give up looking for : Compare 7 Time
The subscript is 1 when , How many times will it fail ? In fact, the calculation of failure times is to assume the most extreme situation , Less than the heart of the Yellow River die , We decide that if the number we are looking for does not match the coordinate position , That is conflict , It must be next . therefore :
When subscript is 1 when : The number of search failures is 6 Time ,
When subscript is 2 when . The number of search failures is 5 Time
When subscript is 3 when . The number of search failures is 4 Time
When subscript is 4 when . The number of search failures is 3 Time
When subscript is 5 when . The number of search failures is 2 Time
When subscript is 6 when . The number of search failures is 1 Time

Because our sequence has 6 Data element , The above reasoning is that the hash table length is 7 when , The result of reasoning . Subscript to be 6 The location of the for NULL .

According to the above information, we can draw our hash table

Keyword sequence :{6,12,18,24,30,36}, The hash function is H(Key)=Key MOD 6
The loading factor is 6/7

So the average number of search failures is
(7+6+5+4+3+2+1)/7=4

Example : Put the keyword sequence (7,8,30,11,18,6,13) Hash is stored in hash table , Hash storage space is from subscript 0 The first one-dimensional array , The hash function is H(Key)= Key MOD 7, Linear detection and hashing are used to deal with conflicts . The required filling factor is 0.7
(1) Draw a hash table of structures :
(2) Calculate the average search length when the search succeeds and fails in the case of equal probability :

The average length when the search is successful is :ASL( success )=(1 * 5+2 * 2)/7=9/7
The average length when the search fails is :
ASL( Failure )=(4+3+2+1+5+4+3+2+1+1)/10=26/10=13/5