英文:
Why AND(&) operator used calculating final index in Hashmap why not modulo(%) operator i.e hashValue & ()
问题
我正在尝试理解 HashMap 的实现。我发现在计算键哈希值之后，最终的哈希值是使用按位与操作符（hashValue & (n-1)）生成的，其中 n 是桶的大小。是否有人可以解释一下，为什么没有使用取模运算，取模运算也可以保证输出范围在桶的大小内呢？
英文:
I am trying to understand HashMap implementation. I found after calculating key hash value, final hash value is generated using AND operator (hashValue & (n-1)) where n is size of bucket.Could someone explain why modulo is not used which will also guarantee output range within bucket size.
答案1
得分: 2
& 运行速度更快，代价是仅适用于二的幂次。具体来说，如果 x 为非负整数且 n 为二的幂次，则 x & (n - 1) == x % n。对于哈希表，x & (n - 1) 也可以达到你想要的效果 — 即使 x 为负数，x & (n - 1) 也是如此，但对于 x % n 则不然。
这是完整且唯一的原因。
英文:
& runs faster, in exchange for working only for powers of two. (Specifically, x & (n - 1) == x % n if x is nonnegative and n is a power of two. x & (n - 1) also does what you want for a hash table -- even if x is negative, x & (n - 1) isn't -- unlike x % n.)
That's the complete and only reason.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论