HashMap 的长度为什么是2的幂次方

2024-08-24 04:44

文章标签 hashmap 次方长度

本文主要是介绍HashMap 的长度为什么是2的幂次方，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HashMap 的长度为什么是2的幂次方

因为这样可以让计算桶位置的操作更加高效。

具体来说，如果 HashMap 的长度是 2 的幂次方，那么计算桶位置时可以使用位运算来代替除法运算，从而提高计算速度。

我们都知道为了找到 KEY 的位置在哈希表的哪个槽里面，需要计算 hash(KEY) % 数组长度

HashMap为了存取高效，就要尽量减少碰撞，将数据分配均匀，那么如何分配均匀，此时主要靠将数据存入到那个链表中的算法，这个算法就是 hash(KEY) & (length - 1)。& 是按位与运算，是一个位运算，而在计算机中位运算的效率很高，% 计算比 & 慢很多,这就是不用%运算的原因,为了保证 & 的计算结果等于 % 的结果需要把 length 减 1。

hash(KEY) & (length - 1)=hash(KEY) %length

既然两个计算出的hash值是相同的那当然是用效率更高的&

我做了一个小实验：

假设现在数组的长度：2 ^ 14 = 16384

String key = "zZ1!." 的 hash 值为 115398910

public static void main(String[] args) {String key = "zZ1!.";System.out.println(key.hashCode());// 115398910
}

hash & (length - 1) = 115398910 & 16383 = 6398 （你可以使用电脑的计算机验证一下是不是对的）6398 的二进制是 ‭0001100011111110‬

hash % length = 115398910 % 16384 = 6398

这样可以大大提高计算速度，因为按位与运算比取模运算要快得多。

另外，长度为 2 的幂次方的数组也可以更好地处理哈希冲突。在使用链表解决哈希冲突时，如果数组长度是 2 的幂次方，那么每个桶的链表长度最多只有 8 个元素，这样可以保证链表的查找效率。如果数组长度不是 2 的幂次方，那么桶的数量可能不能均匀分布，从而导致某些桶的链表长度很长，影响查找效率。

因此，为了提高 HashMap 的性能，通常建议将长度设置为 2 的幂次方。

骚戴理解：如果数组长度是 2 的幂次方，每个桶的链表长度最多只有 8 个元素是因为 JDK 1.8 中 HashMap 的实现使用了一种称为“树化”的策略，当某个桶中的链表长度超过了 8 个元素时，会将该链表转换成红黑树，以提高查找效率。

树化操作的前提条件是桶中的链表长度超过了阈值（默认为 8），而如果数组长度是 2 的幂次方，那么对于任意的哈希值，它与数组长度的按位与操作的结果一定是小于数组长度的。例如，如果数组长度是 16，那么对于任意的哈希值，它与 15 的按位与操作的结果一定是在 0 到 15 之间。

因此，如果数组长度是 2 的幂次方，那么对于任意的哈希值，它与数组长度的按位与操作的结果一定是小于数组长度的，也就是说，它一定可以作为桶的下标。而由于数组长度是 2 的幂次方，因此桶的数量也是 2 的幂次方，这样就可以保证桶的数量和数组长度是一致的，从而可以保证每个桶的链表长度最多只有 8 个元素。

需要注意的是，这种情况只针对 JDK 1.8 中 HashMap 的实现，如果使用其他版本的 HashMap 或者其他哈希表实现，可能不具备这种性质。