HashMap的reHash多线程循环链表

HashMap put()元素时会扩容，生成一个newTable存储元素

   /** 
    * 
    * 往表中添加元素，如果插入元素之后，表长度不够，便会调用resize方法扩容 
    */  
   void addEntry(int hash, K key, V value, int bucketIndex) {  
       Entry<K,V> e = table[bucketIndex];  
       table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
       if (size++ >= threshold)  
           resize(2 * table.length);  
   }  
  
   /** 
    * resize()方法如下，重要的是transfer方法，把旧表中的元素添加到新表中
    */  
   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);  
       table = newTable;  
       threshold = (int)(newCapacity * loadFactor);  
   }

    /**
     * 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) {
                // 重点。线程A执行到这一步时间片用完挂起
                // 设置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.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }

• 假设hash算法是key mod size (key%size)。
• old 表的size=2，key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。

• 单线程下ReHash，resize 变成4，如图

  
  image.png

并发下的ReHash

1. 线程T一 在执行完 Entry<K,V> next = e.next; 这一步后挂起。

2. 此时e = 3；next = 7；

3. 线程T二开始执行并完成整个ReHash的过程，并把oldTable = newTable（最主要的一点，线程T二完成了oldTable的偷梁换柱）;

   
   image.png

4. 线程T一获得时间片重新执行；

5. 此时第一次while循环正式开始；

6. e指向了newTable的3，next指向了newTable的7；

   
   image.png