本文主要是介绍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 或者其他哈希表实现,可能不具备这种性质。
那为什么是两次扰动呢?
答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的;
这篇关于HashMap 的长度为什么是2的幂次方的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!