java并发-HashMap并发环形链表详解-jdk1.7

比眉伴天荒 2022-05-22 11:28 64阅读 0赞

**1.      Jdk1.7的HashMap并发问题介绍**

我们都知道，在并发使用HashMap会造成线程不安全的情况，这种不安全不仅是数据丢失，而且可能在一定情况下出现环形链表，导致数据无法插入。

**2.      原因1——并发时resize头插法**

此处分析参考http://www.importnew.com/22011.html

我们都知道，HashMap默认大小为16，超过threshold就会扩容2倍，下面是扩容方法。

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);
    }

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);  
\}  
  
  
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;  
\}  
    \}  
\}

在单线程情况下，扩容调用transfer方法，会执行头部插入法：

e.next = newTable\[i\];

newTable\[i\] = e;

将原链表1->2->3倒叙插入到新扩容链表3->2->1（如果在扩容后还存在于table相同下标的链表中）。

例如下面这个例子。假设hash算法就是最简单的 key mod table.length（也就是数组的长度）。

同时可以发现在Entry中的next是普通类型，也就是说整个链表不具有内存可见性。

1)       单线程

最上面的是old hash 表，其中的Hash表的 size = 2, 所以 key = 3, 7, 5，在 mod 2以后碰撞发生在table\[1\]；

接下来的三个步骤是 Hash表 resize 到4，并将所有的 <key,value> 重新rehash到新 Hash 表的过程。如图所示：

[![java并发-16-HashMap并发环形链表详解-jdk1.7][java_-16-HashMap_-jdk1.7]][java_-16-HashMap_-jdk1.7_java_-16-HashMap_-jdk1.7]

2)       并发

假设有两个线程执行了put()并准备扩容，执行到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;  
\}  
    \}  
\}

线程1在Entry<K,V> next = e.next后挂起，线程2正常完成了扩容，结果如下：

[![java并发-16-HashMap并发环形链表详解-jdk1.7][java_-16-HashMap_-jdk1.7 1]][java_-16-HashMap_-jdk1.7_java_-16-HashMap_-jdk1.7 1]

此时线程1继续执行，此时e是3节点，next是7节点，而线程2中链表却被改为7->3->null，后面所说的环形链表正是由于线程1中内部存在的历史链表关系和实际链表关系的冲突导致，**此时Entry的next不是volatile类型，是否需要考虑内存可见性，除非线程2将链表节点引用立即刷到主存？**这个问题在原因2中会详细讨论。

下面继续执行线程1：

l  执行e.next=newTable\[i\]，此时线程1的newTable\[i\]是null。也就是说此时链表仍然为7->3->null。

l  执行newTable\[i\]=e，即此时newTable\[i\]=3->null

l  然后更新e=next为7节点。

接着开始重新循环：

l  Entry<K,V> next=e.next，此时next是3节点

l  执行e.next=newTable\[i\]，此时线程1的newTable\[i\]是3节点。也就是说此时链表仍然为7->3->null

l  执行newTable\[i\]=e，即此时newTable\[i\]=7->3->null

l  然后更新e=next为3节点。

接着开始重新循环：

l  Entry<K,V> next=e.next，此时next是null

l  执行e.next=newTable\[i\]，此时线程1的newTable\[i\]是7节点。也就是说此时链表变成环形链表3->7->3->7…

l  执行newTable\[i\]=e，即此时newTable\[i\]=3->7->3->7…

l  然后更新e=next为null。

[![java并发-16-HashMap并发环形链表详解-jdk1.7][java_-16-HashMap_-jdk1.7 2]][java_-16-HashMap_-jdk1.7_java_-16-HashMap_-jdk1.7 2]

此时仍然可以退出循环。

**3.      原因2:——循环链表产生的关键：内存可见性**

网上写1.7版本HashMap并发产生环形链表问题都没有考虑内存可见性，如果多线程情况下内存不可见，自然也不会有环形链表问题。

**【关键问题】此时Entry的next不是volatile类型，是否需要考虑内存可见性，除非线程2将链表节点引用立即刷到主存？**

答：是的，需要考虑内存可见性。HashMap中没有定义volatile变量，无法保证多线程情况下内存可见性，所以理论上来说，线程1中本地缓存的链表就是3->7->5，线程2虽然修改了链表关系7->3->null，但仍在其本地缓存没有刷新到主存，或即使刷新到主存，线程1在后续执行过程中没有重新读取主存。

所以如果没有其他强迫线程1读取主存操作，线程1就会按照自己缓存的链表3->7->5执行transfer，最终会向线程2执行结果一样。但线程1在循环时的某些情况下执行了hash方法：

final int hash(Object k) {
    int h = hashSeed;
        if (0 != h && k instanceof String) {
    return sun.misc.Hashing.stringHash32((String) k);
    }
    
        h ^= k.hashCode();
    
    // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
    h ^= (h >>>20) ^ (h >>>12);
        return h ^ (h >>>7) ^ (h >>>4);
    }

hash方法调用了sun.misc.Hashing.stringHash32地方方法，该方法强迫线程1重读主存，所以此时如果线程2没有将本地缓存写入主存，那么会先将自己的缓存写入主存，然后线程1进而读取更新了主存（类似MESI协议）。

这样，线程1内的链表结构就变得和线程2（主存）一致，从而导致了环形链表的出现。

本人回复于CSDN：https://blog.csdn.net/zhuqiuhui/article/details/51849692

下面是一个测试用例，可以发现调用了sun.misc.Hashing.stringHash32方法时能够输出“执行结束”，即线程读取了最新主存。

public class TestMain {
    static MyObject myObject;
    
        public static void main(String[] args){
            System.out.println(DateFormatUtils.format(new Date(),"yyyy-MM-dd HH:mm:ss"));
    testVolatileObject();
    }
    public static void testVolatileObject() {
    int i = 0;
    MyObject objectFalse = new MyObject();
    MyObject objectFalseNext = new MyObject();
    objectFalse.setNext(objectFalseNext);
    
    MyObject objectTrue = new MyObject(true);
    MyObject objectTrueNext = new MyObject(true);
    objectTrue.setNext(objectTrueNext);
    myObject = objectFalse;
            final int a = 0;
    Thread backgroundThread = new Thread(new Runnable() {
    public void run() {
                    System.out.println("执行ing");
                    int i = 0;
                    while (!myObject.next.getFlag()){
                        i = i + 1 + a;
    sun.misc.Hashing.stringHash32((String) "12");
    //这段System.out语句会导致线程结束，原因？ //                    System.out.println(i); }
                    System.out.println("执行结束");
    }
            });
    
    backgroundThread.start();
    System.out.println("开始执行");
            try {
                Thread.sleep(1000);
    myObject.next = objectTrueNext;
    Thread.sleep(2000);
    System.out.println("完成");
    } catch (InterruptedException e) {
                e.printStackTrace();
    }
        }
    
    private static class MyObject {
    boolean flag;
            public MyObject() {
    flag = false;
    }
    
    public MyObject(boolean flag) {
    this.flag = flag;
    }
    public boolean getFlag() {
    return flag;
    }
            MyObject next;
            public void setNext(MyObject next) {
    this.next = next;
    }
    public MyObject getNext() {
    return next;
    }
        }
    }

参考文献

\[1\] http://www.importnew.com/22011.html

[java_-16-HashMap_-jdk1.7]: http://s11.sinaimg.cn/mw690/002i2qf8zy7jRxGhi6m8a&690
[java_-16-HashMap_-jdk1.7_java_-16-HashMap_-jdk1.7]: /images/20220522/c5a4fcea986d42768585350e23ae27b2.png
[java_-16-HashMap_-jdk1.7 1]: http://s16.sinaimg.cn/mw690/002i2qf8zy7jRxGZ2GPbf&690
[java_-16-HashMap_-jdk1.7_java_-16-HashMap_-jdk1.7 1]: /images/20220522/8c977212b7ed4a98a2ea273fdd4d2325.png
[java_-16-HashMap_-jdk1.7 2]: http://s5.sinaimg.cn/mw690/002i2qf8zy7jRxHLsbO24&690
[java_-16-HashMap_-jdk1.7_java_-16-HashMap_-jdk1.7 2]: /images/20220522/c262ceefa79c4a27b8c27050625ddb66.png