猿们都知道，hashmap是非线程安全的集合类，在jdk1.7中并发情况下还有可能出现因死循环导致cpu飙升，下面来扒一扒原因。
注：基于jdk1.7
简述hashmap结构
数组 + 单链表
hashmap的每个元素的key会生成一个hash值，然后根据这个hash值计算一个在数组中的位置下标indexFor。index不同的元素放在数组的不同位置，index相同的元素会以链表形式存放，最新的数据会放在链表的头部。
image.png
下面看看死循环是如何发生的
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//获取key的hash值
int hash = hash(key);
//计算数组下标
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果在同一个下标，并且key相同，进行值覆盖
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;
}
// 先扩容后添加元素
void addEntry(int hash, K key, V value, int bucketIndex) {
//size是否大于阈值，并且该下标不为空，则进行扩容
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);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//可以看出是头插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
//扩容
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];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
//这个方法就是出现问题的地方
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//遍历条件
while(null != e) {
//next临时变量，留在后面赋值以支持迭代
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//newTable[i]相当于上次迭代的形成的链表头结点
//相当于把上次迭代的形成的链表接到e后面，反过来讲就是e插到链表头
e.next = newTable[i];
//将本次迭代的e元素链接到数组位置，完成头插新链表替换
newTable[i] = e;
//next临时变量赋值给下次迭代
e = next;
}
}
}
举个并发put时的栗子
1.假设当前结构如下，现在两个线程并发插入一个新元素，并会引起扩容
image.png
2.线程a
while(null != e) {
//线程a执行完这行后挂起，
// e=key:3,e.next=key:7, next=key:7
Entry<K,V> next = e.next;
...
}
此刻线程a创建的newTable为一个空数组
2.线程b比较顺利的执行完整个transfer，newTable如下，
注意 该下标的链表元素和扩容前顺序反了，头插法
image.png
3.接着线程a继续执行，第一遍循环
while(null != e) {
//e=key:3,e.next=key:7, next=key:7
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 = null,此时a的newTable[i]为空
e.next = newTable[i];
//newTable[i] = key:3
newTable[i] = e;
//e=key:7
e = next;
}
第一遍循环完得到如下:
image.png
4.接着线程a继续执行，第二遍循环
while(null != e) {
//e=key:7,e.next=key:3, next=key:3
//注意这里为何e.next=key:3，，回想线程a的结果链表，
//hashmap之所以不安全，entry时公共资源
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 = key:3,a的newTable[i]头节点key:3
e.next = newTable[i];
//newTable[i] = key:7
newTable[i] = e;
//e=key:3
e = next;
}
第二遍循环完后，如下
image.png
5.此刻，while(null != e)还未结束，接着线程a继续执行，第三遍循环
while(null != e) {
//e=key:3,e.next=null, next=null
//key:3节点next为空
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 = key:7,a的newTable[i]即头节点key:7
e.next = newTable[i];
//newTable[i] = key:3，a的newTable[i]即头节点key:3-key:7-key:3
newTable[i] = e;
//e=null,结束遍历
e = next;
}
image.png
