2列コレクションフレームワークMapをこれほど雄弁に説明する方法は見たことがない。

よく使われる実装クラス構造

I. ハッシュマップ

Map、Cloneable、Serializable インターフェースを実装し、AbstractMap クラスを継承しています。

public class HashMap<K,V> extends AbstractMap<K,V>
 implements Map<K,V>, Cloneable, Serializable 	
 /**
 * Map : キーと値のペアを実装するMapインターフェースは、キーが値に対応することを指定する
 * HashMapこのインターフェイスを使ってDictionaryクラスを置き換える
 *
 * AbstractMap : Map抽象クラスを継承し、Map操作の実装を減らす
 *
 * Cloneable : Objectを呼び出すことで表示できる.clone()メソッドは、このクラスでは合法である
 * フィールド複製の例
 *
 * Serializable : インターフェイスを実装した後、クラスはシリアライズとデシリアライズができる
 */

HashMapはスレッドセーフですか？

HashMapはスレッドセーフではありませんが、ConcurrentHashMapは並行環境で使用できます。

HashMapの内部実装は

内部実装：JDK1.8で配列+連鎖テーブル、配列+連鎖テーブル+赤黒木の後にJDK1.8です赤黒木の理由に参加：JDK1.8 HashMapは配列+連鎖テーブルを使用して、ハッシュ関数に起因する100％にすることはできませんので、均一の分布の要素は、インデックスが非常に長い連鎖テーブルを形成するように、同じインデックスに堆積要素の数が多い原因となる、このように要素のトラバーサル時間の複雑さO（ログn）は、HashMapの利点を失って、赤黒木に参加し、O（ログn）の時間の複雑さを見つける、O（ログn）の時間の複雑さを見つける、赤黒木の利点を失う。Oの（n）の時間の複雑さ、HashMapの利点の損失の走査のこの要素は、赤と黒の木に参加し、Oの（ログn）の時間の複雑さを見つける、配列の特性の最適化を達成するために：高速、Oの（1）の時間の複雑さを見つけるために、追加および削除遅い、Oの（n）の時間の複雑さ連鎖テーブルの特性：遅い、Oの（n）の時間の複雑さを見つけるために、追加および削除速い、時間の複雑さはOです。(1）赤黒木の特性：チェーンテーブルをトラバースに基づいて、赤黒木は、時間の複雑さを見つけるためにO（ログn）です赤黒木のクエリの効率ははるかにチェーンテーブルよりも大きいですが、挿入/削除チェーンテーブルよりも遅い

HashMapの主なパラメータ

1.デフォルトの初期容量：16、2の整数乗でなければなりません。

2.デフォルト負荷係数：0.75

3.しきい値：容量*負荷率

4.ツリーのしきい値：デフォルトは8、バケット内のチェーンテーブルの長さが8より大きい場合、チェーンテーブルのツリー化

5.非ツリーのしきい値：デフォルトは6、ときに展開が実行される）、計算後、<6内の元の赤黒木の数は、その後、赤黒木から連鎖表に変換されます

6.ツリーの最小容量：バケットは、容量を拡張する際の衝突を避けるために、ツリーのハッシュテーブルの最小容量、少なくともTREEIFY_THRESHOLDの4倍であってもよい。

//赤黒木に連鎖するテーブルのしきい値
static final int TREEIFY_THRESHOLD = 8;
//赤黒木の閾値を連鎖表にする
static final int UNTREEIFY_THRESHOLD = 6;
/**
*最小ツリー化容量のしきい値：すなわち、ハッシュテーブルの容量が> リンクされたテーブルのツリー化は、値が
*そうでなければ、バケツに要素が多すぎる場合、ツリー化する代わりに直接展開される
*展開とツリー化オプションの競合を避けるため、この値は4より小さくできない* TREEIFY_THRESHOLD
**/
static final int MIN_TREEIFY_CAPACITY = 64;

配列の長さが64より大きく、チェインテーブルの長さが8より大きい場合のみ、チェインテーブルをツリー化することができます チェインテーブルの長さが8より大きい場合、treeifyBinメソッドを呼び出して赤黒ツリーに変換することになりますが、treeifyBinメソッド内に判定があり、配列の長さが64より大きい場合のみ、チェインテーブルをツリー化することができます そうでない場合は、チェインテーブルの拡張サイズを変更することしかできません チェインテーブルが長すぎて配列が短すぎるため、ハッシュの衝突が頻繁に発生します。チェーンテーブルが長すぎて配列が短すぎるため、ハッシュの衝突が頻繁に起こります。そうなると、ツリー化はあまり役に立ちません。<64进行扩容，而不是进行树形化 链表的长度>ツリー化は配列の長さである8をチェックすべきですが、もし配列の長さが64未満であれば、ツリー化せずにリサイズ後にリハッシュします。

HashMapの共通メソッド

Add: V put(K key,V value) --> 要素の追加

Delete: void clear() --> すべてのキーと値のペア要素をクリアします。

V remove(Object key) --> キーに対応する値を削除し、その値を返します。

判定：containsKey(Object key) --> 指定されたキーを含むか否か。

containsValue(オブジェクトの値) -> 指定された値を含むかどうか

反復: Set< />entrySet()-> キーと値のペアの取得

V get(Object key) --> キーを元に値を取得

コレクション value()->値のコレクションを取得

Get: Set SetKey()-> キーのセットを取得

int size()-> セット要素の数を取得します。

基本メソッドの使用

HashMap<Integer,String> map=new HashMap<>();
		//要素を追加する
		map.put(1, "a");
		map.put(2, "b");
		map.put(3, "c");
		//キーは繰り返し使用できず、値は上書きされる
		map.put(3, "C");
		
		//キーによってキーと値のペア全体を削除する
		map.remove(3);
		// 
		map.clear();
		//ヌルかどうか
		System.out.println(map.isEmpty());//false
		//4つの値を含むかどうか
		System.out.println(map.containsKey(4));//false
		//値 "b "を含むかどうか。
		System.out.println(map.containsValue("b"));//true
		//コレクション要素の数を取得する
		System.out.println(map.size());//3
		//キーで値を取得する
		System.out.println(map.get(3));//C
		//すべての値からなるコレクションを取得する
		Collection<String> values=map.values();
		for(String v:values){
			System.out.println(" :"+v);//値：a 値：b 値：c
		}
		
		System.out.println(map);
	}

種類のトラバーサル

public static void main(String[] args) {
 Map<String,Integer> map=new HashMap<>();
 map.put(" ",21);
 map.put(" ",35);
 map.put(" ",18);
 demo1(map);
 demo2(map);
 }
 //セット<K> setKey()メソッド・トラバーサル
 private static void demo1(Map<String,Integer> map) {
 Set<String> keys=map.keySet();
 for (String key:keys){
 Integer value=map.get(key);
 System.out.println(" "+key+" "+value);//キーは：小林 値は：21
 //キーは: Xiao Wang 値は: 18
 //キーは: Xiao Zhang 値は: 35
 }
 }
 //セット<Map.Entry<K,V>> entrySet()メソッド・トラバーサル
 private static void demo2(Map<String, Integer> map) {
 Set<Map.Entry<String,Integer>> kvs=map.entrySet();
 for (Map.Entry<String,Integer> kv:kvs){
 String kstring=kv.getKey();
 Integer istring=kv.getValue();
 System.out.println(kstring+"-----"+istring);
 //小林 -----21
 //王暁 -----18
 //張暁 -----35
 }
 }

ハッシュのコンフリクト問題について

1.原因

ある要素に対してハッシュ演算を行うと、格納アドレスが取得され、挿入を行うと、そのアドレスが他の要素によって占有されていることが判明します。これをハッシュ競合といい、ハッシュ衝突ともいいます。

ハッシュ関数の設計が重要であり、優れたハッシュ関数は、計算が簡単で、ハッシュアドレスの分布が均一であることを確認しようとしますが、配列は、メモリ空間の連続した固定長であり、その後、優れたハッシュ関数は、ストレージアドレスが絶対に競合していないことを保証することはできません。2.ハッシュ競合法の解決策：

オープン・アドレス方式：競合が発生した場合、次に空いているストレージ・アドレスを探し続けます。再ハッシュ関数法：競合が発生した場合、競合がなくなるまで2番目、3番目、ハッシュ関数を使用してアドレスを計算します。チェーンアドレス法：すべてのキーワードの同義語のレコードを1つの連鎖したテーブルに格納し、このテーブルを同義語サブテーブルと呼びます。HashMap は連鎖アドレス法、つまり配列＋連鎖テーブル法を使用します。

HashMapは、配列+連鎖テーブルで構成され、配列はHashMapの本体であり、連鎖テーブルは、主にハッシュの競合と存在を解決するために、配列の場所が連鎖テーブルが含まれていない場合は、検索、追加、およびその他の操作のために非常に迅速に、1つだけアドレス指定することができます。つまり、カバーするために、そうでない場合は追加され、その後、キーオブジェクトの等しいメソッドを介して1つずつ比較検索します。だから！パフォーマンスを考慮すると、HashMap内のリンクされたテーブルの数が少ないほど、パフォーマンスが向上します。

JDK1.8HashMapのデッドループ問題

理由：配列の拡張により、同じインデックス位置のノードの順序が逆になります。

7.HashMapとHashtableの違い

equals()メソッドを書き換えた後、hashCode()メソッドを書き換える必要がありますか？なぜですか？

equals() メソッドをオーバーライドするには、hashCode() メソッドをオーバーライドする必要があります。

hashCodeの指定：2つのオブジェクトが等しい場合、hashCodeは同じでなければなりません。2つのオブジェクトのhashCodeが同じ場合、2つのオブジェクトは必ずしも等しくありません；

hashCodeメソッドをオーバーライドせずにequalsメソッドをオーバーライドすると、デフォルトでObjectクラスのhashCode()メソッドが呼び出されます。簡単に言うと、equals メソッドの後に hashCode メソッドをオーバーライドすることは、比較される 2 つのオブジェクトが同じオブジェクトであることを確認するためです。

LinkedHashMap

違いは、LinkedHashMap は内部的に Entry を提供し、HashMap の Node を置き換えます。

LinkedHashMap：マップの要素をトラバースする際に、追加順序に従ってトラバースできるようにします。

理由：元のHashMapの基本構造に基づいて、前後の要素へのポインタのペアを追加しました。

頻繁にトラバーサル操作を行う場合は、HashMapよりもLinkedHashMapの方が効率的です。

第三に、TreeMap

キーと値のペアは、キーまたはカスタムソートの自然な順序を考慮するこの時点で、ソートされたトラバーサルの実装に従ってソートされていることを確認し、赤黒木の基礎となる使用

要素はキーでソートされ、要素は一意です。

1) ナチュラルオーダー

要素のクラスが自然順序Comparableを継承するようにします。

2) コンパレーターソート

コレクションのコンストラクタ・メソッドにコンパレータ・インターフェースを持たせます。

IV.ハッシュテーブル

スレッドセーフで非効率。