为什么hashMap的容量扩容时一定是2的幂次

一时失言乱红尘 2022-03-30 03:29 261阅读 0赞

**目录**

一、HashMap通过哈希算法得出哈希值之后，将键值对放入哪个索引的方法

二、再例如：hashMap源码获取元素的位置

三、根据Hash算法进行观察：

--------------------

# 一、HashMap通过哈希算法得出哈希值之后，将键值对放入哪个索引的方法 #

static int indexFor(int h, int length) {
    
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    
    return h & (length-1);
    
    }

HashMap的容量为16转化成二进制为10000，length-1得出的二进制为01111

哈希值为1111

![70][]

可以得出索引的位置为15

假设

HashMap的容量为15转化成二进制为1111，length-1得出的二进制为1110

哈希值为1111和1110

![70 1][]

那么两个索引的位置都是14，就会造成分布不均匀了，

**增加了碰撞的几率，**

**减慢了查询的效率，**

**造成空间的浪费。 **

总结：

1.  因为2的幂-1都是11111结尾的，所以碰撞几率小。

# 二、再例如：**hashMap源码获取元素的位置** #

**static int** indexFor(**int** h, **int** length) \{

*// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";*

**return** h & (length-1);

解释：

h:为插入元素的hashcode

length:为map的容量大小

&：与操作 比如 1101 & 1011=1001

如果length为2的次幂 则length-1 转化为二进制必定是11111……的形式，在于h的二进制与操作效率会非常的快，

而且空间不浪费；如果length不是2的次幂，比如length为15，则length-1为14，对应的二进制为1110，在于h与操作，

最后一位都为0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费

PS: 这都是老版本jdk的源码，1.7,8之后都没有这个方法了, 但是计算位置index的思想不变，就是要充分散列，减少碰撞

下面是1.8的代码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) \{

Node<K,V>\[\] tab; Node<K,V> p; int n, i;

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

if ((p = tab\[i = (n - 1) & hash\]) == null) //计算*index*

tab\[i\] = newNode(hash, key, value, null);

# 三、根据Hash算法进行观察： #

我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。

所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式那？java中时这样做的，

Java代码

1.  **static int indexFor(int h, int length) \{  **

1.         **return h & (length-****1);  **

1.     \}

首先算得key得hashcode值，然后跟数组的长度-1做一次“与”运算（&）。看上去很简单，其实比较有玄机。比如数组的长度是2的4次方，那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问，为什么hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高，我以2的4次方举例，来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。

看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！

![4b3732d6-fb5f-369b-b50d-e8b8325c69d4.jpg][]

所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

说到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面annegu的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。

所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：

Java代码   ![icon_star.png][]

1.  // Find a power of 2 >= initialCapacity

1.          **int capacity = ****1;  **

1.          **while (capacity < initialCapacity)   **

1.              capacity <<= 1;

总结：

本文主要描述了HashMap的结构，和hashmap中hash函数的实现，以及该实现的特性，同时描述了hashmap中resize带来性能消耗的根本原因，以及将普通的域模型对象作为key的基本要求。尤其是hash函数的实现，可以说是整个HashMap的精髓所在，只有真正理解了这个hash函数，才可以说对HashMap有了一定的理解。

该博文用于扩展学习 用于[Java集合深度解析之全面解析HashMap][Java_HashMap]

转载：[**https://blog.csdn.net/sd\_csdn\_scy/article/details/57083619**][https_blog.csdn.net_sd_csdn_scy_article_details_57083619]

[https://www.cnblogs.com/wengshuhang/][https_www.cnblogs.com_wengshuhang]

[https://blog.csdn.net/weixin\_36910300/article/details/79538421][https_blog.csdn.net_weixin_36910300_article_details_79538421]

[70]: /images/20220330/3a3bd1fe6c834c059404ece7dbc5097c.png
[70 1]: /images/20220330/1a207f48ff5e4660b6bad9c31ded4f1c.png
[4b3732d6-fb5f-369b-b50d-e8b8325c69d4.jpg]: /images/20220330/d1ffa87d2c134c1ebcc82423a02a41e4.png
[icon_star.png]: /images/20220330/2a4a0a1fa7624f82a4020d0619f2ea3c.png
[Java_HashMap]: https://blog.csdn.net/gududedabai/article/details/85631398
[https_blog.csdn.net_sd_csdn_scy_article_details_57083619]: https://blog.csdn.net/sd_csdn_scy/article/details/57083619
[https_www.cnblogs.com_wengshuhang]: https://www.cnblogs.com/wengshuhang/
[https_blog.csdn.net_weixin_36910300_article_details_79538421]: https://blog.csdn.net/weixin_36910300/article/details/79538421