当前位置:网站首页>Average lookup length when hash table lookup fails
Average lookup length when hash table lookup fails
2022-07-05 12:20:00 【A finger leaf next to the giant】
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
边栏推荐
猜你喜欢
什么是数字化存在?数字化转型要先从数字化存在开始
Reinforcement learning - learning notes 3 | strategic learning
Understand redis persistence mechanism in one article
Take you two minutes to quickly master the route and navigation of flutter
强化学习-学习笔记3 | 策略学习
abap查表程序
Automated test lifecycle
16 channel water lamp experiment based on Proteus (assembly language)
Error modulenotfounderror: no module named 'cv2 aruco‘
Hiengine: comparable to the local cloud native memory database engine
随机推荐
struct MySQL
Simply solve the problem that the node in the redis cluster cannot read data (error) moved
Solution to order timeout unpaid
Understand redis persistence mechanism in one article
Intern position selection and simplified career development planning in Internet companies
[cloud native | kubernetes] actual battle of ingress case (13)
GPS數據格式轉換[通俗易懂]
Get data from the database when using JMeter for database assertion
Which domestic cloud management platform manufacturer is good in 2022? Why?
Linux安装部署LAMP(Apache+MySQL+PHP)
Solve the problem of cache and database double write data consistency
Complete activity switching according to sliding
Seven ways to achieve vertical centering
July Huaqing learning-1
MySQL function
调查显示传统数据安全工具在60%情况下无法抵御勒索软件攻击
Hash tag usage in redis cluster
一款新型的智能家居WiFi选择方案——SimpleWiFi在无线智能家居中的应用
嵌入式软件架构设计-消息交互
【ijkplayer】when i compile file “compile-ffmpeg.sh“ ,it show error “No such file or directory“.