HashMapは、ハッシュテーブルに基づくMAPインターフェイスの実装であり、すべてのオプションのマッピング操作を提供し、同期からヌル値とヌル構造を可能にし、マッピング順序の保証なしです。 Hashmapの実装原則を記録しましょう。
ハッシュマップ内部ストレージ
ハッシュマップでは、すべてのキー値ペアの関係は、一連の瞬時変数テーブル（バケットとも呼ばれる）を維持することにより保存されます。バケットは、エントリオブジェクトの配列です。バケットサイズは必要に応じてサイズを変更でき、長さは2のパワーでなければなりません。次のコード：
/ ***空のエントリアレイ、バケットのデフォルト値*/静的最終エントリ<？、？> [] empty_table = {}; / ***バケツ、必要に応じてサイズを変更しますが、2*/一時的なエントリ<k、v> [] table =（entry <k、v> []）empty_tableのパワーでなければなりません。初期容量と負荷係数
HashMapには、パフォーマンス、初期容量、負荷係数に影響する2つのパラメーターがあります。容量はハッシュテーブルのバケット数、初期容量はハッシュテーブルの作成時の容量のみであり、負荷係数は、ハッシュテーブルが自動的に増加する前にフルに到達できるスケールです。ハッシュテーブルのエントリの数が負荷係数と現在の容量の積を超える場合、ハッシュテーブルを再ハッシュする必要があり（つまり、内部データ構造を再構築します）、再構築は現在の容量の2倍で作成されます。初期容量と負荷係数は、コンストラクターを介して設定できます。デフォルトの初期容量は16のエントリ、最大容量は2^30エントリ、デフォルトの負荷係数は0.75です
バケツは、水を貯めるバケツのようなものです。デフォルトの初期貯蔵容量は16単位の水です。水を16*0.75に注ぐと、次回データが追加されると、容量は最初に32ユニットに拡張されます。 0.75は負荷係数であり、バケットを作成するときに初期容量と負荷係数を設定できます。バケットの最大容量は、30の電力に対する2ユニットの水です。初期容量設定の数が最大容量よりも大きい場合、最大容量が優先します。拡大すると、最大容量以上が大きい場合は直接返されます。
以下は、ハッシュマップのソースコードの一部であり、デフォルトの初期容量、負荷係数、およびその他の定数を定義します。
/ ** *デフォルトの初期容量は2のパワーでなければなりません。 */ static final int default_initial_capacity = 1 << 4; //別名16/ ***最大容量、初期容量がコンストラクターパラメーターを介して最大容量よりも大きい場合、容量は初期容量としても使用されます*は2の電力であり、30番目の電力2*/ static final int maximince_capacity = 1 << 30; / ***デフォルトの負荷係数は、コンストラクターで指定できます*/静的最終float default_load_factor = 0.75f; / ***バケットが初期化されていない場合*/静的最終エントリ<？、？> [] empty_table = {}; / ***バケツ、すべてのキー価値ペアエントリを保存し、必要に応じてサイズ変更できます。 /***マップ内のキー価値ペアの数、サイズは追加または削除されるたびに+1または-1操作になります。 */一時的なINTサイズ。 /** *サイズする必要がある負荷値の重要な値は次のとおりです。（容量 *荷重係数）。各サイズ変更後、新しい容量は新しい容量を使用して計算されます。 * @serial */ // table == empty_tableの場合、これは//テーブルが膨らんだときに作成される初期容量です。 intしきい値; / ** *荷重係数、コンストラクターで指定されていない場合、デフォルトの負荷係数が使用されます。 /** *ハッシュマップ構造の変更、ハッシュマップのマップの数を変更するか、構造が変更されたら内部構造を変更します（たとえば、 * rehashメソッド、内部データ構造を再構築します）。このフィールドは、ハッシュマップコレクションビューで生成されたイテレーターで使用されます。初期容量と負荷係数のパフォーマンス調整
通常、デフォルトの負荷係数（0.75）は、時間とスペースのコストの妥協を求めています。負荷係数は高すぎますが、クエリコストも増加します（これは、GETおよびPUT操作を含むほとんどのハッシュマップ操作に反映されます）。初期容量を設定する場合、マップに必要なエントリの数とその負荷係数を考慮する必要があります。初期容量が荷重係数で割ったエントリの最大数よりも大きい場合、再ハッシュ操作は発生しません。
多くのマッピング関係をハッシュマップインスタンスに保存する場合、それを十分に大きく初期容量で作成すると、テーブルの容量を増やすためにオンデマンドで自動リハッシュ操作の実行に対してマッピング関係がより効率的に保存されます。
以下は、ハッシュマップデータ構造を再構築するコードです。
void resize（int newcapacity）{entry [] oldtable = table; int oldcapacity = oldtable.length; if（oldCapacity == Maximing_Capacity）{//容量が最大制限に達した場合、負荷値を設定し、しきい値= integer.max_valueに直接戻します。戻る; } //データエントリ[] NewTable = new Entry [NewCapacity]を保存する新しいテーブルを作成します。 //古いテーブルから新しいテーブルにデータを転送すると、この手順は転送に多くの時間がかかります（NewTable、InithashseedasNeeded（NewCapacity））;テーブル= newTable; //最後に、次のサイズのしきい値=（int）math.min（newcapacity * load_capacity + 1）;}の負荷値を設定します。ハッシュマップ構築方法
4番目の構築方法は、既存のマップを使用して新しいハッシュマップを作成することです。後でそれについて話しましょう。実際、最初の3つの構造方法は、2つのパラメーターを備えた最後の3番目の方法で呼び出されます。パラメーターが渡されない場合、デフォルト値が使用されます。コードは次のとおりです。
/** *デフォルトの初期容量 *（16）とデフォルトの負荷係数（0.75）を使用して、空の<tt> hashmap </tt>を構築します。 */ public hashmap（）{this（default_initial_capacity、default_load_factor）; } /** *指定された初期 *容量とデフォルトの負荷係数（0.75）を使用して、空の<tt> hashmap < /tt>を構築します。 * * @param initialcapacity初期容量。 *初期容量が負の場合、@Throws IllegalargumentException。 */ public hashmap（int initialcapacity）{this（initialcapacity、default_load_factor）; } /** *指定された初期 *容量と負荷係数を使用して、空の<tt> hashmap < /tt>を構築します。 * * @param initialcapacity初期容量 * @param loadfactorロードファクター * @throws初期容量が負の場合 * @throws load係数が非陽性 */ public hashmap（int initial -capacity、float loadfactor）{if（initialcapacity <0）show show new Illegalargumentexception（ " if（initialcapacity> maximion_capacity）hiritioncapacity = maxim_capacity; if（loadFactor <= 0 || float.isnan（loadFactor））を投げて、新しいIllegalargumentException（ "違法負荷係数：" +loadFactor）; this.loadfactor = loadfactor;しきい値= initialcapacity; init（）; }上記からわかるように、コンストラクターでは、初期容量が最大容量よりも大きい場合、最大容量は直接置き換えられます。
PUTメソッド
次に、ハッシュマップのより重要な部分を見てみましょう
/***このマップでは、指定された値と指定されたビルドが関連付けられています。マップにキーのマッピング関係が以前に含まれていた場合、古い値が交換された場合** @paramは関連するキーを指定します* @paramは関連する値を指定します* @ @returnキーに関連付けられた古い値を指定します。 {inflateTable（しきい値）; } 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を返します。 }1。最初に、PUTメソッドでは、最初にバケットがデフォルトの非初期化状態にあるかどうかを判断します。初期化されていない場合は、膨張可能な方法を呼び出して初期化し、パラメーターキーがnullかどうかを判断します。 nullの場合は、putfornullkeyを呼び出して、keyをnullとしてキーとともに配置します。 PutFornullKeyメソッドは、実際には次のステップ3と同じです。ただし、nullが最初であるため、キーを持つデータのデフォルトのストレージ位置、つまりデフォルトのサブスクリプトは0です。
2。キーがnullでない場合は、hash（）メソッドを呼び出して、キーのハッシュ値を取得します。ハッシュ値とバケツの長さに基づいて、キーをバケットに配置できる位置を計算できます。
3.次はエントリオブジェクトに属性があり、同じハッシュ値の要素を保存するために一方向リンクリストを形成できます。したがって、キーのハッシュ値が計算されると、ストレージの位置も繰り返されます。ストレージの場所の要素と要素の次の属性リストが、指定されたキーとキーのハッシュ値とまったく同じかどうかを判断してください。完全に一貫したものがある場合、それは既に存在し、古い値を置き換え、古い値を返品値として直接返すことを意味します。
4。構造修正の数を1で増やします
5. Addentryメソッドを呼び出して、新しいキー値ペアをハッシュマップに追加します。 Addentityメソッドは、最初に、現在のエントリデータが負荷値（バケット *荷重係数の容量）とバケットの指定位置がnullではないかどうかを決定します。すでにより大きく、指定された位置がヌルでない場合、調整バケットの容量は現在の容量の2倍です。調整バケットの容量は、上記の初期容量と負荷係数のパフォーマンス調整ディレクトリを参照しています。ハッシュ値を再計算し、ストレージの場所を計算します。 CreateEntryメソッドを呼び出して、バケットに保存してください
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 backetindex）{entry <k、v> e = table [bucketindex];表[BucketIndex] = new entry <>（hash、key、value、e）;サイズ++; } /***新しいエントリを作成するためのエントリコンストラクターメソッド。 */ entry（int h、k k、v v、entry <k、v> n）{value = v; next = n; key = k;ハッシュ= h; }6。CreateEntryメソッドでは、最初に指定された場所でエントリを取得し、次に新しいエントリを生成します。エントリを生成するときは、元のエントリを新しく生成されたエントリの次のプロパティに保存し（エントリ構築方法を参照）、指定された場所のエントリを新しく生成した場所に置き換えます。
新しいエントリを追加するときは、ハッシュ値を計算する必要があり、長さが十分でない場合、長さを調整する必要があるためです。計算されたストレージの場所に要素がある場合、リンクされたリストを保存する必要があるため、HashMapを使用して新しい操作を追加する効率は高すぎません。
メソッドを取得します
まず、GETメソッドのソースコードを見てみましょう。
/***指定されたキーによってマッピングされた値を返します。このマップにこのキーのマッピング関係が含まれていない場合、null *を返すNULL値を返します。必ずしもマップにキーのマッピングが含まれていないことを意味するわけではなく、マッピングをnullに変更する可能性もあります。 ContainsKey操作を使用して、これら2つの状況を区別できます * @see＃put（object、object） */ public v get（object key）{if（key == null）return getFornullkey（）;エントリ<k、v> entry = getEntry（key）; null ==エントリを返しますか？ null：entry.getValue（）; }最終エントリ<k、v> getEntry（オブジェクトキー）{if（size == 0）{return null; } 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を返します;}GETメソッドの実装は簡単で、以下はいくつかのステップです。
GETのソースコードを見ると、GETメソッドがキーのハッシュ値とバケットの長さを介してストレージの場所を計算することがわかります。基本的に、探している要素を見つけることができます。ハッシュ値を繰り返していくつかのキーを横断しても、非常に高速です。ハッシュ値は比較的ユニークであるため、ハッシュマップは検索に非常に高速です。
ハッシュマップの鍵としてのカスタムオブジェクト
クラスユーザー{// id番号保護されたint idnumber; public user（int id）{idnumber = id; }} public class testuser {public static void main（string [] args）{map <user、string> map = new hashmap <user、string>（）; for（int i = 0; i <5; i ++）{map.put（new user（i）、 "name："+i）; } system.out.println（ "user3の名前：" + map.get（new user（3）））; }} output：user3 name：null上記のように、カスタムユーザークラスインスタンスをハッシュマップオブジェクトとして使用する場合、ユーザークラスがベースクラスオブジェクトを自動的に継承するため、ユーザー3の名前は印刷時に見つかりません。したがって、オブジェクトのハッシュコードメソッドを自動的に使用してハッシュ値を生成し、デフォルトでハッシュ値を計算するためにオブジェクトのアドレスを使用します。したがって、新しいユーザー（3）によって生成された最初のインスタンスのハッシュ値は、生成された2番目のインスタンスのハッシュ値とは異なります。ただし、ハッシュコードメソッドを単純にオーバーライドするだけが必要な場合は、等しいメソッドを同時にオーバーライドしない限り、適切に機能しません。オブジェクトの一部でもあります。 HashMapはEquals（）を使用して、現在のキーがテーブルに存在するキーと同じかどうかを判断します。上記のGETまたはPut Methodを参照できます。
正しいEquals（）メソッドは次の5つの条件を満たす必要があります。
繰り返しますが、デフォルトのobject.equals（）は比較オブジェクトのアドレスにすぎないため、1人の新しいユーザー（3）は別の新しいユーザー（3）に等しくありません。したがって、独自のクラスをHashMapのキーとして使用する場合は、HashCode（）とEquals（）の両方を過負荷する必要があります。
次のコードは正常に機能します：
クラスユーザー{// id番号保護されたint idnumber; public user（int id）{idnumber = id; } @override public int hashcode（）{return idnumber; } @Override public boolean equals（object obj）{return obj instance of user &&（idnumber ==（（user）obj）.idnumber）; }} public class testuser {public static void main（string [] args）{map <user、string> map = new hashmap <user、string>（）; for（int i = 0; i <5; i ++）{map.put（new user（i）、 "name："+i）; } system.out.println（ "user3の名前：" + map.get（new user（3）））; }} output：user3の名前：名前：3上記は、単にハッシュコードの唯一の差別としてidnumberを返すだけであり、ユーザーは自分のビジネスに従って独自の方法を実装することもできます。 Equalsメソッドでは、InstanceOFはオブジェクトがnullであるかどうかを静かに確認します。 InstanceOFの左側のパラメーターがnullの場合、falseが返されます。 equals（）のパラメーターがnullでなく、タイプが正しい場合、比較は各オブジェクトの実際のidnumberに基づいています。出力からわかるように、現在の方法は正しいです。
参照：
「Javaプログラミングの考え」
JDK 1.6中国のヘルプマニュアル
上記はこの記事のすべての内容です。この記事の内容が、すべての人の勉強や仕事に役立つことを願っています。また、wulin.comをもっとサポートしたいと思っています！