HashMap在并发编程环境下有什么问题啊?
代码回顾
1.7 的时候，HashMap 在多并发环境下，多线程扩容，有可能引起的死循环问题：
如1.7 的时候，HashMap的底层是由数组加链表来实现的，如下所示：
jdk7-HashMap 数据结构.png
当往HashMap中put一个键值对时：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
方法addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
当达到扩容条件为 if ((size >= threshold) && (null != table[bucketIndex])) 成立时，会发生 resize(2 * table.length); 扩容。
比如 table的初始容量为8,加载因子为0.75,此时阈值为6，table已有三个元素，现在put一个元素 Entry8 , Entry8 被散列到table[5]处，而table[5] != null,此时满足扩容条件.
jdk7 HashMap 数据结构插入扩容.png
扩容时先生成一个是table大小2倍的newTable，然后把table中的元素迁移到newTable中
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
迁移的工作就由 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的初始容量为4，先往HashMap中依次put三个元素<5,”B”>、<9,”C”>、<1,”A”>，它们都被散列到table[1]处，形成了链
模拟扩容前.png
假设一个HashMap已经到了Resize的临界点。此时有两个线程Thread1和Thread2，在同一时刻对HashMap进行Put操作：
模拟扩容前插入.png
此时达到Resize条件，两个线程各自进行resize的第一步，也就是扩容：
模拟同时扩容.png
此时， 这时候，两个线程都走到了rehash的步骤。假设线程1执行完 transfer 方法中的 Entry<K,V> next = e.next 语句后时间片用完，挂起
线程1挂起.png
此时，线程1内的 e 指向 <1,“A”>，next指向<9,”C”> ，如下图所示：
线程1挂起状态.png
线程2 生成完newTable后用transfer方法进行迁移，执行完后与线程1一样，e指向<1,”A”>,next指向<9,”C”>
线程2第一次循环状态.png
线程2 然后继续执行循环体下面的语句
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 = <1,A>
// 下面的语句会把运行时的变量的值填进去
//注意: <1,A> 代表了指向 <1,A>的引用，就是此e的值
e.next = newTable[i];
// <1,A>.next = newTable[1];
newTable[i] = e;
// newTable[1] = <1,A>;
e = next;
// <1,A> = <9,C>;
// 此时e的指针指向了<9,C>
}
}
线程2执行完之后为下图 ：
线程2执行完第一次循环状态.png
然后线程2按照同样的逻辑进行第二次循环（while循环），下图是第二遍循环后的结果 ：
线程2执行完第二次循环状态.png
然后线程2按照同样的逻辑进行第三遍循环，执行后的结果 ：
线程2执行完第三次循环状态.png
此时，线程2时间片用完，线程1得到时间片，开始执行 :
线程1继续执行.png
注意，此时线程1的e指向<1,A>,next指向<9,C>,在线程2操作链表的时候，线程1 中的e,next指向的元素没变(一直是红色的e和next)
线程2时间片用完.png
线程一和线程二整体图为：
线程1重新开始整体图.png
然后线程1开始执行循环内剩下的代码 ：
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 = <1,A>
// 下面的语句会把运行时的变量的值填进去
//注意: <1,A> 代表了指向 <1,A>的引用，就是此e的值
e.next = newTable[i];
// <1,A>.next = newTable[1];
newTable[i] = e;
// newTable[1] = <1,A>;
e = next;
// <1,A> = <9,C>;
// 此时e的指针指向了<9,C>
}
}
线程1执行完之后为下图 ：
线程1执行第一次循环.png
线程1继续执行第二遍循环 :
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;
// next = <1,A>
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 此时 e = <9,C>
e.next = newTable[i];
// <9,C>.next = newTable[1];
newTable[i] = e;
// newTable[1] = <9,C>;
e = next;
// <9,C> = <1,A>;
// 此时e的指针指向了<1,A>
}
}
执行完之后如下图所示：
线程1执行第二次循环.png
线程1继续第三遍循环（注意：此次循环会形成环）：
先执行
线程1执行第3-1次循环.png
然后执行
线程1执行第3-2次循环.png
此时环已经形成
然后执行剩余的两行代码
newTable[i] = e;
// newTable[1] = <1,A>;
e = next;
// e = null;
执行完，e 为 null,退出循环
线程1执行第3-3次循环.png
死循环的发生
当形成环后,当往HashMap中put元素的时候，这个元素恰巧落在了table[1]（不管有没有更新table），而这个元素的Key不在table[1]这条链上，此时会发生死循环
put死循环.png
或者在get元素的时候，该元素恰巧落在table[1]上，并且该元素的Key不在该链上，会发生死循环 ：
get死循环.png
死循环是这样形成的， 核心就是线程2修改了原来的链表结构，而线程1却以原来的逻辑执行迁移 。
jdk1.8 会产生死循环么？
JDK 8 用 head 和 tail 来保证链表的顺序和之前一样； 并且采用尾插法，避免了这种死循环的产生， 但是还会有数据丢失等弊端（并发本身的问题）。
那并发下我还想使用散列表这种数据结构怎么办呢 ？
多线程情况下还是建议使用 ConcurrentHashMap，锁的粒度较小，较HashTable或者 Collections.synchronizedMap() 性能要好一些 。
网友评论