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

HashMap 中的长度为2的幂次方是为了提高HashMap的效率和减少冲突概率。当我们向HashMap中添加元素时，我们会根据元素的哈希值和数组长度计算出元素在数组中的位置。如果长度为非2的幂次方，则在计算元素位置时会涉及到复杂的位运算，而长度为2的幂次方的数组可以通过位运算来快速计算出元素在数组中的位置，从而提高效率。此外，长度为2的幂次方还可以减少冲突概率，因为哈希值除以2的幂次方得到的余数比较均匀，减少了元素在数组中分布不均的情况。因此，长度为2的幂次方是HashMap中一个非常重要的设计决策。

相关问题

hashmap 为什么采用2的幂次方

HashMap采用2的幂次方作为数组长度的原因有以下几点：

1. 快速计算数组下标：使用2的幂次方作为数组长度，可以通过位运算（&）快速计算数组下标，而不需要使用取模等较慢的操作。

2. 减少哈希冲突：哈希函数通常会将键的哈希码映射到数组的下标上，如果数组长度不是2的幂次方，哈希码的低位可能无法充分参与计算，导致哈希冲突较多，而使用2的幂次方作为数组长度，可以保证哈希码的所有位都可以充分参与计算，减少哈希冲突的概率。

3. 方便扩容：HashMap在扩容时，会将原来的数组长度翻倍，如果数组长度不是2的幂次方，翻倍后可能会导致哈希码映射到的下标发生大幅度变化，需要重新计算所有键的下标，而使用2的幂次方作为数组长度，翻倍后只需要将原来的下标的低位增加一位即可，不需要重新计算所有键的下标，方便扩容操作。

hashmap为什么采用2的幂次方

HashMap采用2的幂次方作为数组的长度是因为这样可以提高散列的效率。具体原因如下：

1. 取模运算可以转化为位运算：HashMap中取模运算可以转化为与运算，即h & (length-1)，其中length为数组长度，因为length总是2的幂次方，所以length-1的二进制表示中所有位都是1，这样与运算的结果就是h的二进制表示中低位的length-1位，可以在保证散列均匀的情况下减少计算量。

2. 减少碰撞概率：如果数组长度不是2的幂次方，那么在进行取模运算时，余数的分布会出现偏差，导致某些桶的负载过高，增加碰撞的概率。而采用2的幂次方作为数组长度，可以使得余数的分布更加均匀，减少碰撞的概率。

3. 提高效率：在进行扩容操作时，如果数组长度是2的幂次方，那么新的数组长度就可以通过移位运算快速计算得到，而不需要进行乘法运算。这样可以提高扩容的效率。

综上所述，HashMap采用2的幂次方作为数组长度可以提高散列的效率，减少碰撞概率，提高扩容的效率。