ArrayListとLinkedListの2つのセットを分析しました。 ArrayListは配列に基づいて実装されており、LinkedListはリンクリストに基づいて実装されていることがわかります。それぞれには独自の利点と短所があります。たとえば、ArrayListは、要素を配置および探しているときにLinkedListよりも優れていますが、LinkedListは要素を追加および削除するときにArrayListよりも優れています。この記事で導入されたハッシュマップは、両方の利点を組み合わせています。その基礎となる層は、ハッシュテーブルに基づいて実装されています。ハッシュ競合が考慮されない場合、ハッシュマップの時間の複雑さに加えて、削除、変更、および検索操作は驚くべきo（1）に到達する可能性があります。まず、それが基づいているハッシュテーブルの構造を見てみましょう。
上記の図からわかるように、ハッシュテーブルは、配列とリンクリストで構成される構造です。もちろん、上記の数字は悪い例です。適切なハッシュ関数は、配列内の要素の分布を平均し、ハッシュ競合を減らし、リンクリストの長さを短縮する必要があります。リンクリストの長さが長いほど、検索中に移動する必要があるノードが多いほど、ハッシュテーブルのパフォーマンスが悪化します。次に、ハッシュマップのメンバー変数を見てみましょう。
// default intirical capipation static final int default_initial_capacity = 1 << 4; //デフォルトの最大容量静的最大int最大_capacity = 1 << 30; //デフォルトロード係数は、ハッシュテーブルが静的最終float_load_factor = 0.75f; //空のハッシュテーブル<？ entry <k、v> [] table =（entry <k、v> []）empty_table; // hashmapサイズ、つまり、ハッシュマップ過渡的なintサイズに保存されているキー値ペアの数;メカニズム過渡int modcount; //代替ハッシュのデフォルトのしきい値を使用します。
メンバー変数からわかるように、ハッシュマップのデフォルトの初期容量は16で、デフォルトの負荷係数は0.75です。しきい値は、セットに保存できるキー値ペアのしきい値です。デフォルトは、初期容量*負荷係数、つまり16*0.75 = 12です。キー価値ペアがしきい値を超える必要がある場合、この時点でハッシュテーブルがすでに飽和していることを意味します。要素が追加され続けると、ハッシュ競合が追加され、ハッシュマップの性能が低下します。現時点では、自動容量拡張メカニズムがトリガーされ、ハッシュマップのパフォーマンスが確保されます。また、ハッシュテーブルは実際にはエントリアレイであり、配列に保存されている各エントリが一方向リンクリストのヘッダーノードであることがわかります。このエントリは、ハッシュマップの静的な内部クラスです。エントリのメンバー変数を見てみましょう。
静的クラスエントリ<k、v>はmap.entry <k、v> {final k key; //キーV値; // value entry <k、v> next; //次のエントリINT HASHへの参照。 // histocode ... //次のコードを省略}エントリインスタンスは、キーと値を含むキー価値ペアです。各エントリインスタンスには、次のエントリインスタンスへの参照があります。繰り返し計算を回避するために、各エントリインスタンスは対応するハッシュコードも保存します。エントリアレイはHashMapの中核であり、すべての操作がこの配列に対して行われていると言えます。 HashMapソースコードは比較的長いため、すべての方法を包括的な方法で導入することは不可能であるため、それらを導入するためのキーポイントのみに焦点を当てます。次に、問題指向になり、次の問題についてハッシュマップの内部メカニズムを詳細に調査します。
1. Hashmapは、建設中にどのような操作を行いますか？
//コンストラクター、初期化容量に合格し、荷重係数public hashmap（int initialCapacity、float loadFactor）{if（initialCapacity <0）{throw new IllegalArgumentException（ "違法初期容量：" + initialCapacity）; } //初期化容量が最大容量よりも大きい場合、（initialcapacity> maximing_capacity）{initialCapacity = Quiming_capacity;の場合、最大容量に設定します。 } //負荷係数が0未満であるか、負荷係数が浮動小数点番号ではない場合、例外がスローされます（loadFactor <= 0 || float.isnan（loadfactor））{新しいIllegalargumentException（ "違法負荷係数：" + loadFactor）; } // Load Factor this.LoadFactor = LoadFactor; //しきい値は初期化容量のしきい値= initialCapacityです。 init（）;} void init（）{}すべてのコンストラクターがこのコンストラクターを呼び出します。このコンストラクターでは、パラメーターの検証を実行することに加えて、2つのことを行うことがわかります。荷重係数を着信荷重係数に設定し、しきい値を着信初期化サイズに設定します。 initメソッドは空で、何もしません。現時点では、着信初期化サイズに基づいて新しいエントリアレイは作成されていないことに注意してください。では、いつ新しい配列を作成しますか？読み続けてください。
2. Hashmapがキー価値のペアを追加すると、どのような操作が実行されますか？
//キーバリューのペアをハッシュマップパブリックv put（k key、v value）{// initialize if（table == empty_table）{//ハッシュテーブルインフレータブルを初期化（しきい値）; } if（key == null）{return putfornullkey（value）; } // key int hash = hash（key）のハッシュコードを計算します。 //ハッシュコードに従ってハッシュテーブルの位置を配置int i = indexfor（hash、table.length）; for（entry <k、v> e = table [i]; e！= null; e = e.next）{object k; //対応するキーがすでに存在する場合、その値値を置き換えて元の値を返します（e.hash == hash &&（（k = e.key）== key || key.equals（k））{v oldvalue = e.value; e.value = value; E.RecordAccess（This）; OldValueを返します。 }} modcount ++; //対応するキーがない場合は、Hashmap Addentry（Hash、Key、Value、i）にエントリを追加します。 // null return nullを返します;}キー価値のペアを追加すると、最初にハッシュテーブルが空のテーブルであるかどうかを確認し、空のテーブルである場合、初期化されます。次に、後続の操作を実行し、ハッシュ関数を呼び出して、渡されたキーのハッシュコードを計算します。エントリアレイの指定されたスロットをハッシュコードに従って配置し、スロットの一元配置リンクリストをトラバースします。既に存在する場合は、交換操作を実行します。そうしないと、新しいエントリが作成され、ハッシュテーブルに追加されます。
3.ハッシュテーブルはどのように初期化されますか？
//ハッシュテーブルを初期化するとハッシュテーブル容量が拡張されます。これは、着信容量が2つのプライベートボイドインフレーター可能（int tosize）のパワーではない可能性があるため、拡張されます。 //しきい値を設定します。ここに容量があります * loadFactorしきい値=（int）math.min（容量 * loadfactor、maxim_capacity + 1）; //指定された容量テーブルを使用して新しいハッシュテーブルを作成します= new entry [capacity]; //ハッシュシードの初期化inithashseedasneeded（容量）;}
上で知っているように、ハッシュマップを構築するときは、新しいエントリアレイを作成することはありませんが、現在のハッシュテーブルが操作中に空のテーブルであるかどうかを確認します。空のテーブルの場合は、初期化のために膨張可能な方法を呼び出します。この方法のコードは上に投稿されています。ハッシュマップを構築するときに渡された初期化サイズが2のパワーではない可能性があるため、エントリアレイの容量がメソッド内で再計算されることがわかります。したがって、この数値を2のパワーに変換し、新しい容量に基づいて新しいエントリアレイを作成する必要があります。ハッシュテーブルを初期化するときは、しきい値を再度リセットすると、しきい値は一般に容量*loadFactorです。さらに、ハッシュテーブルの初期化時にハッシュシード（ハッシュシード）が初期化されます。このハッシュシードは、ハッシュ関数を最適化するために使用されます。デフォルトは0であり、代替ハッシュアルゴリズムは使用されませんが、最適化効果を実現するためにハッシュシード値を自分で設定することもできます。これについては、以下で詳しく説明します。
4. Hashmapは、容量を拡大する必要があるかどうか、どのように容量を拡大するかをいつ決定しますか？
//エントリメソッドを追加し、最初に容量を拡張するかどうかを決定します（int hash、k key、v value、int bucketindex）{//ハッシュマップのサイズがしきい値より大きく、ハッシュテーブルの対応するスロットの値が空でない場合しきい値は、ハッシュ競合が発生しようとしていることを示しているため、容量のサイズ変更（2 * table.length）を拡張します。 hash =（null！= key）？ハッシュ（キー）：0; BucketIndex = indexfor（hash、table.length）; } //ここでは、ハッシュマップのサイズがしきい値を超えないため、容量createentry（ハッシュ、キー、値、backetindex）を拡張する必要はないことが示されています。 int oldcapacity = oldtable.length; //現在の最大容量が既に使用されている場合、（OldCapacity == Maximum_Capacity）{threshold = integer.max_value;戻る; } //それ以外の場合は、容量エントリを展開します[] newtable = new entry [newCapacity]; //ハッシュテーブル転送を移行する方法（NewTable、inithashseedasneeded（newcapacity））; //現在のハッシュテーブルを新しいハッシュテーブルテーブルに設定します= newTable; //ハッシュテーブルのしきい値を更新=（int）math.min（newcapacity * loadfactor、maxim_capacity + 1）;}Putメソッドを呼び出してキー値ペアを追加するとき、コレクションにキーがない場合は、Addentryメソッドを呼び出して新しいエントリを作成します。新しいエントリを作成する前に上に掲載されているAddentryコードが表示されたら、最初に現在の収集要素のサイズがしきい値を超えるかどうかを判断します。しきい値がしきい値を超えている場合は、拡張のためにサイズを呼び出します。渡された新しい容量は、元のハッシュテーブルの2倍です。サイズ変更方法では、元のハッシュテーブルの2倍の容量を持つ新しいエントリアレイが作成されます。次に、古いハッシュテーブルのすべての要素が新しいハッシュテーブルに移行され、そこで再ハッシュが実行される可能性があり、再ハッシュを実行するかどうかは、inithashseedasneed methodによって計算された値に従って実行されます。ハッシュテーブルの移行が完了した後、現在のハッシュテーブルは新しいテーブルに置き換えられ、最後にハッシュマップのしきい値は新しいハッシュテーブル容量に基づいて再計算されます。
5.エントリアレイのサイズが2のパワーでなければならないのはなぜですか？
//ハッシュコードに対応する配列インデックスを返しますstatic int indexfor（int h、int length）{return h＆（length-1）; }IndexForメソッドは、ハッシュコードに基づいて配列内の対応するサブスクリプトを計算します。 （＆）演算子がこの方法で使用されていることがわかります。操作は、2つのオペランドでビット操作を実行することです。対応する2つのビットが1の場合、結果は1です。それ以外の場合は0です。操作は、01011010＆00001111 = 00001010などのオペランドの高ビット値を削除するためによく使用されます。コードに戻り、H＆（長さ1）が何をするかを見てみましょう。
渡された長さは、エントリアレイの長さであることが知られています。配列添え付けが0から計算されることがわかっているため、配列の最大添え字は長さ1です。長さが2の電力の場合、長さ1のバイナリビットの後に1が続きます。この時点で、H＆（長さ1）の関数は、Hの高ビット値を除去し、Arrayの添え字としてHの低ビット値のみを残すことです。これから、このアルゴリズムを使用して配列のサブスクリプトを決定するために、エントリアレイのサイズが2のパワーとして定義されていることがわかります。
6.ハッシュ関数はハッシュコードをどのように計算しますか？
//ハッシュコードfinal int hashを生成する関数（オブジェクトk）{int h = hashseed; //キーが文字列タイプの場合、別のハッシュアルゴリズムを使用します（0！= h && k instanceof string）{return sun.misc.hashing.stringhash32（（string）k）; } h ^= k.hashcode（）; //摂動関数h ^ =（h >>> 20） ^（h >>> 12）; return h ^（h >>> 7） ^（h >> 4）;}ハッシュメソッドの最後の2行は、ハッシュ値を真に計算するアルゴリズムです。ハッシュコードを計算するアルゴリズムは、摂動関数と呼ばれます。いわゆる摂動関数は、すべてを混ぜることです。ここでは、4つの右から右へのシフト操作が使用されていることがわかります。目的は、Hの高い値と低い値を混合して、低値のランダム性を高めることです。上記のように、ポジショニングアレイの添え字がハッシュコードの低ビット値に基づいて決定されることを知っています。キーのハッシュコードはハッシュコード法によって生成され、悪いハッシュコード法によって生成されたハッシュコードの低い値は多くの繰り返しを持っている可能性があります。ハッシュコードを配列に比較的均一にマッピングするために、摂動関数が役立ち、高ビット値の特性を低ビット値に組み合わせて低ビット値のランダム性を高め、ハッシュ分布をより緩め、パフォーマンスを改善します。次の図は、理解するための例を示しています。
7。交換用のハッシュで何が起こっているのですか？
ハッシュメソッドでは、ハッシュシードが最初にHに割り当てられることがわかります。このハッシュシードはハッシュシードであり、ランダムな値であり、ハッシュ関数の最適化に使用されます。デフォルトのハッシュシードは0です。つまり、代替ハッシュアルゴリズムはデフォルトでは使用されません。では、いつハッシュシードを使用するのでしょうか？まず、システムプロパティにjdk.map.althashing.thresholdの値を有効にするために代替ハッシュを設定し、設定する必要があります。この値は、システムプロパティでデフォルトで-1です。 -1の場合、代替ハッシュを使用するしきい値は整数です。max_value。これはまた、交換用ハッシュを使用できないことを意味します。もちろん、このしきい値を少し小さく設定できるため、設定要素がしきい値に達するとランダムハッシュシードが生成されます。これにより、ハッシュ関数のランダム性が向上します。なぜ代替ハッシュを使用するのですか？設定された要素が設定したしきい値に達すると、ハッシュテーブルが比較的飽和しており、ハッシュ競合の可能性が大幅に増加します。この時点で、追加された要素に対してよりランダムなハッシュ関数を使用すると、追加の要素がハッシュテーブルにランダムに分布することができます。
注：上記の分析はすべてJDK1.7に基づいており、異なるバージョン間に大きな変化があります。読者は注意を払う必要があります。