首页 > 技术文章 > 关于hashMap的长度为什么是2的n次方的问题

hello-liu 2021-11-29 00:48 原文

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

加快计算

首先如果拿到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,取&运算后能够最大限度的减少哈希冲突。

推荐阅读