Java实现HashMap计算存储索引 应使用模运算还是按位与运算符？

核心前提说明 #

key.hashCode() & (array.length - 1) 方案存在硬性约束：底层数组长度必须是2的整数次幂。
当数组长度为2^n时，其二进制表现为1后接n个0，array.length - 1的二进制就是n个连续的1，此时按位与操作会直接保留哈希值的低n位，计算结果和key.hashCode() % array.length完全等价。如果数组长度不满足这个约束，按位与的计算结果要么超出数组范围，要么分布极度不均匀，完全不可用。

模运算（%）方案优缺点 #

• 优点
  • 无数组长度限制，无论数组长度是质数、合数、任意正整数，都能得到[0, array.length-1]范围内的合法索引
  • 散列效果灵活性更高：当数组长度选择质数时，能最大化打散哈希值，大幅降低哈希碰撞概率，对本身哈希值分布不均匀的场景适配性更好
• 缺点
  • 运算性能低：模运算属于整数除法类操作，CPU运算耗时是按位与的3~5倍，高并发、哈希计算频繁的场景下性能差距会被明显放大
  • 如果数组长度选择不当（比如选了偶数或带多个公因数的数），哈希碰撞概率会大幅上升，需要额外做哈希值预打散处理

按位与（&）方案优缺点 #

• 优点
  • 运算性能极高：按位与是CPU底层位操作，单时钟周期即可完成，性能远高于模运算
  • 工程实现简单：只要保证数组初始化、扩容后的长度始终为2的整数次幂，计算逻辑非常简洁，工业界应用成熟度高
• 缺点
  • 强依赖数组长度约束：一旦数组长度不符合2的整数次幂要求，方案完全失效
  • 哈希值利用率低：默认只取哈希值的低位参与计算，如果没有额外的哈希值打散逻辑（比如JDK HashMap中会先将哈希值高低位异或的操作），哈希值高位完全不参与索引计算，哈希值低位分布不均匀时碰撞概率会非常高

方案选择建议 #

二者没有绝对的优劣，根据场景不同选择不同：

• 如果是学校作业场景：如果作业没有强制要求数组长度必须为2的整数次幂，优先选模运算方案即可，实现逻辑简单，不需要额外处理数组长度约束，不容易出现逻辑错误
• 如果是工业级实现场景：追求高性能，且能保证数组长度始终满足2的整数次幂，同时搭配哈希值预打散逻辑，优先选择按位与方案，性能优势非常明显，目前主流的工业级HashMap实现均采用该方案

内容的提问来源于stack exchange，提问作者Phrille