java - 为什么 HashMaps 使用二的幂来实现？

Question

我的问题是为什么 hashmap bucket size 是 2 的幂，我已经在 stackoverflow 上看了很多答案，但我仍然不相信。原因是:

1. 我读到容量是 2 的幂使得 & 操作更有效地计算索引，所以我的问题是它在这里到底有什么用。我的大小可能是 3 的幂，我仍然可以像这样执行 & 操作 (hash)&(length-1) 那么为什么它应该是 2 的幂？

2. 另外，如果容量不是 2 的幂，为什么我需要做余数运算？

Answer 1

当你从一个 2 的幂数中减去 1 时，你得到的是一个二进制表示全为 1 的数。 16 是 2 的幂。如果你从中减去 1，你会得到 15，它的二进制表示是 1111。现在，如果你对任何数字与 1111 进行按位与，你将得到的最后 4 位换句话说，它等于数字除以 16 的模数(除法运算通常是一项昂贵的运算。因此，按位运算通常优于除法)。最后 4 位将计算为 0 到 15 之间的任何数字，这些数字是您的基础数组的索引。

您可以改用 17 号。在这种情况下，从中减去 1 后，您将得到 16，即二进制形式的 10000。现在你用 16 对一个数字进行有点明智的 AND，你将丢失数字的所有位，除了从末尾算起的第 5 位。因此，无论您取多少，数组索引都将是 16 或 0。这意味着您会遇到很多冲突，这反过来又意味着性能不佳。您需要 O(log n) 而不是 O(1) 的检索，因为当发生碰撞时，给定桶中的所有节点都将存储在红黑树中。不仅。如果您在多线程环境中使用 ConcurrentHashMap，您会遇到很多同步，因为所有新添加的内容最终都会出现在非常少量的桶中(只有两个 - 0 和 16上述情况)，当你在一个已经有其他节点的桶中添加新节点时，该桶将被锁定，以避免由于多线程修改而导致数据不一致。因此，其他尝试添加新节点的线程需要等到当前线程释放锁。

最后，我还应该提一下，Java HashMap 实现还将 key 的哈希码向右移动 16 位，并在执行按位与 ( length - 1) 以确保也捕获高阶位的影响。

所以，基本上重点是，如果大小是 2 的幂，则键将更均匀地分布在数组中，冲突最小，从而导致更好的检索性能(并且在 ConcurrentHashMap< 的情况下同步更少) 与任何其他不是 2 的幂的大小进行比较时。