[toc]
注：JDK1.8之后进行了优化，多线程不会造成死循环问题，但依旧线程不安全，容易造成数据丢失，多线程推荐使用ConcurrentHashMap

原因分析

在了解来龙去脉之前先看HashMap的数据结构
在内部HashMap使用一个Entry数组保存key、value数据，当一对key、value被加入时，会通过一个hash算法得到数组下表index，算法很简单，根据key的hash值，对数组的大小取模hash&(length-1)，并把结果结果插入数组该位置，如果该位置上已经有元素了，就说明hash冲突，这样index位置生成链表。
如果存在hash冲突，最惨情况，就是所有元素定位在同一个位置，形成一个长长链表，这样get值时，最坏的情况需要遍历所有节点，性能变成了O(n)，所以元素的hash值算法和HashMap的初始大小很重要。
当插入一个新节点时，如果不存在相同的key，会判断当前内部元素是否达到阈值(默认是数组大小的0.75)，如果达到这个阈值，会对数组进行扩容，也会对链表中元素进行rehash。

jdk1.7的put方法实现

判断key是否存在

public V put(K key,V value){
    if(key == null){
        return putForNullKey(value);
    }    
    int hash = hash(key.hashCode());
    int i = indexFor(hash,table.length);
    // 如果key已经存在，则替换value，并返回旧值
    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++;
    //key不存在，则插入新的元素
    addEntry(hash,key,value,i);
    return null;
}

检查容量是否达到阈值

void addEntry(int hash,K key,V value,int bucketIndex){
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash,key,value,e);
    //检查是否达到扩容阈值
    if(size++ >= threshold){
        resize(2 * table.lengeth);
    }
}
//Entry的构造方法：
Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
}

扩容的实现

void resize(int newCapacity){
    Entry[] oldTable=table;
    int oldCapaicty=oldTable.length;
    if(oldCapaicty == MAXIMUM_CAPACITY){
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable=new Entry[newCapacity];
    transfer(newTable);
   table = newTable;
   threshold = (int)(newCapacity * loadFactor);
}

transfer方法移动元素

void transfer(Entry[] newTable){
    Entry[]src=table;
    int newCapacity=newTable.length;
    for(int j=0;j<src.length;j++){
        Entry<K,V> e=src[j];
        if(e!=null){
            src[j]=null;
            do{
                Entry<K,V> next=e.next;
               int i=indexfor(e.hash,newCapacity);
               e.next=newTable[i];
               newTable[i]=e;
               e=next; 
            }while(e!=null);
        }
    }
}

移动逻辑很清晰，遍历原来table中每一个位置的链表，并对每一个元素进行重新hash，在新的newTable找到归宿，并插入。

案例分析

假设HahsMap初始化大小为4，插入3个节点，不巧的是，这三个节点都hash到同一个位置，如果按照默认的负载因子，插入第三个节点就会扩容，为了验证效果，假设负载因子是1。

image

插入第四个节点时，发生rehash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会创建新的数组

image

假设线程2在执行到Entry<K,V> next=e.next;之后CPU时间片用完了，这变量e指向节点a。变量next指向节点b；
线程1继续执行，很不巧a，b，c节点rehash之后又在同一位置7，开始移动节点
- 第一步移动节点a，如图
  
  image
- 第二步移动节点b
  
  image
- 注意，这里的顺序是反过来的继续移动节点c
  
  image
这个时候线程1时间片用完，内部的table还没有设置成新的newTabel，线程2开始执行，这时内部引用关系如下：

image
这时，线程2中变量e指向节点a，变量next指向节点b，开始执行循环体的剩余逻辑。

Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;

执行后的引用关系如下图：

image
执行后e的指向节点b，因为e不是null，则继续执行循环体，执行后的引用关系：

image

变量e又重新指向了节点a，只能继续执行循环体，这里仔细分析一下：
- 执行完Entry<K,V>next=e.next；目前节点a没有next，所以next指向null。
- e.next=newTable[i]；其中newTable[i]执行节点b，那就是把a的next指向了节点b，这样a和b互相引用了，形成一个环；
- nnewTable[i]=e把节点a放在了数组i的位置；
- e=next；把变量e赋值为null。因为第一步中变量next就是指向了null，所以最终引用关系是时这样的：
  
  image
节点a和b互相引用，形成一个环，当在数组该位置get寻找对应的key时，就会发生死循环。另外如果线程2把newTable设置成内部table，节点c的数据就丢了，所以还存在数据丢失问题。

总结

并发情况下，发生扩容，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免并发环境使用HashMap，如果多线程就用ConcurrentHashMap。

jdk 1.7 HashMap死循环问题

jdk 1.7 HashMap死循环问题

原因分析

jdk1.7的put方法实现

案例分析

总结