一直都知道 HashMap 是非线程安全的, 但是也没有去深究过在多线程情况下会存在怎样的问题, 偶然听说在高并发的情况下,HashMap极有可能会出现死循环的情况,耗尽CPU,所以就看了以下HashMap的实现,研究了下为何会出现死循环
对HashMap的操作,无外乎put和get操作.
get操作底层是由getEntity来处理的(具体实现如下),可以看到对需要获取的对象,是先计算其hash值,得到它可能出现的链表.然后循环链表中所有元素,进行判断, 在链表正常构建的情况下,这里应该是不会出现死循环的
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
而put操作的实现如下,会先查找当前的map中是否存在相同的key,若存在则直接替换value,并返回旧值.若不存在则会调用 addEntry() 向链表中放入一个新的元素.
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;
}
在 addEnty() 中, 若Map当前的元素个数已经超过了 临界值, 则会对整个Map执行扩容处理.
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);
}
在 resize() 中会调用 transfer() 将已有的元素,全部放入新table中.
在开头说的死循环的问题, 也就出现在了这个transfer中:
在这里会遍历旧table中的所有元素,然后将其放入新table中.
为了简化问题讨论,我们假设其中一个链表上有两个元素e1和e2,在链表中的顺序为: e1->e2->null, 并且这两个元素在重新hash的时候,在新表中也会在同一个链表上.
现在有两个线程同时走到了 这个方法中,线程一刚走到下面第五行(e=e1,next=e2), 线程一被挂起,线程二执行, 线程二全部执行完毕,此时的元素顺序为: e2->e1->null, 然后执行线程一(此时 e=e1,next=e2),
第一遍while执行完成后,新链表元素顺序为:e1->null.
第二遍while执行时,则 e=e2, next=e1(线程二已经将e2的next指向了e1).执行完成后,新链表顺序为:e2->e1->null.
第三遍while执行时(e=e1,next=null),执行完成后, 新链表的顺序为 e1->e2->e1 (即 e1.next=e2 且 e2.next=e1), 则形成了 环型链.
再回到最开始的get方法的实现处,可以发现等下一次有线程调用get方法时, 一旦进入这个环型链,就再也出不来了.
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;
}
}
}