关于hashMap的长度为什么是2的n次方的问题

本文主要是介绍关于hashMap的长度为什么是2的n次方的问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

首先，我们需要明确：这么做是为了加快计算与减少哈希冲突

加快计算

首先如果拿到key后要去hashmap的内存地址中找到key所在的位置，那么需要进行hash(KEY) % 数组长度的操作，但是取余操作是很慢的，为了加快速度，我们将取余操作改成&（与）操作，能够大大提高计算的速度，但是为了保证替换成&后计算的值和hash(KEY) % 数组长度的结果相同，就需要将公式改成hash(KEY) & (length - 1)。这样既保证了结果的正确性，也提高了运算的速度。

减少哈希冲突

假设现在数组的长度length可能是偶数也可能是奇数。length 为偶数时，length-1 为奇数，奇数的二进制最后一位是 1，这样便保证了 hash &(length-1) 的最后一位可能为 0，也可能为 1（这取决于 h 的值），即 & 运算后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性。
而如果 length 为奇数的话，很明显 length-1 为偶数，它的最后一位是 0。这样hash & (length-1)的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。并且正是因为hash值就是要用低位的信息，那么结合&操作，&的另一个数最好低位全是1。所以如果素组的长度为2的n次方，那么2的n次方减一后，低位全部是1，取&运算后能够最大限度的减少哈希冲突。

这篇关于关于hashMap的长度为什么是2的n次方的问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！