Java 中的 HashMap

发布时间：2023-04-17 12:22:26 所属栏目：教程来源：

导读：Java 中的 HashMap 作者：Grey 原文地址：Java 中的 HashMap 扩容机制 jdk1.7 先生成新数组。遍历老数组中的每个位置上的链表上的个元素。取个元素的key，并基于新

Java 中的 HashMap
作者：Grey

原文地址：

Java 中的 HashMap 作者：Grey 原文地址：Java 中的 HashMap 扩容机制 jdk1.7 先生成新数组。遍历老数组中的每个位置上的链表上的个元素。取个元素的key，并基于新

Java 中的 HashMap
作者：Grey

原文地址：Java 中的 HashMap

扩容机制
jdk1.7
先生成新数组。

遍历老数组中的每个位置上的链表上的个元素。

取个元素的key，并基于新数组长度，计算出每个元素在新数组中的下标。

将元素添加到新数组中去。

所有元转移完了之后，将新数组赋给HashMap对象的table属性。

jdk1.8
同样先生成新数组。

遍历老数组中的每个位置上的链表或红黑树。

如果是链表，则直接将表中的每个元索重新计算下标，并添加到新数组中去。

如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元索对应在新数组中的下标位置。

统计每个下标位置的元索个数。
如果该位下的元素个数超过了8，则生成一个新的红黑树，开将根节点添加到新数组的对应位置。
如果该位置下的元素个数没有超过8，那么则生成一个链表，开将链表头节点添加数组的对应位置。
所有元素转移完了之后，将新数组赋给HashMap对象的table属性。

为什么要使用红黑树
因为在hash冲突比较频繁的情况下，生成的链表长度会非常长，这样就会导致查询的效率会大大降低，为了解决链表过长，查询效率过低的问题，所以使用红黑树来优化，有一个阈值8，超过了这个阈值，就会使用红黑树。

jdk1.7中HashMap死循环问题
复现代码如下，注：以下代码需要指定jdk1.7为运行环境

import java.util.HashMap;
import java.util.Map;
public class HashMapMultiThread {
static Map<String, String> map = new HashMap<>();
public static class AddThread implements Runnable {
int start = 0;
public AddThread(int start) {
this.start = start;
}
@Override
public void run() {
for (int i = start; i < 100000; i += 2) {
map.put(Integer.toString(i), Integer.toBinaryString(i));
}
}
}
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(new HashMapMultiThread.AddThread(0));
Thread t2 = new Thread(new HashMapMultiThread.AddThread(1));
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println(map.size());
}
}
运行main方法，发现程序出现死循环，无法停止。这个问题出现在HashMap扩容操作调用的transfer方法中，

void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
假设HashMap当前状态如下

image

现在有两个线程A和线程B都要执行put操作，线程A和线程B都会看到上面图的状态快照

线程A执行到transfer函数中

Entry<K,V> next = e.next;
这行代码时，此时在线程A的栈中

e = 4节点
next = 5节点
假设此时线程B正在执行transfer函数中的while循环，即会把原来的table变成新一table（线程B自己的栈中），再写入到内存中。如下图（假设两个元素在新的hash函数下也会映射到同一个位置）

image

线程A继续执行（看到的仍是旧表），即从transfer代码

Entry<K,V> next = e.next;
处接着执行，当前的

e = 4号节点,
next = 5号节点

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!