HashMap为何用(n-1)&hash计算下标
哪些公司问过
答案要点
- 容量为2的幂时,hash&(n-1)等价于对非负hash取模,结果落在[0,n-1]
- 与运算比取模快,且hash为负时%得负数,&结果仍非负
- 只用低位会增加冲突,hash()用h^(h>>>16)把高位扰动进低位
- 扩容翻倍后按hash&oldCap判断节点留在原位还是移到原位+oldCap
- 指定的初始容量会被tableSizeFor向上取整为2的幂
易错点
- 认为(n-1)&hash对任意n都等价于取模,只有n为2的幂才成立
- 忽略hash为负数时%取模会得到负下标
- 漏讲hash()的高16位扰动,只讲与运算本身
面试官常见追问
- 哈希表原理与哈希冲突的解决方法
- 如果容量不是2的幂,用(n-1)&hash会怎样?
- 为什么扰动是右移16位?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。