首页 > 其他 > 详细

Double Hashing

时间:2019-01-05 17:03:46      阅读:243      评论:0      收藏:0      [点我收藏+]

Data Structure and Algorithm Analysis in C++

5.4.3 Double Hashing

In the beginning of chapter 5.4, the formula  hi(x) = (hash(x) + f(i))  is mentioned and  f(i) is defined as f(i) = i ;

Here f(i) is defined as f(i) = i * hash2(x) and hash2(x) = R - (x mod R) where R is a prime smaller than TableSize. If R = 7 then hash2(x) = 7 - (x mod 7).

The case it uses is as followed.  Figure 5.18 shows the result of inserting keys {89, 18, 49, 58, 69} into a hash table.

技术分享图片

 

Hash(x), or hash1(x) to be precise, is defined as hash1(x) = x % 10  //  TableSize = 10. 

So if there‘s no collision, h(x) = hash1(x);  otherwise hi(x) = { hash1(x) + i * hash2(x) } % TableSize .

The first collision occurs when 49 is inserted. hash2(49) = 7 ? 0 = 7, so 49 is inserted in position 6    // { 49%10 + (7 - 1* 49%7)  } % 10 .

hash2(58) = 7 ? 2 = 5, so 58 is inserted at location 3     // ( 8 + 1*5 )%10 .

Finally, 69 collides and is inserted at a distance hash2(69) = 7?6 = 1 away.

If we tried to insert 60 in position 0, we would have a collision. Since hash2(60) = 7 ? 4 = 3, we would then try positions 3, 6, 9, and then 2 until an empty spot is found.

 

Double Hashing

原文:https://www.cnblogs.com/heifengli/p/10225160.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!