首页 > 其他 > 详细

哈希表中hash函数中的%和&

时间:2021-04-12 12:28:25      阅读:15      评论:0      收藏:0      [点我收藏+]

MyHashMap

  return h % M;

为了避免hash碰撞,我们将M往往设置成质数,避免由于键在某一范围比较集中所致大量的hash碰撞
如:当h值集中100-120,但是M取了100,这样hash所得值集中在0-20。

Java中的HashMap中

默认值M为16

  return h & (M - 1);
  • 等效取余
    M取值往往为2的幂次方,而M-1会产生低位全为1的情况,使得&运算结果小于M
  • 运算效率提高
    %运算的效率低于位运算
  • 碰撞问题
    产生大量碰撞的情况:
    二进制来看,参数key中M个低位常出现同一值。如M为4,而M-1其二进制为:1111
    参数key中的低位出现同一值,如:00001110,00101110,01001110
    但由此而言,产生hash碰撞的数据相差之间较大。

哈希表中hash函数中的%和&

原文:https://www.cnblogs.com/to-make-life-better/p/14646645.html

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