关注
HashMap中通过h&(length-1)的方法来代替取模
static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值
return h & (length-1);
}
l
ength为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了效率;其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列
查看原帖
5 7
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
14113次浏览 168人参与
# 你最讨厌面试被问什么 #
1391次浏览 26人参与
# 牛客AI体验站 #
17883次浏览 302人参与
# 有转正机会的小厂实习值得去吗? #
714次浏览 19人参与
# 牛友们,签完三方你在忙什么? #
137405次浏览 994人参与
# 担心入职之后被发现很菜怎么办 #
282550次浏览 1185人参与
# 如何缓解入职前的焦虑 #
258894次浏览 1451人参与
# 校招第一份工作你干了多久? #
139428次浏览 609人参与
# 去年的flag与今年的小目标 #
34329次浏览 337人参与
# 牛客租房专区 #
151589次浏览 1488人参与
# 秋招开始捡漏了吗 #
229480次浏览 1044人参与
# 九月了,是考研还是就业? #
89369次浏览 557人参与
# 秋招投递攻略 #
268814次浏览 2554人参与
# 这份实习,有没有动摇过你的职业方向? #
2261次浏览 40人参与
# 搜狐工作体验 #
4120次浏览 30人参与
# 机械人求职现状 #
33664次浏览 297人参与
# 我是XXX,请攻击我最薄弱的地方 #
61806次浏览 410人参与
# 用友工作体验 #
18090次浏览 151人参与
# 你的工资什么时候发? #
57517次浏览 355人参与
# 你的实习什么时候入职 #
348120次浏览 2291人参与