HashMapとConcerenthashMapの原理紹介
3380 ワード
HashMapの原理紹介
Javaビット演算説明
コンカレントHashMap分析 ConccurrenthashMapはjdk 1.7とjdk 1.8での実装に大きな違いがあります。(1と2を参照)jdk 1.8の改善: はsegmentsフィールドをキャンセルして、直接にtranient volatile HashEnty[]tableでデータを保存して、table配列要素をロックとして採用して、それによって各ラインのデータをロックして、さらに合併衝突の確率を減らすことができます。 は、元々テーブル配列+一方向チェーンのデータ構造を、テーブル配列+一方向チェーン+レッドツリーの構造に変更する。hashテーブルにとって、最も核心的な能力は、key hashの後を配列に均等に分布させることである。hashの後にハッシュが均一であれば、テーブル配列の各列の長さは主に0または1である。しかし、いつも理想的ではなく、ConcerenthashMap類のデフォルトのローディング係数は0.75ですが、データ量が多すぎたり、運が悪い場合は、列の長さが長すぎる場合もあります。一方通行のリスト方式を採用している場合は、あるノードの時間の複雑さがO(n)であることを確認します。したがって、8(デフォルト値)を超える数のリストに対して、Jdk 1.8では、赤と黒のツリーの構造が採用されているので、クエリの時間複雑さは、O(logN)に低減され、性能を向上させることができる。元々テーブル配列+一方向チェーンのデータ構造を、テーブル配列+一方向チェーン+レッドツリーの構造に変更します。hashテーブルにとって、最も核心的な能力は、key hashの後を配列に均等に分布させることである。hashの後にハッシュが均一であれば、テーブル配列の各列の長さは主に0または1である。しかし、いつも理想的ではなく、ConcerenthashMap類のデフォルトのローディング係数は0.75ですが、データ量が多すぎたり、運が悪い場合は、列の長さが長すぎる場合もあります。一方通行のリスト方式を採用している場合は、あるノードの時間の複雑さがO(n)であることを確認します。したがって、8(デフォルト値)を超える数のリストに対して、Jdk 1.8では、赤と黒のツリーの構造が採用されているので、クエリの時間複雑さは、O(logN)に低減され、性能を向上させることができる。 ConccurrenthashMapはどうやってスレッドを安全にするかという多くの文章によると、ConcerenthashMapはセグメントロック技術で高合併を実現しています。これはjdk 1.7の中の実現です。jdk 1.8では、synchronized各tableのnodeオブジェクトを使用して、ロックを低減した粒度を実現しています。jdk 1.8では、synchronizedが最適化され、効率はRentrant Lockとほぼ同じである。 ConccurrenthashMap弱整合性の問題:ConcerenthashMapには多くの操作があります。get、put、iterator…ここでこれらの方法の整合性を分析します。 ContcurrenthashMap初期ConccurrenthashMapに弱一致性がある問題は、主にput操作でtableがvolatileを加えたためであるが、tableの中の要素はvolatileではなく、get操作にロックがない。書き込みが発生するデータはすぐには見えません。jdk 1.8は を通ります。
ConccurrenthashMapはHashTableに取って代わることができますか?ConccurrenthashMapのiteratorは弱い一致性ですが、HashTableは強い一致性です。完全に入れ替わるわけではない。
Javaビット演算説明
コンカレントHashMap分析
pred.next = new Node(hash, key,value, null);
を追加します。putの要素はすぐに見られます。弱い一致ではなく、詳しく分析します。まだ弱い一致です。ここでは6666を印刷して詳しく分析してはいけません。 public static void main(String[] str){
//ConcurrentHashMap testCHM = new ConcurrentHashMap(); // concurrentHashMap, concurrentHashMap,
// .
HashMap testCHM = new HashMap(); //HashMap , ConcurrentModificationException
testCHM.put("1","11111");
testCHM.put("2","22222");
testCHM.put("3","33333");
testCHM.put("4","44444");
testCHM.put("5","55555");
testCHM.put("7","77777");
testCHM.put("8","88888");
new Thread(new Runnable() {
@Override
public void run(){
try {
Thread.sleep(6000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("------ 66666-------");
testCHM.put("6","66666");
System.out.println("---------- 666-----");
}
}).start();
for(Map.Entry entry: testCHM.entrySet()){
System.out.println(entry.getValue());
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}