深入理解HashMap的扩容机制

本是古典何须时尚 2024-04-17 17:52 17阅读 0赞

**一、什么时候扩容：**

网上总结的会有很多，但大多都总结的不够完整或者不够准确。大多数可能值说了满足我下面条件一的情况。

扩容必须满足两个条件：

**1、 存放新值的时候当前已有元素的个数必须大于等于阈值**

**2、 存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）**

**二、下面我们看源码，如下：**

首先是put()方法

<table> 
 <tbody> 
 <tr> 
 <td> <code>public</code>&nbsp;<code>V put(K key, V value) { </code> <code>　　　　</code><code>//判断当前Hashmap(底层是Entry数组)是否存值（是否为空数组）</code> <code>　　　　</code><code>if</code>&nbsp;<code>(table == EMPTY_TABLE) { </code> <code>　　　　　　inflateTable(threshold);</code><code>//如果为空，则初始化</code> <code>　　　　}</code> <code>　　　　</code> <code>　　　　</code><code>//判断key是否为空</code> <code>　　　　</code><code>if</code>&nbsp;<code>(key == </code><code>null</code><code>)</code> <code>　　　　　　</code><code>return</code>&nbsp;<code>putForNullKey(value);</code><code>//hashmap允许key为空</code> <code>　　　　</code> <code>　　　　</code><code>//计算当前key的哈希值　　　　</code> <code>　　　　</code><code>int</code>&nbsp;<code>hash = hash(key);</code> <code>　　　　</code><code>//通过哈希值和当前数据长度，算出当前key值对应在数组中的存放位置</code> <code>　　　　</code><code>int</code>&nbsp;<code>i = indexFor(hash, table.length);</code> <code>　　　　</code><code>for</code>&nbsp;<code>(Entry&lt;K,V&gt; e = table[i]; e != </code><code>null</code><code>; e = e.next) { </code> <code>　　　　　　Object k;</code> <code>　　　　　　</code><code>//如果计算的哈希位置有值（及hash冲突），且key值一样，则覆盖原值value，并返回原值value</code> <code>　　　　　　</code><code>if</code>&nbsp;<code>(e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) { </code> <code>　　　　　　　　V oldValue = e.value;</code> <code>　　　　　　　　e.value = value;</code> <code>　　　　　　　　e.recordAccess(</code><code>this</code><code>);</code> <code>　　　　　　　　</code><code>return</code>&nbsp;<code>oldValue;</code> <code>　　　　　　}</code> <code>　　　　}</code> &nbsp; <code>　　　　modCount++;</code> <code>　　　　</code><code>//存放值的具体方法</code> <code>　　　　addEntry(hash, key, value, i);</code> <code>　　　　</code><code>return</code>&nbsp;<code>null</code><code>;</code> <code>　　}</code> </td> 
 </tr> 
 </tbody> 
</table>

在put()方法中有调用addEntry()方法，这个方法里面是具体的存值，在存值之前还有判断是否需要扩容

<table> 
 <tbody> 
 <tr> 
 <td> <code>void</code>&nbsp;<code>addEntry(</code><code>int</code>&nbsp;<code>hash, K key, V value, </code><code>int</code>&nbsp;<code>bucketIndex) { </code> <code>　　　　</code><code>//1、判断当前个数是否大于等于阈值</code> <code>　　　　</code><code>//2、当前存放是否发生哈希碰撞</code> <code>　　　　</code><code>//如果上面两个条件否发生，那么就扩容</code> <code>　　　　</code><code>if</code>&nbsp;<code>((size &gt;= threshold) &amp;&amp; (</code><code>null</code>&nbsp;<code>!= table[bucketIndex])) { </code> <code>　　　　　　</code><code>//扩容，并且把原来数组中的元素重新放到新数组中</code> <code>　　　　　　resize(</code><code>2</code>&nbsp;<code>* table.length);</code> <code>　　　　　　hash = (</code><code>null</code>&nbsp;<code>!= key) ? hash(key) : </code><code>0</code><code>;</code> <code>　　　　　　bucketIndex = indexFor(hash, table.length);</code> <code>　　　　}</code> &nbsp; <code>　　　　createEntry(hash, key, value, bucketIndex);</code> <code>　　}</code> </td> 
 </tr> 
 </tbody> 
</table>

如果需要扩容，调用扩容的方法resize()

<table> 
 <tbody> 
 <tr> 
 <td> <code>void</code>&nbsp;<code>resize(</code><code>int</code>&nbsp;<code>newCapacity) { </code> <code>　　　　Entry[] oldTable = table;</code> <code>　　　　</code><code>int</code>&nbsp;<code>oldCapacity = oldTable.length;</code> <code>　　　　</code><code>//判断是否有超出扩容的最大值，如果达到最大值则不进行扩容操作</code> <code>　　　　</code><code>if</code>&nbsp;<code>(oldCapacity == MAXIMUM_CAPACITY) { </code> <code>　　　　　　threshold = Integer.MAX_VALUE;</code> <code>　　　　　　</code><code>return</code><code>;</code> <code>　　　　}</code> &nbsp; <code>　　　　Entry[] newTable = </code><code>new</code>&nbsp;<code>Entry[newCapacity];</code> <code>　　　　</code><code>// transfer()方法把原数组中的值放到新数组中</code> <code>　　　　transfer(newTable, initHashSeedAsNeeded(newCapacity));</code> <code>　　　　</code><code>//设置hashmap扩容后为新的数组引用</code> <code>　　　　table = newTable;</code> <code>　　　　</code><code>//设置hashmap扩容新的阈值</code> <code>　　　　threshold = (</code><code>int</code><code>)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + </code><code>1</code><code>);</code> <code>　　}</code> </td> 
 </tr> 
 </tbody> 
</table>

transfer()在实际扩容时候把原来数组中的元素放入新的数组中

<table> 
 <tbody> 
 <tr> 
 <td> <code>void</code>&nbsp;<code>transfer(Entry[] newTable, </code><code>boolean</code>&nbsp;<code>rehash) { </code> <code>　　　　</code><code>int</code>&nbsp;<code>newCapacity = newTable.length;</code> <code>　　　　</code><code>for</code>&nbsp;<code>(Entry&lt;K,V&gt; e : table) { </code> <code>　　　　　　</code><code>while</code><code>(</code><code>null</code>&nbsp;<code>!= e) { </code> <code>　　　　　　　　Entry&lt;K,V&gt; next = e.next;</code> <code>　　　　　　　　</code><code>if</code>&nbsp;<code>(rehash) { </code> <code>　　　　　　　　　　e.hash = </code><code>null</code>&nbsp;<code>== e.key ? </code><code>0</code>&nbsp;<code>: hash(e.key);</code> <code>　　　　　　　　}</code> <code>　　　　　　　　</code><code>//通过key值的hash值和新数组的大小算出在当前数组中的存放位置</code> <code>　　　　　　　　</code><code>int</code>&nbsp;<code>i = indexFor(e.hash, newCapacity);</code> <code>　　　　　　　　e.next = newTable[i];</code> <code>　　　　　　　　newTable[i] = e;</code> <code>　　　　　　　　e = next;</code> <code>　　　　　　}</code> <code>　　　　}</code> <code>　　}</code> </td> 
 </tr> 
 </tbody> 
</table>

**三、总结：**

Hashmap的扩容需要满足两个条件：**当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。**

因为上面这两个条件，所以存在下面这些情况

（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

（2）、当然也有可能存储更多值（超多16个值，最多可以存26个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（这时元素个数小于阈值12，不会扩容），后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，所以不会扩容），前面11+15=26，所以在存入第27个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

注：jdk版本1.7