Java

JavaスレッドセーフなHashMapの実装方法と原則



Java Thread Safe Hashmap Implementation Method



JavaHashMapはスレッドセーフではありません。マルチスレッドの条件下では、100％のCPU使用率として具体的に表される無限ループが発生しやすくなります。したがって、マルチスレッド環境でHashMapのスレッドセーフを確保するには、主に次の方法があります。

  1. スレッドセーフなjava.util.Hashtableクラスを使用します。
  2. java.util.concurrent.ConcurrentHashMapを使用してください。このクラスはスレッドセーフです。
  3. java.util.Collections.synchronizedMap（）メソッドを使用して、HashMapオブジェクトをラップし、スレッドセーフなマップを取得して、このマップを操作します。
  4. もちろん、セキュリティを確保するために、プログラムの主要なメソッドまたはコードセクションに自分を閉じ込めてください。もちろん、これは強くお勧めしません。

HashMapがスレッドセーフではない理由については、Chen Hao（weiboアカウント：左耳マウス）彼自身の技術ウェブサイトCoolshellの記事は非常に詳細です。記事リンク（ 電車で ）： http://coolshell.cn/articles/9606.html



ここでは、上記の方法で実装された並列セキュリティの原則に焦点を当てます。

（1）java.util.Hashtableクラス：クラスの主なデータ構造は次のとおりです。



/** * The hash table data. */ private transient Entry[] table private static class Entry implements Map.Entry { int hash K key V value Entry next

Hashtableの実装は配列であり、各配列要素はLinkList構造であるため、クラスのデータは実際にはハッシュテーブルに格納されていることがわかります。この実装は、HashMapの実装と一致しています。データ構造は次のとおりです。

では、Hashtableはどのようにしてスレッドセーフを保証するのでしょうか？以下は、Hashtableのソースコードです。

public synchronized V get(Object key) { Entry tab[] = table ...... // Omitted here, please refer to jdk implementation for specific implementation } public synchronized V put(K key, V value) { ...... // Specific implementation is omitted, please refer to jdk implementation } public synchronized V remove(Object key) { ...... // Specific implementation is omitted, please refer to jdk implementation } public synchronized void putAll(Map t) { for (Map.Entry e : t.entrySet()) put(e.getKey(), e.getValue()) } public synchronized void clear() { ...... // Specific implementation is omitted, please refer to jdk implementation }

上記は、get（）、put（）、remove（）など、Hashtableによって提供される主なメソッドです。 各メソッド自体が同期され、2つのスレッドが同時にデータを操作することはないため、スレッドの安全性が確保されますが、実行効率も大幅に低下します。 。したがって、お勧めしません。



（2）カプセル化にはjava.util.Collections.synchronizedMap（Map）メソッドを使用します。メソッドのソースコードは次のとおりです。

public static Map synchronizedMap(Map m) { return new SynchronizedMap(m) } private static class SynchronizedMap implements Map, Serializable { // use serialVersionUID from JDK 1.2.2 for interoperability private static final long serialVersionUID = 1978198479659022715L private final Map m // Backing Map final Object mutex // Object on which to synchronize SynchronizedMap(Map m) { if (m==null) throw new NullPointerException() this.m = m mutex = this } SynchronizedMap(Map m, Object mutex) { this.m = m this.mutex = mutex } public int size() { synchronized(mutex) {return m.size()} } public boolean isEmpty(){ synchronized(mutex) {return m.isEmpty()} } public boolean containsKey(Object key) { synchronized(mutex) {return m.containsKey(key)} }

これは、実装のソースコードから見つけることができます。 そのカプセル化の性質は、Hashtableの実装と完全に一致しています。つまり、元のマップ自体のメソッドがロックされています。 、ロックされたオブジェクトは、外部の共有オブジェクトミューテックス、またはパッケージ化後のスレッドセーフなマップ自体のいずれかです。 SynchronizedMap mutex = nullの場合、ハッシュテーブルは特殊なケースとして理解できます。したがって、 この同期方法の実行効率も非常に低いです 。

Hashtableができたので、Collectionsが提供するこの静的メソッドをラップする必要があるのはなぜですか？非常にシンプルなこのパッケージは、Javaコレクションフレームワークによって提供される統合インターフェースであり、HashMapに加えて、他のマップにも使用できます。もちろん、コレクションツールクラスは、マップのカプセル化に加えて、コレクションのスレッドセーフなカプセル化メソッド（Set、Listなど）も提供します。詳細については、java.util.Colletionsの実装を参照してください。その原理はSynchronizedMapと一致しています。

（3）java.util.concurrent.ConcurrentHashMapクラスを使用します。並行プログラミングマスターのDougLeaによって作成された、まったく問題ありません。これは、HashMapのスレッドセーフバージョンです。 ConcurrentHashMapは、Hashtableと比較して、アクセスのスレッドセーフを保証するだけでなく、効率も大幅に向上します。

ConcurrentHashMapのデータ構造は次のとおりです（参照画像アドレス http://www.yupoo.com/photos/goldendoc/81556254/ ）：



HashMapおよびHashtableと比較して、ConcurrentHashMapはセグメントレイヤーを追加します。各セグメントは原則としてHashtableと同等であり、ConcurrentHashMapはセグメントの配列です。以下は、ConcurrentHashMapのputメソッドとgetメソッドです。

final Segment segmentFor(int hash) { return segments[(hash >>> segmentShift) & segmentMask] } public V put(K key, V value) { if (value == null) throw new NullPointerException() int hash = hash(key.hashCode()) return segmentFor(hash).put(key, hash, value, false) } public V get(Object key) { int hash = hash(key.hashCode()) return segmentFor(hash).get(key, hash) }

ConcurrentHashMapにデータを挿入したり、データを読み取ったりするには、まず、対応するセグメントへの対応するキーマッピングについて説明する必要があります。 したがって、単一のセグメント操作がロックされている限り、クラス全体をロックする必要はありません。 。理論的には、n個のセグメントがある場合、最大n個のスレッドに同時にアクセスできます。これにより、同時アクセスの効率が大幅に向上します。加えて 再ハッシュ（）操作も単一のセグメントで実行されます 、したがって、マップ内のデータ量の増加によって引き起こされる再ハッシュのコストも比較的低くなります。

単一セグメントのデータ操作のソースコードは次のとおりです。：

V put(K key, int hash, V value, boolean onlyIfAbsent) { lock() try { int c = count if (c++ > threshold) // ensure capacity rehash() ...... // Code is omitted, please check the source code for details } finally { unlock() } } V replace(K key, int hash, V newValue) { lock() try { HashEntry e = getFirst(hash) ...... // Code is omitted, please check the source code for details } finally { unlock() } }

単一のセグメントで実行されるデータ更新操作がすべてロックされていることがわかります。これにより、スレッドの安全性が確保されます。

ConcurrentHashMapのより具体的な実装と分析については、（ 電車で ）。 http://www.iteye.com/topic/1103980 、非常に詳細。

いくつかのスレッド同期実装方法の効率比較を参照できます（ 電車で ）。 http://blog.sina.com.cn/s/blog_734a77160100yku1.html