一文读懂HashMap和HashTable的区别以及常见面试题( 八 )
\n
对length取模来得到hash是常用的hash索引方法 ， 这里采用位运算的话效率更高 。
\n我们回到indexFor方法 ， 该方法仅有一条语句：h&(length - 1) ， 这句话除了上面的取模运算外还有一个非常重要的责任：均匀分布table数据和充分利用空间 。
\n这里我们假设length为16(2^n)和15 ， h为5、6、7 。
\n当n=15时 ， 6和7的结果一样 ， 这样表示他们在table存储的位置是相同的 ， 也就是产生了碰撞 ， 6、7就会在一个位置形成链表 ， 这样就会导致查询速度降低 。 诚然这里只分析三个数字不是很多 ， 那么我们就看0-15 。
\n而当length = 16时 ， length – 1 = 15 即1111 ， 那么进行低位&运算时 ， 值总是与原来hash值相同 ， 而进行高位运算时 ， 其值等于其低位值 。 所以说当length = 2^n时 ， 不同的hash值发生碰撞的概率比较小 ， 这样就会使得数据在table数组中分布较均匀 ， 查询速度也较快 。
\n这里我们再来复习put的流程：当我们想一个HashMap中添加一对key-value时 ， 系统首先会计算key的hash值 ， 然后根据hash值确认在table中存储的位置 。 若该位置没有元素 ， 则直接插入 。 否则迭代该处元素链表并依此比较其key的hash值 。
推荐阅读
- 地下城堡|《代号：破晓》官网“暗藏”剧情，你都读懂了吗？
- 法术|双城之战：羁绊、海克斯强化、装备一文看懂
- 仙剑奇侠传七|“吃鸡”游戏中单价最高的氪金物品！氪度力压车皮，却一文不值！
- 打野|王者荣耀：S25赛季打野需要注意什么？读懂这篇攻略，轻松上分
- 地下城与勇士|DNF：DNF超高质量减负，9.14减负改动一文看完
- 金泰相|“亚军不配找借口”Doinb谈亚军一文不值，只有S11夺冠才能找回颜面
- 梦幻西游|梦幻西游：老王打错灵犀玉损失5000元，百万无级别变得一文不值
- 电子竞技|电竞精神一文不值，贝克曼惨遭炮轰，久城透露QG假赛隐情！
- 孙一文|王者荣耀孙一文联动实锤？采访透露设计想法，皮肤想要带龙标
- 孙一文|王者荣耀：孙一文想要夏洛特冠军皮肤，两点要求让天美无能为力！