Bagaimana untuk menyelesaikan masalah konkurensi berbilang benang HashMap Java

Simptom masalah konkurensi

Letak berbilang benang boleh membawa kepada gelung get yang tidak terhingga

Pada masa lalu, kod Java kami menggunakan HashMap atas sebab tertentu, tetapi program pada masa itu adalah satu benang , semuanya baik-baik saja. Kemudian, program kami mengalami masalah prestasi, jadi kami perlu menjadi multi-threaded, kami pergi ke dalam talian dan mendapati bahawa program ini sering menduduki 100% daripada CPU dan anda akan mendapati bahawa semua program digantung dalam HashMap Kaedah .get() telah dipasang dan masalah itu hilang selepas memulakan semula program. Tetapi ia akan datang lagi selepas beberapa ketika. Selain itu, masalah ini mungkin sukar untuk dihasilkan semula dalam persekitaran ujian.

Jika kita hanya melihat kod kita sendiri, kita tahu bahawa HashMap dikendalikan oleh berbilang urutan. Dokumentasi Java mengatakan bahawa HashMap tidak selamat untuk benang dan ConcurrentHashMap harus digunakan. Tetapi di sini kita boleh mengkaji sebab-sebabnya. Kod ringkas adalah seperti berikut:

package com.king.hashmap;
import java.util.HashMap;
public class TestLock {
     private HashMap map = new HashMap();
     public TestLock() {
         Thread t1 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t1 over" );
             }
         };
         Thread t2 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t2 over" );
             }
         };
         Thread t3 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t3 over" );
             }
         };
         Thread t4 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t4 over" );
             }
         };
         Thread t5 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t5 over" );
             }
         };
         Thread t6 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t6 over" );
             }
         };
         Thread t7 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t7 over" );
             }
         };
         Thread t8 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t8 over" );
             }
         };
         Thread t9 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t9 over" );
             }
         };
         Thread t10 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t10 over" );
             }
         };
         t1.start();
         t2.start();
         t3.start();
         t4.start();
         t5.start();
         t6.start();
         t7.start();
         t8.start();
         t9.start();
         t10.start();
     }
     public static void main(String[] args) {
         new TestLock();
     }
}

ialah untuk memulakan 10 utas dan terus meletakkan/mendapatkan kandungan ke dalam HashMap yang tidak selamat untuk benang Kandungan put adalah sangat mudah, dan kunci serta nilainya ditambah daripada 0. Integer (kandungan put ini tidak dilakukan dengan baik, sehingga kemudiannya mengganggu idea saya untuk menganalisis masalah). Apabila melakukan operasi tulis serentak pada HashMap, saya fikir ia hanya akan menghasilkan data kotor Walau bagaimanapun, jika saya menjalankan program ini berulang kali, utas t1 dan t2 akan digantung. , kadangkala kesemua 10 utas akan digantung.

Punca gelung tak terhingga ini terletak pada pengendalian pembolehubah kongsi yang tidak dilindungi - struktur data "HashMap". Selepas menambah "disegerakkan" pada semua kaedah operasi, semuanya kembali normal. Adakah ini pepijat jvm? Harus dikatakan tidak, fenomena ini telah lama dilaporkan. Jurutera matahari tidak menganggap ini adalah pepijat, tetapi mencadangkan bahawa "ConcurrentHashMap" harus digunakan dalam senario sedemikian

Penggunaan CPU yang berlebihan biasanya disebabkan oleh gelung yang tidak terhingga, menyebabkan beberapa utas terus berjalan sehingga masa cpu. Punca masalah ialah HashMap tidak selamat untuk benang Apabila berbilang benang diletakkan, ia menyebabkan gelung tak terhingga bagi Senarai kunci Masuk nilai kunci tertentu, dan masalah timbul.

Apabila urutan lain mendapat kunci gelung tak terhingga Senarai Kemasukan ini, get ini akan sentiasa dilaksanakan. Hasil akhirnya adalah lebih banyak benang dalam gelung tak terhingga, akhirnya menyebabkan pelayan ranap. Kami biasanya berpendapat bahawa apabila HashMap memasukkan nilai tertentu berulang kali, ia akan menimpa nilai sebelumnya. Ini betul. Walau bagaimanapun, untuk capaian berbilang benang, disebabkan oleh mekanisme pelaksanaan dalamannya (dalam persekitaran berbilang benang dan tanpa penyegerakan, operasi letak pada HashMap yang sama boleh menyebabkan dua atau lebih utas melakukan operasi rehash pada masa yang sama, yang boleh menyebabkan kepada jadual kekunci bulat muncul, apabila benang tidak boleh ditamatkan dan terus menduduki CPU, mengakibatkan penggunaan CPU yang tinggi), isu keselamatan mungkin timbul.

Gunakan alat jstack untuk membuang maklumat tindanan pelayan yang bermasalah. Jika terdapat gelung tak terhingga, mula-mula cari benang RUNNABLE dan cari kod masalah seperti berikut:

java.lang.Thread.State:RUNNABLE
di java.util.HashMap.get (HashMap.java:303 )
di com.sohu.twap.service.logic.TransformTweeter.doTransformTweetT5(TransformTweeter.java:183)
Muncul 23 kali secara keseluruhan.
java.lang.Thread.State:RUNNABLE
at java.util.HashMap.put(HashMap.java:374)
at com.sohu.twap.service.logic.TransformTweeter.transformT5(TransformTweeter. java:816)
muncul 3 kali secara keseluruhan.

Nota: Penggunaan HashMap yang tidak betul mengakibatkan gelung tak terhingga dan bukannya jalan buntu.

Letak berbilang benang boleh menyebabkan elemen hilang

Masalah utama terletak pada Entri baharu (cincang, kunci, nilai, e) kaedah addEntry Jika kedua-dua utas memperoleh e at pada masa yang sama, Kemudian elemen seterusnya adalah semua e, dan kemudian apabila memberikan nilai kepada elemen jadual, satu berjaya dan satu lagi hilang.

Selepas meletakkan elemen bukan nol, hasil yang diperoleh adalah batal

Kod dalam kaedah pemindahan adalah seperti berikut:

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

Dalam kaedah ini, tetapkan tatasusunan lama kepada src dan melintasi src, apabila elemen src bukan nol, tetapkan elemen dalam src kepada null, iaitu, tetapkan elemen dalam tatasusunan lama kepada null, iaitu ayat ini:

if (e != null ) {
         src[j] = null ;

Jika terdapat kaedah get untuk mengakses kekunci ini pada masa ini, ia masih memperoleh tatasusunan lama, dan sudah tentu ia tidak dapat memperoleh nilai yang sepadan.

Ringkasan: Apabila HashMap tidak disegerakkan, banyak masalah halus akan berlaku dalam program serentak, dan sukar untuk mencari punca dari permukaan. Oleh itu, jika terdapat fenomena berlawanan dengan intuisi semasa menggunakan HashMap, ia mungkin disebabkan oleh concurrency.

Struktur data HashMap

Saya perlu bercakap secara ringkas tentang struktur data klasik HashMap.

HashMap biasanya menggunakan tatasusunan penuding (diandaikan sebagai jadual[]) untuk menyuraikan semua kunci Apabila kunci ditambahkan, subskrip i tatasusunan dikira melalui kunci melalui algoritma Hash, dan kemudian Sisipkan. ini ke dalam jadual[i]. Jika dua kekunci berbeza dikira dalam i yang sama, ia dipanggil konflik, juga dipanggil perlanggaran Ini akan membentuk senarai terpaut pada jadual[i].

Kami tahu bahawa jika saiz jadual[] sangat kecil, seperti hanya 2, dan jika 10 kekunci hendak dimasukkan, maka perlanggaran akan menjadi sangat kerap, jadi algoritma carian O(1) menjadi Tanpa traversal senarai terpaut, prestasi menjadi O(n), yang merupakan kecacatan jadual Hash.

所以，Hash表的尺寸和容量非常的重要。一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash，这个成本相当的大。

HashMap的rehash源代码

下面，我们来看一下Java的HashMap的源代码。Put一个Key,Value对到Hash表中：

public V put(K key, V value)
{
     ......
     //算Hash值
     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<K,V>(hash, key, value, e);
     //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
     if (size++ >= threshold)
         resize( 2 * table.length);
}

新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

void resize( int newCapacity)
{
     Entry[] oldTable = table;
     int oldCapacity = oldTable.length;
     ......
     //创建一个新的Hash Table
     Entry[] newTable = new Entry[newCapacity];
     //将Old Hash Table上的数据迁移到New Hash Table上
     transfer(newTable);
     table = newTable;
     threshold = ( int )(newCapacity * loadFactor);
}

迁移的源代码，注意高亮处：

void transfer(Entry[] newTable)
{
     Entry[] src = table;
     int newCapacity = newTable.length;
     //下面这段代码的意思是：
     //  从OldTable里摘一个元素出来，然后放到NewTable中
     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 );
         }
     }
}

好了，这个代码算是比较正常的。而且没有什么问题。

正常的ReHash过程

画了个图做了个演示。

1. 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。

2. 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table1这里了。

3. 接下来的三个步骤是Hash表 resize成4，然后所有的 重新rehash的过程。

并发的Rehash过程

（1）假设我们有两个线程。我用红色和浅蓝色标注了一下。我们再回头看一下我们的 transfer代码中的这个细节：

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

而我们的线程二执行完成了。于是我们有下面的这个样子。

注意：因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

（2）线程一被调度回来执行。

• 先是执行 newTalbe[i] = e。

• 然后是e = next，导致了e指向了key(7)。

• 而下一次循环的next = e.next导致了next指向了key(3)。

（3）一切安好。 线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。

（4）环形链接出现。 e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

于是，当我们的线程一调用到，HashTable.get(11)时，悲剧就出现了——Infinite Loop。

三种解决方案

Hashtable替换HashMap

Hashtable 是同步的，但由迭代器返回的 Iterator 和由所有 Hashtable 的“collection 视图方法”返回的 Collection 的 listIterator 方法都是快速失败的：在创建 Iterator 之后，如果从结构上对 Hashtable 进行修改，除非通过 Iterator 自身的移除或添加方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出 ConcurrentModificationException。因此，面对并发的修改，Iterator 很快就会完全失败，而不冒在将来某个不确定的时间发生任意不确定行为的风险。由 Hashtable 的键和值方法返回的 Enumeration 不是快速失败的。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法：迭代器的快速失败行为应该仅用于检测程序错误。

Collections.synchronizedMap将HashMap包装起来

返回由指定映射支持的同步（线程安全的）映射。为了保证按顺序访问，必须通过返回的映射完成对底层映射的所有访问。在返回的映射或其任意 collection 视图上进行迭代时，强制用户手工在返回的映射上进行同步：

Map m = Collections.synchronizedMap( new HashMap());
...
Set s = m.keySet();  // Needn't be in synchronized block
...
synchronized (m) {  // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
     while (i.hasNext())
         foo(i.next());
}

不遵从此建议将导致无法确定的行为。如果指定映射是可序列化的，则返回的映射也将是可序列化的。

ConcurrentHashMap menggantikan HashMap

Jadual cincang yang menyokong konkurensi penuh dalam pengambilan semula dan konkurensi boleh laras yang dikehendaki dalam kemas kini. Kelas ini mematuhi spesifikasi fungsi yang sama seperti Hashtable dan termasuk versi kaedah yang sepadan dengan setiap kaedah Hashtable. Walau bagaimanapun, walaupun semua operasi selamat untuk benang, operasi mendapatkan semula tidak perlu dikunci dan mengunci keseluruhan jadual dengan cara yang menghalang semua akses tidak disokong. Kelas ini boleh saling beroperasi secara atur cara dengan Hashtable, bergantung pada keselamatan utasnya, bebas daripada butiran penyegerakannya. Operasi mendapatkan semula (termasuk dapatkan) secara amnya tidak menyekat dan, oleh itu, mungkin bertindih dengan operasi kemas kini (termasuk meletakkan dan mengalih keluar). Pendapatan semula menjejaskan keputusan operasi kemas kini yang paling baru selesai. Untuk beberapa operasi agregat, seperti putAll dan clear, pengambilan serentak hanya boleh menjejaskan pemasukan dan pengalihan keluar entri tertentu. Begitu juga, Iterator dan Enumerations mengembalikan elemen yang mempengaruhi keadaan jadual cincang pada satu masa, sama ada semasa iterator/penghitungan dicipta atau sejak. Mereka tidak membuang ConcurrentModificationException. Walau bagaimanapun, iterator direka untuk digunakan oleh hanya satu utas pada satu masa.

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah konkurensi berbilang benang HashMap Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!