ストレージ構造
まず、ハッシュマップはハッシュテーブルに基づいて保存されます。その中には配列があります。要素を保存する場合、最初にそのキーのハッシュ値を計算し、ハッシュ値に基づいて配列内の要素の対応するサブスクリプを見つけます。この位置に要素がない場合は、現在の要素を直接置きます。要素がある場合（ここで記憶されています）、現在の要素を要素Aの前面にリンクし、現在の要素を配列に入れます。したがって、ハッシュマップでは、配列は実際にリンクリストの最初のノードを保存します。以下は、バイドゥ百科事典の写真です。
上の図に示すように、各要素はエントリオブジェクトであり、要素のキーと値が保存され、次のオブジェクトを指すために使用できるポインターがあります。同じハッシュ値（つまり、競合）を持つすべてのキーは、Zipperメソッドであるリンクリストを使用してそれらをまとめます。
内部変数
// default iniviory capipation static final int default_initial_capacity = 16; //最大容量静的最終int最大30; //デフォルトロードファイナルフロートdefault_load_factor = 0.75f; // hasフロートロードファクター;
上記の変数では、容量とは、ハッシュテーブルの長さ、つまりテーブルのサイズ、デフォルトは16です。負荷係数荷重ファクターはハッシュテーブルの「完全」であり、JDKのドキュメントは次のように述べています。
負荷係数は、容量が自動的に増加する前に、ハッシュテーブルがどれだけ完全に取得できるかの尺度です。ハッシュテーブルのエントリの数が荷重係数と現在の容量の積を超えると、ハッシュテーブルが再ハッシュされ、ハッシュテーブルにはバケットの数の数が約2倍になります。
一般的な意味は次のとおりです。荷重係数は、拡張前にハッシュテーブルがどれだけ完全にインストールできるかの尺度です。ハッシュテーブルの「キー価値ペア」の数が現在の容量と荷重係数の積を超えると、ハッシュテーブルがハッシュし（つまり、内部データ構造が再構築されます）、ハッシュテーブルの容量は元の2倍になります。
上記の変数定義からわかるように、デフォルトの読み込み係数default_load_factorは0.75です。この値が大きいほど、スペース使用率が高くなりますが、クエリ速度（GETおよびPUTを含む）は減速します。負荷係数を理解した後、しきい値も理解できます。実際、容量*荷重係数に等しくなります。
コンストラクタ
public hashmap（int initialcapacity、float loadfactor）{if（initialcapacity <0）throw new IllegalargumentException（ "違法初期容量：" + initialCapacity）; if（initialcapacity> maximion_capacity）hiritioncapacity = maxim_capacity; if（loadFactor <= 0 || float.isnan（loadFactor））を投げて、新しいIllegalargumentException（ "違法負荷係数：" + loadFactor）; // 2> = initialCapacity int caperation = 1の電力を見つける; while（容量<initialcapacity）//指定された容量容量<< = 1よりも大きい2の最小電力を計算します。 this.loadfactor = loadfactor;しきい値=（int）math.min（容量 * loadfactor、maxim_capacity + 1）;表=新しいエントリ[容量]; //ハッシュテーブルにスペースを割り当てますusealthashing = sun.misc.vm.isbooted（）&&（capipour> = holder.alternative_hashing_threshold）; init（）;}いくつかのコンストラクターがあり、最終的には上記を呼び出します。 2つのパラメーターを受け入れます。1つは初期容量で、もう1つは荷重係数です。最初は、値の組み合わせが合法かどうか、そして問題がある場合、例外がスローされるかどうかを判断します。重要なのは、以下の容量の計算です。その論理は、初期容量よりも2の最小の電力を計算することです。実際、目的は、容量を指定された初期容量以上にすることですが、この値は2の指数関数的倍数でなければなりません。これは重要な問題です。この理由は、主にハッシュ値をマッピングするためです。まず、ハッシュマップのハッシュメソッドを見てみましょう。
final int hash（オブジェクトk）{int h = 0; if（usealthashing）{if（k instanceof string）{return sun.misc.hashing.stringhash32（（string）k）; } h = hashseed; } h ^= k.hashcode（）; //この関数は、各ビット位置で//定数倍数によって異なるハッシュコードが境界のある//衝突の数（デフォルト負荷係数で約8）を持っていることを保証します。 h ^ =（h >>> 20） ^（h >>> 12）; return h ^（h >>> 7） ^（h >>> 4）;} static int indexfor（int h、int length）{return h＆（length-1）;}Hash（）メソッドは、キーのハッシュ値を再計算し、比較的複雑なビット操作を使用します。特定のロジックがわかりません。とにかく、それは間違いなくより良い方法であり、紛争や何かを減らすことができます。
以下のindexfor（）は、ハッシュ値に基づいてハッシュテーブルの要素の添え字です。一般に、ハッシュテーブルでは、ハッシュ値を使用してテーブルの長さを変調します。長さ（つまり、容量）が2のパワーである場合、h＆（長さ1）は同じ効果です。さらに、2のパワーは偶数でなければなりません。その後、1を減算した後、それは奇数であり、バイナリの最後のビットは1でなければなりません。その後、h＆（長さ1）の最後のビットは1または0であり、均等にハッシュすることができます。長さが奇数の場合、長さ1は偶数で、最後のビットは0です。この時点で、h＆（長さ1）の最後のビットは0であり、結果のサブスクリプがすべて偶数であるため、スペースの半分が無駄になります。したがって、ハッシュマップの容量は2のパワーでなければなりません。デフォルトのdefault_initial_capacity = 16およびmaximix_capacity = 1 << 30はどちらもこのようなものであることがわかります。
エントリオブジェクト
ハッシュマップのキー価値ペアは、ハッシュマップの内部クラスであるエントリオブジェクトにカプセル化されます。その実装を見てみましょう。
静的クラスエントリ<k、v>はmap.entry <k、v> {final k key; v値;エントリ<k、v> next; int hash; entry（int h、k k、v v、entry <k、v> n）{value = v; next = n; key = k;ハッシュ= h; } public final k getKey（）{return key; } public final v getValue（）{return値; } public final v setValue（v newValue）{v oldValue = value; value = newValue; OldValueを返します。 } public final boolean equals（object o）{if（！（o instanceof map.entry））return false; map.entry e =（map.entry）o;オブジェクトk1 = getKey（）;オブジェクトk2 = e.getKey（）; if（k1 == k2 ||（k1！= null && k1.equals（k2）））{object v1 = getValue（）;オブジェクトv2 = e.getValue（）; if（v1 == v2 ||（v1！= null && v1.equals（v2）））trueを返します。 } falseを返します。 } public final int hashcode（）{return（key == null？0：key.hashcode（）） ^（value == null？0：value.hashcode（））; } public final String toString（）{return getKey（） + "=" + getValue（）; } void recordAccess（hashmap <k、v> m）{}}このクラスの実装はシンプルで理解しやすいです。 getKey（）、getValue（）などのメソッドが呼び出しに提供されます。平等を決定するには、キーと値の両方が等しい必要があります。
操作を入れます
あなたがそれを取得する前に最初に置くので、最初にput（）メソッドを見てください：
public v put（k key、v value）{if（key == null）return putfornullkey（value）; int hash = hash（key）; int i = indexfor（hash、table.length）; 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）; OldValueを返します。 }} modcount ++; Addentry（Hash、Key、Value、I）; nullを返します;}この方法では、最初にキーがnullかどうかを決定します。はいの場合、putfornullkey（）メソッドを呼び出します。つまり、ハッシュマップによりキーをnullにすることができます（実際、値は可能です）。 nullでない場合は、ハッシュ値を計算し、表に添え字を取得します。次に、対応するリンクリストに移動して、同じキーがすでに存在するかどうかを照会します。既に存在する場合、値は直接更新されます。それ以外の場合は、挿入のためにaddentry（）メソッドを呼び出します。
putfornullkey（）メソッドをご覧ください。
private v putfornullkey（v value）{for（entry <k、v> e = table [0]; e！= null; e = e.next）{if（e.key == null）{v oldvalue = e.value; e.value = value; E.RecordAccess（This）; OldValueを返します。 }} modcount ++; addentry（0、null、value、0）; nullを返します;}キーがnullである場合、値が存在する場合は値が更新されます。
以下は、addentry（）メソッドの実装です。
void addentry（int hash、k key、v value、int bucketindex）{if（（size> = threshold）&&（null！= table [backetindex]））{resize（2 * table.length）; hash =（null！= key）？ハッシュ（キー）：0; BucketIndex = indexfor（hash、table.length）; } createentry（hash、key、value、bucketindex）;} void createentry（int hash、k key、v value、int bucketindex）{entry <k、v> e = table [bucketindex];表[BucketIndex] = new entry <>（hash、key、value、e）;サイズ++;}まず、容量を拡張するか（容量を拡大するとサブスクリプト値が再計算され、要素がコピーされます）かどうかを判断し、次にアレイsubscriptを計算し、最後にcreateentry（）のヘッダー挿入方法を使用して要素を挿入します。
操作を取得します
public v get（object key）{if（key == null）return getfornullkey（）;エントリ<k、v> entry = getEntry（key）; null ==エントリを返しますか？ null：entry.getValue（）;} private v getFornullkey（）{for（entry <k、v> e = table [0]; e！= null; e = e.next）{if（e.key == null）return e.value; } return null;}最終エントリ<k、v> getEntry（object key）{int hash =（key == null）？ 0：ハッシュ（キー）; for（entry <k、v> e = table [indexfor（hash、table.length）]; e！= null; e = e.next）{object k; if（e.hash == hash &&（（k = e.key）== key ||（key！= null && key.equals（k）））return e; } nullを返します;}これはput（）よりも簡単です。また、キーがnullであるかどうかを判断し、リンクリストのトラバーサルクエリを決定する必要があります。
パフォーマンスの最適化
HashMapは、すべてのJavaプログラムのどこにでも見ることができる効率的で普遍的なデータ構造です。最初に基本的な知識を紹介しましょう。ご存知かもしれませんが、HashMapはHashCode（）およびEquals（）キーのメソッドを使用して、値を異なるバケットに分割します。バケットの数は通常、マップ内のレコードの数よりわずかに大きいため、各バケットには値が少なくなります（できれば1つ）。キーを検索すると、バケツ（HashCode（）を使用してバケットの数をmodulo）と一定の時間で探しているオブジェクトをすばやく見つけることができます。
あなたはすでにこれらすべてを知っている必要があります。また、ハッシュの衝突がハッシュマップのパフォーマンスに壊滅的な影響を与える可能性があることも知っているかもしれません。複数のHashCode（）値が同じバケットに分類される場合、これらの値はリンクリストに保存されます。最悪の場合、すべてのキーが同じバケットにマッピングされるため、ハッシュマップはリンクリストに縮退します - 検索時間はO（1）からO（n）になります。最初に、通常の状況下でJava 7とJava 8のHashmapのパフォーマンスをテストしましょう。 HashCode（）メソッドの動作を制御するために、次のようにキークラスを定義します。
クラスキー実装comparable <key> {private final int value; key（int value）{this.value = value;}@overridepublic int compareto（key o）{return integer.compare（this.value、o.value）;}@overridepublic boolean equals（object o）{of = = return null; o.getClass（））return false; key key =（key）o; return値== key.value;}@overridepublic int hashcode（）{return value;}}キークラスの実装はかなり標準的です。Equals（）メソッドを書き換え、かなり適切なHashCode（）メソッドを提供します。過度のGCを避けるために、毎回再び作成し始めるのではなく、不変のキーオブジェクトをキャッシュしました。
クラスキー実装Camparable <key> {public class keys {public static final int max_key = 10_000_000; private static final key = new key [max_key]; static {for（int i = 0; i <max_key; ++ i）{keys_cache [i] = newキー（i） keys_cache [value];}これで、テストを開始できます。当社のベンチマークは、連続キー値を使用して、異なるサイズのハッシュマップを作成します（乗数10、100万から100万）。テストでは、キーを使用して、さまざまなサイズのハッシュマップにかかる時間を検索および測定します。
com.google.caliper.paramをインポート;インポートcom.google.caliper.runner; Import com.google.caliper.simplebenchmark; public class mapbenchmark extends {private hashmap <key、integer> map; @paramprivate int mapsize; hashmap <>（mapsize）; for（int i = 0; i <mapsize; ++ i）{map.put（keys.of（i）、i）;}} public void timemapget（int reps）{for（int i = 0; i <reps; i ++）{map.get（keysize）;}}}}}}}興味深いことに、この単純なHashmap.get（）では、Java 8はJava 7よりも20％高速です。全体的なパフォーマンスも非常に優れています。ハッシュマップには100万件の記録がありますが、単一のクエリは10ナノ秒未満で、私の機械で約20 cpuサイクルしかかかりませんでした。とても衝撃的です！しかし、これは私たちが測定したいものではありません。
悪いキーがあるとし、常に同じ値を返します。これは最悪のシナリオであり、ハッシュマップをまったく使用しないでください。
クラスキー実装comparable <key> {//...@overridepublic int hashcode（）{return 0;}}Java 7の結果が予想されます。ハッシュマップのサイズが大きくなるにつれて、get（）メソッドのオーバーヘッドはますます大きくなります。すべてのレコードは同じバケツの超長リンクリストにあるため、平均1つのレコードを検索するには、リストの半分を横断する必要があります。したがって、その時間の複雑さがO（n）であることが図から見ることができます。
ただし、Java 8のパフォーマンスははるかに優れています！それはログカーブなので、そのパフォーマンスは桁違いに優れています。重度のハッシュ衝突の最悪のシナリオにもかかわらず、この同じベンチマークは、o（logn）のJDK8で時間の複雑さを持っています。 JDK 8だけの曲線を見ると、より明確になります。これは対数線形分布です。
ここでは大きなOシンボルが使用されているにもかかわらず、なぜこのような大きなパフォーマンス改善があるのですか（Big Oは漸近上の上限を説明しています）。実際、この最適化はJEP-180で言及されています。バケツのレコードが大きすぎる場合（現在treeify_threshold = 8）、ハッシュマップはそれを特別なTreemap実装に動的に置き換えます。これにより、o（logn）が改善され、o（n）が悪くなります。どのように機能しますか？正面に競合があるキーに対応するレコードは、単にリンクされたリストに追加され、これらのレコードはトラバーサルによってのみ見つけることができます。ただし、このしきい値を超えた後、ハッシュマップは、ハッシュ値をツリーの分岐変数として使用して、リストをバイナリツリーにアップグレードし始めます。 2つのハッシュ値が等しくないが、同じバケットを指している場合、大きなバケットが右のサブツリーに挿入されます。ハッシュ値が等しい場合、ハッシュマップは、キー値が同等のインターフェイスによって最適に実装され、順番に挿入できることを期待しています。これは、Hashmapのキーには必要ありませんが、もちろん実装されている場合は最高です。このインターフェイスが実装されていない場合、重度のハッシュ衝突が発生した場合にパフォーマンスの改善を達成することを期待してはなりません。
このパフォーマンスの改善の使用は何ですか？たとえば、悪意のあるプログラムは、ハッシュするアルゴリズムを使用していることを知っている場合、多数のリクエストを送信して、深刻なハッシュ衝突をもたらす可能性があります。その後、これらのキーに絶えずアクセスすると、サーバーのパフォーマンスに大きな影響を与える可能性があり、サービス攻撃の拒否（DOS）につながります。 JDK 8のO（n）からO（logn）への跳躍は、同様の攻撃を効果的に防止すると同時に、ハッシュマップ性能の予測可能性をわずかに向上させることができます。この改善が最終的に上司にJDK 8へのアップグレードに同意するよう説得することを願っています。
テストに使用される環境は、64ビットWindows 8.1システムで実行されているデフォルトのJVMパラメーターを使用して、Intel Core I7-3635QM @ 2.4 GHz、8GBメモリ、SSDハードディスクです。
要約します
HashMapの基本的な実装は上記で分析されたとおりであり、最後に概要が作成されます。