HashMap高频面试题，让你掌握青铜回答与王者级回答，你值得拥有

骑猪看日落 2024-02-20 08:50 35阅读 0赞

《HashMap高频面试题，让你掌握青铜回答与王者级回答，你值得拥有》

![format_png][]

HashMap的实现原理是什么？

HashMap是一个高频的面试题，那么如何才能回答的比较合适呢？

## 一、青铜级 ##

以下是jdk1.7与jdk1.8中hashmap的区别：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th><strong>JDK1.7</strong></th> 
   <th><strong>JDK1.8</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>存储</td> 
   <td>数组+链表</td> 
   <td>数组+链表+红黑树</td> 
  </tr> 
  <tr> 
   <td>链表超过8</td> 
   <td>链表</td> 
   <td>红黑对(链表超过8且数组长度超64)</td> 
  </tr> 
  <tr> 
   <td>节点结构</td> 
   <td>Entry&lt;K,V&gt; implements Map.Entry&lt;K,V&gt;</td> 
   <td>Node&lt;K,V&gt; implements Map.Entry&lt;K,V&gt;</td> 
  </tr> 
  <tr> 
   <td>插法</td> 
   <td>头插法(扩容环化造成死循环)</td> 
   <td>尾插法</td> 
  </tr> 
 </tbody> 
</table>

![format_png 1][]

概括下可以从以下几个方面来回答：

### 1、基本原理 ###

HashMap是一个基于Hash散列技术，以键值对形式存储的数据结构。

### 2、数据存储 ###

JDK 1.8 之前的 HashMap 使用的数组+链表的结构，插入时使用头插法。

JDK 1.8 之后的 HashMap 使用的数组+链表/红黑树的结构，插入时使用头插法。

### 3、哈希冲突 ###

JDK 1.8 之前的 HashMap 使用的是拉链法（Chaining）作为冲突解决策略。

JDK 1.8 引入了红黑树作为替代链表的冲突解决策略。

### 4、扩容和负载因子 ###

当哈希表中的元素数量超过一定阈值时，HashMap 会自动进行扩容，以保持较低的负载因子，从而提高性能。

## 二、王者级 ##

可以从以下几个方面来回答：

### 1、基本原理 ###

HashMap是一个基于Hash散列技术，以键值对形式存储的数据结构。

### 2、数据存储 ###

HashMap内部维护一个数组，这个数组的每个位置都是一个链表或红黑树的头节点。这些节点用于存储键值对。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>jdk1.8之前</th> 
   <th>jdk1.8之后(含1.8)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>结构</td> 
   <td>数组+链表</td> 
   <td>数组+链表/红黑树</td> 
  </tr> 
  <tr> 
   <td>数组类型</td> 
   <td>Entry数组</td> 
   <td>Node数组</td> 
  </tr> 
 </tbody> 
</table>

#### 2.1、JDK1.8之前 ####

![format_png 2][]

JDK1.8之前的 HashMap 由 Entry 数组组成，Entry 类是 HashMap 中存储键值对的类。Entry 类包含 key、value 和 next 三个属性。key 是键，value 是值，next 是指向下一个 Entry 对象的指针，出现 hash 冲突存放到链表中。具体源码是通过 put() 方法实现的。

**put() 方法的实现如下：**

ini

复制代码

`public V put(K key, V value) { // 如果哈希表为空，则对其进行申请数组空间 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 如果 key 为 null，则将其放入 null 键的特殊位置 if (key == null) { return putForNullKey(value); } // 计算 key 的哈希值 int hash = hash(key); // 根据哈希值和哈希表的长度计算索引位置 int i = indexFor(hash, table.length); // 遍历索引位置上的链表，寻找 key for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 如果 key 相同，则更新 value 并返回旧值 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果 key 不存在，则添加一个新的链表成员 modCount++; addEntry(hash, key, value, i); return null; }`

put() 方法首先计算 key 的 hash 值，然后定位到数组索引位置。如果数组索引位置上已经存在 Entry 对象，则判断 key 是否相同。如果相同则直接覆盖value，否则添加到链表中。如果数组索引位置上不存在 Entry 对象，则直接添加到数组中。

**链表的具体实现如下：**

typescript

复制代码

`static class Entry<K, V> implements Map.Entry<K, V> { final int hash; final K key; V value; Entry<K, V> next; Entry(int hash, K key, V value) { this.hash = hash; this.key = key; this.value = value; } @Override public K getKey() { return key; } @Override public V getValue() { return value; } @Override public V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Entry<?, ?> entry = (Entry<?, ?>) o; return hash == entry.hash && Objects.equals(key, entry.key) && Objects.equals(value, entry.value); } @Override public int hashCode() { return Objects.hash(hash, key, value); } @Override public String toString() { return key + "=" + value; } }`

链表的每个元素是一个 Entry 对象，Entry 对象包含 key、value、hash 和 next 四个属性。key 是键，value 是值，hash 是 key 的 hash 值，next 是指向下一个 Entry 对象的指针。

当 HashMap 出现 hash 冲突时，会将新的 Entry 对象添加到链表的尾部。链表的查询性能较差，当链表长度过长时，会影响 HashMap 的查询性能。

![format_png 3][]

**源代码中有几处关键的地方：**

*  **关键一：**

![format_png 4][]

先通过indexFor下标定位到的数组元素位置，再遍历这个元素(链表)，依次和链表中的key比较，如果 key 相同就直接覆盖，不同就采用头插法插入元素。

*  **关键二:**

头插法的实现主要涉及到两个方法：addEntry 和 createEntry。addEntry 方法用于判断是否需要扩容，并调用 createEntry 方法将键值对存入数组中。createEntry 方法用于创建一个新的节点，并将其 next 属性指向原来的链表头节点，然后将新节点赋值给数组对应位置，完成头插法。

![format_png 5][]

![format_png 6][]

插入元素使用createEntry，新元素会的next指向table\[bucketIndex\]也就是链表的头节点。

#### 2.2、JDK1.8之后(含1.8) ####

![format_png 7][]

JDK1.8的 HashMap 由 Node 数组组成，Node 类是 HashMap 中存储键值对的类。Node 类包含 key、value、hash、next 和 prev 五个属性。key 是键，value 是值，hash 是 key 的 hash 值，next 是指向下一个 Node 对象的指针，prev 是指向前一个 Node 对象的指针。  
JDK1.8之后的 HashMap 由 Node 数组组成，出现 hash 冲突存放到链表中同时满足条件的情况下会生成红黑树。具体源码是通过 put() 方法实现的。

put() 方法的实现如下：

ini

复制代码

`public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // 获取哈希表 Node<K,V>[] tab = table; // 如果哈希表为空或长度为0，则进行扩容 if (tab == null || tab.length == 0) { tab = resize(); } // 计算索引位置 int n = tab.length; int i = (n - 1) & hash; // 如果索引位置上的节点为空，则添加一个新的节点 Node<K,V> p = tab[i]; if (p == null) { tab[i] = newNode(hash, key, value, null); } else { // 如果索引位置上的节点存在，则遍历链表，寻找 key 相同的节点 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { e = p; } else if (p instanceof TreeNode) { // 如果索引位置上的节点是红黑树节点，则调用红黑树的 putTreeVal() 方法添加新的节点 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); } else { // 如果索引位置上的节点是链表节点，则遍历链表，寻找 key 相同的节点 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 如果没有找到 key 相同的节点，则在链表尾部添加一个新的节点 p.next = newNode(hash, key, value, null); // 如果链表长度超过阈值，则将链表转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); } break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { // 如果找到 key 相同的节点，则停止遍历 break; } p = e; } } if (e != null) { // 找到 key 相同的节点 // 获取旧值 V oldValue = e.value; // 如果只有 key 不存在才添加新的节点，则仅当旧值为 null 时才更新值 if (!onlyIfAbsent || oldValue == null) { e.value = value; } // 调用 afterNodeAccess() 方法更新节点的访问时间 afterNodeAccess(e); return oldValue; } } // 添加新的节点后，更新 HashMap 的大小和修改次数 ++modCount; if (++size > threshold) { resize(); } // 调用 afterNodeInsertion() 方法更新节点的插入状态 afterNodeInsertion(evict); return null; }`

put() 方法在添加元素时，会先判断数组索引位置上是否已经存在 Node 对象。如果已经存在，则判断 key 是否相同。如果相同则更新 value，否则添加到链表中。

如果链表长度超过阈值，则将链表转换为红黑树。阈值的默认值是 8。

treeifyBin() 方法的实现如下：

ini

复制代码

`final void treeifyBin(Node<K,V>[] tab, int hash) { // 如果哈希表为空或长度小于 MIN_TREEIFY_CAPACITY，则进行扩容 int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { resize(); } else if ((e = tab[index = (n - 1) & hash]) != null) { // 获取索引位置上的节点 TreeNode<K,V> hd = null, tl = null; // 遍历链表，将每个节点转换为红黑树节点 do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) { hd = p; } else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); // 将转换后的红黑树节点添加到哈希表中 if ((tab[index] = hd) != null) { hd.treeify(tab); } } }`

treeifyBin() 方法首先判断链表的长度是否超过阈值。如果超过阈值，则将链表的第一个元素作为红黑树的根节点。

然后，将链表中的所有元素添加到红黑树中。

最后，将红黑树的根节点添加到数组中。

这样，当 HashMap 出现 hash 冲突存放到链表中同时满足条件的情况下，会将链表转换为红黑树，提高查询性能。

![format_png 8][]

**源代码中有几处关键的地方：**

*  **关键一：**

当链表的节点数量达到阈值(默认为 8 )，执行 treeifyBin 方法

![format_png 9][]

*  **关键二：**

进入treeifyBin方法后还有一个逻辑就是当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是对数组扩容。所以链表长度大于阈值不是转为红黑树的唯一条件。

![format_png 10][]

*  **关键三：**

区别于jdk1.7，jdk1.8已经使用了尾插法实现链表元素的插入。

![format_png 11][]

**问题：为什么jdk1.8后改为尾插法？**

主要是因为头插法在多线程扩容情况下会引起链表环。那什么是链表环呢？

线程1，第一节点为A，第二节点为B后面就没有了，遍历过程为A->B然后B没有后面节点即遍历结束。

这时线程1挂起。线程2引发扩容，扩容后为B->A。这时线程1遍历就会发现A的下一节点是B，会发现遍历B时B还有后续的节点为A，这样就出样链表环了。

![format_png 12][]

#### 2.3、Node 与Entry区别 ####

在 Java 的 HashMap 中，Node 和 Entry 都是用于表示键值对的数据结构，但它们在不同版本的 HashMap 中有一些区别：

**1）Node：**

*  Node 是在 JDK 1.8 之后的版本中引入的，用于存储键值对。
 *  Node 主要用于存储在哈希冲突的情况下，将键值对以链表或红黑树的方式组织起来的数据结构。
 *  Node 是 TreeNode 和 LinkedNode 的父类，这两个子类分别用于表示红黑树节点和链表节点。
 *  Node 中包含了键、值、哈希码、下一个节点引用等信息。

**2）Entry：**

*  Entry 是在 JDK 1.7 及之前的版本中用于存储键值对的数据结构。
 *  Entry 是 HashMap 内部的静态内部类，用于表示键值对。
 *  Entry 主要用于存储在哈希冲突的情况下，将键值对以链表的方式组织起来的数据结构。
 *  Entry 中包含了键、值、下一个 Entry 的引用等信息。

Node 和 Entry 都用于表示键值对，但它们的命名和实现方式在不同的 Java 版本中有所不同。Node 主要用于 JDK 1.8 及之后的 HashMap，而 Entry 主要用于 JDK 1.7 及之前的 HashMap。Node 进一步改进了哈希冲突的处理方式，引入了红黑树来提高性能。

### 3、哈希冲突 ###

JDK 1.8 之前的 HashMap 使用的是拉链法（Chaining）作为冲突解决策略。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。以下就是JDK1.7中的hashcode扰动函数。

![format_png 13][]

JDK 1.8 中，HashMap 使用了拉链法和红黑树两种冲突解决策略。当链表长度超过一定阈值时，会将链表转换为红黑树。红黑树是一种自平衡二叉树，具有较高的查询性能。以下就是JDK1.8中的hashcode扰动函数。

![format_png 14][]

JDK1.8 中的 HashMap 在查询性能上比 JDK1.7 中的 HashMap 有一定的提升。

以下是 JDK1.7 和 JDK1.8 中 HashMap 解决哈希冲突方法的具体对比：

<table> 
 <thead> 
  <tr> 
   <th>方面</th> 
   <th>JDK1.7</th> 
   <th>JDK1.8</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冲突解决策略</td> 
   <td>链表</td> 
   <td>链表 + 红黑树</td> 
  </tr> 
  <tr> 
   <td>优点</td> 
   <td>实现简单，查询性能较好</td> 
   <td>兼顾查询性能和插入性能</td> 
  </tr> 
  <tr> 
   <td>缺点</td> 
   <td>当链表过长时，查询性能会下降</td> 
   <td>实现比较复杂</td> 
  </tr> 
  <tr> 
   <td>适用场景</td> 
   <td>键值对数量较少，并且键值对的哈希值分布均匀</td> 
   <td>键值对数量较多，或者键值对的哈希值分布不均匀</td> 
  </tr> 
 </tbody> 
</table>

![format_png 15][]

JDK1.8 中的 HashMap 解决哈希冲突的方法更加灵活，可以适应不同的场景。

### 4、扩容和负载因子 ###

当哈希表中的元素数量超过一定阈值时，HashMap 会自动进行扩容，以保持较低的负载因子，从而提高性能。

Java HashMap 使用负载因子来控制扩容。负载因子是指 HashMap 中键值对数与 HashMap 容量的比值。

HashMap 的初始容量为 16，负载因子为 0.75。这意味着，当 HashMap 中键值对数达到 16 \* 0.75 = 12 时，HashMap 就会进行扩容。

HashMap 的扩容方式是将容量扩大为原来的 2 倍。例如，当 HashMap 的容量为 16 时，扩容后容量为 32。

HashMap 扩容的原因是，当 HashMap 的负载因子达到一定值时，HashMap 的查询性能会下降。这是因为，当 HashMap 的容量较小，并且键值对数较多时，会导致哈希冲突的概率增加。

因此，HashMap 会在负载因子达到一定值时进行扩容，以提高查询性能。

以下是 HashMap 扩容的具体步骤：

1.  创建一个新的 HashMap，容量为原来的 2 倍。
2.  将原 HashMap 中的所有键值对复制到新 HashMap 中。
3.  将原 HashMap 置为空。

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/b5c41674cb684ccf9ddb63e880727425.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/e38482ce126b4ef088f33ccf4a3eb3ce.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/991022123ab04be5a6890cd775acbcba.png
[format_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c9d06561a40c455aaa333c9f44077e3b.png
[format_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/0412a11367b6437bb131893fa5c7726a.png
[format_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a49104db6ecb4d85872f051e02487ab0.png
[format_png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/bd6dd9283b6a472fb9eb755e44b8c65c.png
[format_png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/4b0ca490c3924b8582c4461b83b0b9f9.png
[format_png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/82812743a8484a638f883ade5cb13865.png
[format_png 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/eb1c7ee5a55d4700a3ef8143518bbfc6.png
[format_png 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/79358a08ca21493a938ef31ebc468743.png
[format_png 11]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/7b45e5e8c43a4242a76fdab590ccb705.png
[format_png 12]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/7c59e170e8be493283fffe4cec1b063a.png
[format_png 13]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/d90465060bd5416e882d2b3b4fcc3e03.png
[format_png 14]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/dd8af670da23470a8f037ec5a371d9ca.png
[format_png 15]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/61b651615b3d42a5a257db6b797f1c99.png