If you read a lot of other blogs and don't understand it, you see this one , You can understand it easily ! I'm convinced , Such a simple thing is too rigid to talk about the topic and not the principle. I can understand it , This kind of culture is really not good , I can't help but scold rubbish , What the hell , mislead and cause harm to the young men ! What problem can't be done after understanding the principle ?
You want to know Average lookup length of hash table lookup failures , You need to know what a search failure is ! Take a chestnut ：8 Numbers key%11 Here's how it works ：
Hash address 012345678910
keyword 331131234382722
Number of conflicts 00023017
What is search failure ? For example, you need to check 55 This keyword , You must %11, be equal to 0, Check the address 0 by 33, incorrect , Next 1, incorrect , Continue to search down until empty to know that the keyword must not exist , Or it'll be left at the empty address . So the table above , The calculated address is 0 The key words of 9 Time to know that there is no such keyword is called search failure ; The calculated address is 1 The key word of the is only detected 1-8 To determine that the element does not exist , and so on . But pay attention , If the calculated address is 8 Or 9 Of ,10 Of , You only need to look it up once to know that the address is empty , failed . So just look it up once . And you should know that if the search is successful, it is divided by the number of keywords , But the search failure is divided by the number you want to module 11, Do remember , It's not the number of addresses , Not the number of keywords . in summary , The average length of the lookup failed is （9+8+7+6+5+4+3+2+1+1+1）/11=47/11. Don't worry about it , The original title of the book .
And pay attention , The questions are as follows H(key)=key%7：
Hash address 012345678
keyword 982230871140620
Be careful ,%7 Can only be mapped to 0-6, Hash function mapping not possible 7, Therefore, the average search length is （9+8+7+6+5+4+3)/7=6. You may want to curse your mother when you see this , What the hell , Don't worry . I'll let you understand , Because I hate prawns and chickens the most. Blog idiots , It's not clear and it doesn't explain , It's a mistake ,low Coffee !!! All right, back to business . The first thing to know , We're looking for the average search length, but we're looking for probabilities , For successful average lookup length , The probability of finding each element is 1/8, this 8 Is the number of keywords . That is to say , You can only choose if the search is successful 8 One of them , Otherwise it won't succeed , So they're all waiting for probability 1/8 In the case of . The same is true of lookup failures , The search probability for each location is 1/7, be careful 7 It's the number you want to model , That is to say , Take any number you like , Model 7, It can only be 0,1,2,3,4,5,6, One of them is , It can't be 7,8 Later numbers , So just calculate the address in the 0-6 Probability in . If the calculated address is 0, So we need to compare 9 second , and so on , So it can only be the formula above , Don't make a mistake ! Also note that some hashes are not completely filled , There is a vacancy in the middle , I'm sure you don't have to explain it after reading the above principle , If you find a vacancy, it means it doesn't exist , Otherwise, it will occupy the space . Note that all of the above is linear detection , If it's a square probe, notice the left and right jumps , Specific analysis of specific problems , It doesn't unfold . I believe you can see that you have really understood what is called search failure average search length . You need to scold spam blogs , For me, too , I write bad everyone to me scold , In this way, we can reduce the dregs of people's children , What's the use of just talking about how to operate without talking about the principle , Another way to describe no or not . To know what it is, we should know why !!! If there is any mistake above , Please point it out , Thank you very much !
Like this blog , True Buddha , When he came, balabalabala was there to calculate , It's like someone can't compute a hash table , What people really don't understand is the calculation of the average search length of a failed search , The real title party . Junk articles !!!
Technology