HashmapとHashsetは、Javaコレクションフレームワークの2人の重要なメンバーです。 HashMapはMAPインターフェイスの一般的な実装クラスであり、HashsetはSETインターフェイスの共通の実装クラスです。 HashMapとHashsetによって実装されたインターフェイス仕様は異なりますが、その基礎となるハッシュストレージメカニズムはまったく同じであり、Hashset自体でもHashmapを使用して実装します。
実際、ハッシュセットとハッシュマップには多くの類似点があります。ハッシュセットの場合、システムはハッシュアルゴリズムを使用してコレクション要素のストレージ位置を決定し、コレクション要素を迅速に保存および取得できるようにします。ハッシュマップの場合、システムのキー値は全体として処理され、システムは常にハッシュアルゴリズムに基づいてキー値のストレージ位置を計算し、マップのキー値ペアを迅速に保存および取得できるようにします。
コレクションストレージを導入する前に、コレクションはJavaオブジェクトを保存すると主張していますが、実際にはJavaオブジェクトをセットコレクションに入れるのではなく、セットコレクションのこれらのオブジェクトへの参照のみを保持することを指摘する必要があります。つまり、Javaコレクションは、実際には実際のJavaオブジェクトを指す複数の参照変数のコレクションです。
1。ハッシュマップの基本機能
JDKソースコードHashmap.classでコメントを読んだ後、多くのハッシュマップ機能を要約できます。
HashMapは、キーと値の両方をnullにすることができますが、ハッシュテーブルはnullになります。
Hashmapはスレッドインセキュアですが、ハッシュテーブルはスレッドセーフです
ハッシュマップの要素の順序は必ずしも同じではなく、同じ要素の位置も時間とともに変化する可能性があります（サイズの場合）
ハッシュマップを通過する時間の複雑さは、その容量と既存の要素の数に比例します。横断の効率を確保する場合、初期容量を高く設定しすぎたり、バランス係数を低すぎたりすることはできません。
以前の関連リストと同様に、ハッシュマップはスレッドにインスケイであるため、反復プロセス中にイテレーターがコンテナ構造を変更しようとすると、フェイルファストが生成されます。同期されたハッシュマップは、collections.synchronizedMap（hashmap）を介して取得できます
2。ハッシュテーブルデータ構造分析
ハッシュテーブル（ハッシュテーブル、ハッシュテーブル）は、キーワードに基づいてメモリストレージの場所に直接アクセスするデータ構造です。つまり、ハッシュテーブルは、キーワードとストレージアドレスの間に直接マッピングを確立します
以下の図に示すように、キーはハッシュ関数を介してバケツのインデックス位置を取得します。
ハッシュ関数を介してインデックスを取得すると、必然的に同じ状況、つまり競合が発生します。競合を解決する方法は次のとおりです。
オープンアドレス指定：この方法の基本的な考え方は、競合に遭遇したときに順番にテーブルの下の位置をスキャンし、無料のものがある場合は記入することです。特定のアルゴリズムはもう説明されません。以下は概略図です。
個別のチェーン：この方法の基本的なアイデアは、競合に遭遇したときにリンクされたリストに同じインデックス値を持つエントリを一緒に描くことです。特定のアルゴリズムはもう説明されません。以下は概略図です。
JDKのハッシュマップでの競合を解決する方法は、個別のチェーン法を使用することです。
3。ハッシュマップソースコード分析（JDK1.7）
1。HashMap読み取りおよび書き込み要素
エントリ
Hashmapに保存されている要素は、入力タイプです。ソースコードのソースエントリコードを以下に示します。
静的クラスエントリ<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; } //キーの取得と設定のメソッド、値は省略され、GETおよびセット操作は後続のイテレータで使用されます...パブリックファイナルブール等等（オブジェクト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を返します。 } //ここで、キーのハッシュコードと値のハッシュコードを実行または操作して、パブリックファイナルint hashcode（）{return objects.hashcode（getKey（）） ^ objects.hashcode（getValue（））; } public final String toString（）{return getKey（） + "=" + getValue（）; } /** *このメソッドは、エントリ内の値が、ハッシュマップに既に *既に *であるキーkの呼び出し（k、v）によって上書きされるたびに呼び出されます。 * / void recordAccess（hashmap <k、v> m）{} / ** *この方法は、エントリがテーブルから削除されるたびに呼び出されます。 */ void recordremoval（hashmap <k、v> m）{}}エントリには、キー、値、ハッシュ、次のエントリへの参照が含まれます。これは単一のリンクされたリストであり、Map.entryインターフェイスを実装していることは明らかです。
RecordAcess（Hashmap <k、v>およびRecordRemoval（Hashmap <k、v>）はHashmapで実装されていません。ただし、Linkedhashmapの2つの方法はLRUアルゴリズムの実装に使用されます。
取得：要素を読み取り、Hashmapから対応するエントリを取得します。以下は、GETのソースコードです。
public v get（object key）{//キーがnull if（key == null）return getfornulkey（）; //キーエントリエントリに基づいてエントリを見つけます<K、v> entry = getEntry（key）; null ==エントリを返しますか？ null：entry.getValue（）; }getFornullKeyソースコード
private v getFornullKey（）{if（size == 0）{return null; } //（entry <k、v> e = table [0]; e！= null; e = e.next）{if（e.key == null）return e.value; } nullを返します。 }キーヌルを使用したエントリは表[0]に保存されますが、表[0]の競合チェーンには必ずしもnullとしてキーがあるわけではないため、通過する必要があります。
キーに従ってエントリを取得します：
最終エントリ<k、v> getEntry（オブジェクトキー）{if（size == 0）{return null; } int hash =（key == null）？ 0：ハッシュ（キー）; //ハッシュを介してテーブル内のインデックス位置を取得し、競合するリンクリストをトラバースして、（エントリ<k、v> e = table [indexfor（hash、table.length）]; e！= null; e = edext）{object k; if（e.hash == hash &&（（k = e.key）== key ||（key！= null && key.equals（k）））return e; } nullを返します。 }上記は、ハッシュマップがエントリとそのソースコードを読み取るプロセスです。時間の複雑さo（1）
プット：要素を書き込みます
ハッシュマップでのプット操作は、プット操作中にハッシュマップ拡張操作が行われるため、比較的複雑です。
新しい要素が書かれている場合、Hashmapで要素を書き込む鍵がある場合、値を置き換える操作が実行されます。これは更新に相当します。プットソースコードは次のとおりです。
public v put（k key、v value）{//テーブルが空の場合、if（table == empty_table）のsize {inflateTable（threshold）; } // null if（key == null）return putfornullkey（value）のようにキーを入力します。 //ハッシュを生成して、インデックスインデックスのマッピングを取得しますint hash = hash（key）; int i = indexfor（hash、table.length）; //現在のインデックスの競合チェーンを透過して、対応するキーがあるかどうかを見つけます（エントリ<k、v> e = table [i]; e！= null; e = e.next）{object k; //対応するキーが存在する場合、oldvalueを置き換えてoldvalueを返します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を返します。 }AddentryとCreateEntryソースコード：
void addentry（int hash、k key、v value、int bucketindex）{//新しいエントリを挿入する前に、最初に現在のハッシュマップのサイズとそのしきい値サイズを判断し、if（（size> =しきい値）&&（null！= table [bucketindex]））{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 backetindex）{entry <k、v> e = table [bucketindex]; //ヘッド挿入方法、新しく書かれたエントリが、現在のインデックス位置の競合チェーンの最初のエントリの前面に挿入されます。表[BucketIndex] = new entry <>（hash、key、value、e）;サイズ++; }上記は、ハッシュマップとそのソースコードへのエントリを書き込むプロセスです。時間の複雑さo（1）
削除要素を削除：
最終エントリ<k、v> removeEntryforkey（オブジェクトキー）{if（size == 0）{return null; } //キーに従ってハッシュ値を計算し、インデックスint hash =（key == null）を取得しますか？ 0：ハッシュ（キー）; int i = indexfor（hash、table.length）; //リンクリストを削除し、2つのポインターを定義し、事前は前身エントリを表します<k、v> prev = table [i];エントリ<k、v> e = prev; //競合チェーンをtranstraightし、すべてのキーを削除しますwhile（e！= null）{entry <k、v> next = e.next;オブジェクトk; //見つかった場合（e.hash == hash &&（（k = e.key）== key ||（key！= null && key.equals（k）））{modcount ++;サイズ - ; //最初のノードを見つけることは、（prev == e）table [i] = next;の場合、削除するノードです。 else prev.next = next; E.RecordRemoval（This）; eを返す; } prev = e; e = next; } return e; }上記は、エントリとそのソースコードを削除するハッシュマップのプロセスです。時間の複雑さo（1）
2。ハッシュマップハッシュ原理（ハッシュ関数）
ハッシュマップでのハッシュ関数の実装は、ハッシュ（オブジェクトk）とindexfor（int h、int length）を介して行われます。以下のソースコードを見てみましょう。
final int hash（object k）{int h = hashseed; if（0！= h && k instanceof string）{sun.misc.hashing.stringhash32（（string）k）; } h ^= k.hashcode（）; //この関数は、各ビット位置で//定数倍数によって異なるハッシュコードが境界のある//衝突の数（デフォルト負荷係数で約8）を持っていることを保証します。 //競合の可能性を減らすためh ^ =（h >>> 20） ^（h >>> 12）; return h ^（h >>> 7） ^（h >>> 4）; }インデックスインデックスソースコードを取得します：
static int indexfor（int h、int length）{// assert integer.bitcount（length）== 1： "長さは2の非ゼロパワーでなければなりません"; h＆（length-1）;を返します。 }ハッシュマップは、ハッシュ関数を介して[0、table.length]の間隔内でインデックスにキーをマップします。通常、インデックス作成方法には2種類あります。
ハッシュ（キー）％table.length。長さは素数でなければなりません。 Hashtableは、この実装をJDKで使用します。
素数を使用する具体的な理由から、関連するアルゴリズムのデータ証明を見つけることができますが、これはここには記載されていません。
Hash（key）＆（table.length -1）ここで、長さは2指数パワーに必要です。 JDKのHashMapは、この実装方法を使用します。
長さのサイズは2つの指数時間であるため、ハッシュ（key）＆（table.length -1）は常に[0、長さ-1]の間になります。ただし、これを単独で行うと、Javaのハッシュコードの値が32ビットであるため、競合に大きな問題が発生します。ハッシュマップの容量が小さい場合、たとえば16の場合、XOR操作を行うと、高ビットが常に破棄されますが、ビット操作が低い後、競合の確率が増加します。
したがって、競合の発生の可能性を減らすために、コードでは多くのビット操作と排他的または操作が実行されます。
3。ハッシュメモリの割り当て戦略
メンバー変数容量とLoadFactor
必要な容量容量は、ハッシュマップの2の指数倍数であり、デフォルト容量は1 << 4 = 16です。ハッシュマップにはバランス係数（荷重ファクター）もあります。過度に高い要因はストレージスペースを削減しますが、検索の時間（ハッシュマップでのプットおよび取得方法を含むルックアップ）が増加します。 LoadFactorのデフォルト値は0.75です。これは、時間の複雑さと空間の複雑さを比較検討することによって与えられる最適な値です。
static final int default_initial_capacity = 1 << 4; //別名16 Static final int maximion_capacity = 1 << 30;静的最終float default_load_factor = 0.75f;
ハッシュマップコンストラクター
ハッシュマップの構築は、容量とLoadFactorの初期値を設定することです
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）; this.loadfactor = loadfactor;しきい値= initialcapacity; init（）; }私は前に、ハッシュマップの容量は2の指数時間でなければならず、コンストラクターに制限はないと言いました。では、容量値が2の指数時間であることを確認するにはどうすればよいですか？
操作中に、ソースコードは、現在のハッシュテーブルが空のテーブルであるかどうかを判断します。もしそうなら、インフレータブルに電話してください（int tosize）
private void inflateTable（int tosize）{// 2> = tosize int capitial = rounduppopowerof2（tosize）の電力を見つける;しきい値=（int）math.min（容量 * loadfactor、maxim_capacity + 1）;表=新しいエントリ[容量]; inithashseedasneeded（容量）; }rounduppopowerof2は、指定されたパラメーターよりも大きい2のnパワーを取得することです
private static int rounduptopowerof2（int number）{// assert number> = 0： "番号は非陰性でなければなりません"; return number> = maximion_capacity？ Maximum_capacity ：（番号> 1）？ integer.highestonebit（（number -1）<< 1）：1; }integer.hightestonebit（int）は、指定されたパラメーターの最高ビットを保持し、残りの0を変更する操作です。簡単に言えば、パラメーターINTを最大2以下以下に変更することです。
数値が2のn電力の場合、最高ビットはDectrement 1後の元の2番目の高ビットにあり、その後、残り1ビットをシフトして、最高のビット位置に配置されます。数値が2のn電力でない場合、最高のビットは、1ビットを残して1ビットを左にシフトした後、依然として元の最高のビットです。
容量の拡大：
Hashmapは、操作を行うとサイズ変更動作があります。特定のソースコードは次のとおりです。
void resize（int newcapacity）{entry [] oldtable = table; int oldcapacity = oldtable.length; //ハッシュテーブルは最大容量に達しました。1<< 30 if（oldcapacity == maximix_capacity）{threhold = integer.max_value;戻る; } entry [] NewTable = new Entry [NewCapacity]; // oldtableのエントリをNewtableに転送しますテーブル= newTable; //しきい値のしきい値=（int）math.min（newcapacity * loadfactor、maxim_capacity + 1）; } void転送（entry [] newtable、boolean rehash）{int newcapacity = newtable.length; // transweep oldtable for（entry <k、v> e：table）{// transweep競合チェーンwhile（null！= e）{entry <k、v> next = e.next; if（rehash）{//ハッシュ値を再計算e.hash = null == e.key？ 0：ハッシュ（E.Key）; } int i = indexfor（e.hash、newcapacity）; //ヘッドに要素をヘッドに挿入します。ヘッダー挿入方法e.next = newTable [i]; newtable [i] = e; e = next; }}}上記は、ハッシュマップメモリ割り当てのプロセス全体です。要約すると、Hashmapがエントリを置くと、現在の容量としきい値サイズをチェックして、容量を拡大するかどうかを選択します。各拡張のサイズは2 * table.lengthです。拡張期間中、ハッシュ値をInithashseedasneededに基づいて再計算する必要があるかどうかを判断します。
4。HashmapIterator
HashmapのValueTiterator、Keyiterator、Entryiteratorなどの反復器はすべてハシテレーターに基づいています。ソースコードを見てみましょう。
プライベートアブストラクトクラスハシテレーター<e> Iterator <e> {entry <k、v> next; //次のエントリはint expectModCountを返します。 //ファーストフェイルINTインデックスの場合; //現在のスロット、テーブルインデックスエントリ<k、v> current; //現在のエントリHashiterator（）{expectionModCount = modCount; //ハッシュテーブルで最初のエントリを見つけます（size> 0）{entry [] t = table; while（index <t.length &&（next = t [index ++]）== null）; }} public final boolean hasnext（）{return next！= null; } final entry <k、v> nextentry（）{// hashmapは非スレッドセーフであり、移動する場合、テーブル構造の変更があるかどうかを決定します（modcount！= expectsModCount）新しいconcrurentModificationexception（）;エントリ<k、v> e = next; if（e == null）新しいnosuchelementexception（）; if（（next = e.next）== null）{//次のエントリエントリ[] t = table; while（index <t.length &&（next = t [index ++]）== null）; } current = e; eを返す; } public void remove（）{if（current == null）新しいIllegalStateException（）; if（modcount！= expectsModCount）を新しいconcurrentModificationException（）;オブジェクトk = current.key; current = null; hashmap.this.removeentryforkey（k）; expectsModCount = modCount; }}キー、バリュー、エントリの3つの反復器はカプセル化されており、キーズセット、値、エントリセットの3つのコレクションの視点になります。これらの3つのコレクションの視点は、HashMapの除去、Removeall、および明確な操作をサポートしており、AddおよびAddall操作をサポートしていません。