Hashmapは、私たちがたくさん使用するコレクションでもあります。これは、ハッシュテーブルに基づいたマップインターフェイスの実装であり、キー価値の形で存在します。ハッシュマップでは、キー値は常に全体として処理されます。システムは、ハッシュアルゴリズムに基づいてキー価値のストレージ位置を計算します。キーを介して値を迅速に保存および取得することができます。ハッシュマップへのアクセスを分析しましょう。
1。定義
HashMapはマップインターフェイスを実装し、AbstractMapを継承します。マップインターフェイスは、キーマッピングの値へのルールを定義し、AbstractMapクラスは、このインターフェイスを実装するために必要な作業を最小限に抑えるために、MAPインターフェイスのバックボーン実装を提供します。実際、AbstractMapクラスはMAPを実装しています。ここでMap LZをマークすることはより明確でなければならないと思います！
パブリッククラスのhashmap <k、v>は、abstractmap <k、v>を拡張します<k、v>、クローン可能、シリアル化可能
2。コンストラクター関数
HashMapは3つのコンストラクターに提供されます。
Hashmap（）：デフォルトの初期容量（16）とデフォルトの負荷係数（0.75）を使用して空のハッシュマップを構築します。
HashMap（int initialCapacity）：指定された初期容量とデフォルトの負荷係数（0.75）を備えた空のハッシュマップを構築します。
Hashmap（int initialcapacity、float loadfactor）：指定された初期容量と負荷係数を備えた空のハッシュマップを構築します。
ここでは、2つのパラメーターが記載されています。初期容量、読み込み係数です。これらの2つのパラメーターは、ハッシュマップのパフォーマンスに影響を与える重要なパラメーターです。容量は、ハッシュテーブルのバケット数を表します。初期容量は、ハッシュテーブルを作成する際の容量です。負荷係数は、容量が自動的に増加する前にハッシュテーブルが到達できるスケールです。ハッシュテーブルスペースの使用度を測定します。負荷係数が大きいほど、ハッシュテーブルの負荷の程度が高く、その逆も同様です。リンクリストメソッドを使用してハッシュテーブルの場合、要素を見つける平均時間はO（1+A）です。したがって、負荷係数が大きい場合、スペースはより完全に利用されますが、結果は検索効率の低下です。負荷係数が小さすぎると、ハッシュテーブルのデータがまばらすぎて、空間に深刻な廃棄物を引き起こします。システムのデフォルトの負荷係数は0.75であり、通常、変更する必要はありません。
HashMapは、高速アクセスをサポートするデータ構造です。そのパフォーマンスを理解するには、データ構造を理解する必要があります。
iii。データ構造
Javaで最も一般的に使用される2つの構造は、配列とシミュレートされたポインター（参照）であることがわかっています。ほとんどすべてのデータ構造は、これら2つと組み合わせて実装でき、同じことがハッシュマップにも当てはまります。実際、HashMapは、次のように、次のように「リンクリストハッシュ」です。
上記の図から、HashMapの基礎となる実装が配列かどうかを確認できますが、配列内のすべてのアイテムはチェーンです。パラメーター初期性は、配列の長さを表します。以下は、ハッシュマップコンストラクターのソースコードです。
public hashmap（int initialcapacity、float loadfactor）{//初期容量は<0になりません（initialcapacity <0）新しいIllegalargumentexception（ "違法初期容量：" + initialcapacity）; //初期容量は>最大容量の値を>最大容量値、ハッシュマップの最大容量は2^30 if（initialcapacity> maximion_capacity）initialcapacity = maximix_capacity; //負荷係数は<0になりません（loadFactor <= 0 || float.isnan（loadfactor））新しいIllegalargumentException（ "違法負荷係数：" + loadFactor）; //初期容量よりも大きい最小2のNパワー値を計算します。 int容量= 1; while（容量<initialcapacity）容量<< = 1; this.loadfactor = loadfactor; //ハッシュマップの容量制限を設定します。ハッシュマップの容量がこの制限に達すると、容量拡張操作が実行されます=（int）（容量 * loadfactor）; //テーブルアレイテーブルの初期化= new entry [capurity]; init（）; }ソースコードからわかるように、新しいハッシュマップが作成されるたびにテーブル配列が初期化されます。テーブル配列の要素は、エントリノードです。
静的クラスエントリ<k、v>はmap.entry <k、v> {final k key; v値;エントリ<k、v> next;最終的なintハッシュ; /***新しいエントリを作成します。 */ entry（int h、k k、v v、entry <k、v> n）{value = v; next = n; key = k;ハッシュ= h; } .....}その中でも、エントリはハッシュマップの内部クラスで、キーキー、値値、次のノード、およびハッシュ値が含まれています。これは非常に重要です。これはまさに、エントリがリンクリストとしてテーブル配列のアイテムを形成するためです。
上記では、ハッシュマップのデータ構造を簡単に分析し、以下ではハッシュマップが高速アクセスをどのように実装するかを検討します。
4。ストレージ実装：Put（key、vlaue）
まず、ソースコードを見てみましょう
public v put（k key、v value）{//キーがnullの場合、putfornullkeyメソッドを呼び出して、nullとテーブルの最初の位置を保存します。これが、hashmapがnullを許可する理由です（key == null）putfornullkey（value）; // key int hash = hash（key.hashcode（））のハッシュ値を計算します。 -----（1）//テーブル配列のキーハッシュ値の位置を計算しますint i = indexfor（hash、table.length）; -----（2）// iから反復し、キーが保存されている場所を見つけます（エントリ<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を返します。 //古い値を返します}} //変更の数を1 modcount ++で増やします。 // i position addentry（hash、key、value、i）にキーと値を追加します。 nullを返します。 }ソースコードを使用して、HashMapの保存データのプロセスが次のことを明確に確認できます。まず、キーがnullかどうかを判断します。 nullの場合は、putfornullkeyメソッドを直接呼び出します。空でない場合は、最初にキーのハッシュ値を計算し、ハッシュ値に従ってテーブル配列のインデックス位置を検索します。この位置に要素がある場合は、同じキーが存在するかどうかを比較してください。存在する場合は、元のキーの値を上書きし、それ以外の場合はチェーンのヘッドに要素を保存します（保存された最初の要素はチェーンの端に配置されます）。テーブルに要素がない場合、直接保存されます。このプロセスは簡単に思えますが、実際には内部情報があります。次のようにいくつかのポイントがあります：
1。最初に反復を見てみましょう。ここでの反復の理由は、同じキー値の存在を防ぐためです。 2つのハッシュ値（キー）が同じであることがわかった場合、ハッシュマップの処理方法は、古い値を新しい値に置き換えることです。キーはここでは処理されていません。これは、ハッシュマップに2つの同一のキーがないことを説明しています。
2。ビュー（1）および（2）。これがハッシュマップの本質です。まず、ハッシュメソッドがあります。これは純粋な数学的計算であり、hのハッシュ値を計算することです。
static int hash（int h）{h ^ =（h >>> 20） ^（h >>> 12）; return h ^（h >>> 7） ^（h >>> 4）; }HashMapテーブルの場合、データ分布は均等にする必要があることを知っています（各アイテムに1つの要素しか持たないようにすることが最善であるため、直接見つけることができます）。きつすぎたり、緩すぎたりすることはできません。きつすぎるとクエリの速度が遅くなり、ゆるいほどスペースが無駄になります。ハッシュ値を計算した後、テーブル要素が均等に分散されるようにするにはどうすればよいですか？金型の獲得については考えますが、金型の獲得が大いに消費されるため、HashMapは次のように処理します。Indexforメソッドを呼び出します。
static int indexfor（int h、int length）{return h＆（length-1）; }Hashmapの基礎となる配列の長さは常に2のN-Powerにあり、コンストラクターに存在します：容量<< = 1;そうすることで、根底にあるハッシュマップの長さが2のn電力であることを常に保証できます。長さが2のn電力である場合、h＆（長さ-1）は長さの弾性率を取るのと同等であり、速度はモジュラスを直接摂取するよりもはるかに高速です。これは、速度の観点からハッシュマップの最適化です。なぜそれがnの電力に2であるかについては、次の説明があります。
indexforメソッドに戻りましょう。これには、h＆（length -1）の1つのステートメントのみがあります。上記のモジュラス操作に加えて、この文には非常に重要な責任があります。テーブルデータを均等に配布し、スペースを最大限に活用することです。
ここでは、長さは16（2^n）および15であり、Hは5、6、および7であると仮定します。
n = 15の場合、6と7の結果は同じです。つまり、テーブルに保存されている場所は同じです。つまり、衝突が発生し、6と7は1つの場所でリンクリストを形成し、クエリ速度の低下につながります。ここでは3つの数字のみが分析されているが、多くはないので、0-15を見てみましょう。
上記のチャートから、合計8つの衝突が見られます。同時に、無駄なスペースが非常に大きく、1、3、5、7、9、11、13、13、13、および15の場所に記録がないことがわかります。つまり、データは保存されません。これは、彼らが14で実行され、操作すると、得られる結果の最後のビットは常に0になります。つまり、0001、0011、0101、0111、1001、1011、1101、1111、および1111の場所にデータを保存することは不可能です。長さ= 16の場合、長さ1 = 15は1111です。その後、低ビットと動作を実行する場合、値は常に元のハッシュ値と同じであり、高ビット操作を実行すると、その値は低ビット値に等しくなります。したがって、長さ= 2^nの場合、異なるハッシュ値間の衝突の確率は比較的小さく、テーブル配列でデータが均等に分布し、クエリ速度が高速になります。
ここでは、PUTプロセスを確認します。キー価値のペアをハッシュマップに追加する場合、システムは最初にキーのハッシュ値を計算し、次にハッシュ値に基づいてテーブルに保存されている場所を確認します。この位置に要素がない場合は、直接挿入します。それ以外の場合は、そのポイントの要素のリストを反復し、それに応じてキーのハッシュ値を比較します。 2つのハッシュ値が等しく、キー値が等しい場合（e.hash == hash &&（（k = e.key）== key || key.equals（k）））、元のノードの値は新しいエントリの値で上書きされます。 2つのハッシュ値が等しいがキー値が等しくない場合は、リンクリストのヘッダーにノードを挿入します。特定の実装プロセスについては、次のように、Addentryメソッドを参照してください。
void addentry（int hash、k key、v value、int bucketindex）{//エントリエントリを取得<k、v> e = table [bucketindex]; //新しく作成されたエントリをBucketIndexインデックスに入れ、新しいエントリポイントを元のエントリテーブル[BucketIndex] = new entry <K、v>（hash、key、value、e）にします。 //ハッシュマップ内の要素の数が制限を超える場合、容量は（size ++> =しきい値）resize（2 * table.length）の場合、2倍大きくなります。 }この方法には注意すべき2つのポイントがあります。
1つはチェーンの生成です。これは非常にエレガントなデザインです。システムは常に新しいエントリオブジェクトをBucketIndexに追加します。 BucketIndexにオブジェクトがある場合、新しく追加されたエントリオブジェクトは元のエントリオブジェクトを指し、エントリチェーンを形成します。ただし、BucketIndexにエントリオブジェクトがない場合、つまりe == null、新しく追加されたエントリオブジェクトがNULLをポイントし、エントリチェーンが生成されない場合があります。
2。容量の拡大。
ハッシュマップの要素の数が増加すると、衝突の確率が大きくなり、生成されたリンクリストの長さがより長くなります。これは必然的にハッシュマップの速度に影響します。ハッシュマップの効率を確保するために、システムは特定の重要なポイントで容量を拡大する必要があります。この重要なポイントは、ハッシュマップの要素の数がテーブル配列長*荷重係数に等しい場合です。しかし、スケーリングは非常に時間のかかるプロセスです。これは、新しいテーブルアレイのこのデータの位置を再計算してコピーする必要があるためです。したがって、ハッシュマップの要素の数を予測した場合、プリセット要素の数はハッシュマップのパフォーマンスを効果的に改善できます。
5。実装を読む：get（key）
ハッシュマップの保管と比較して、撤回は比較的簡単です。キーのハッシュ値を介してテーブル配列のインデックスのエントリを見つけてから、キーに対応する値を返します。
public v get（object key）{// nullの場合、getFornullKeyメソッドを呼び出して対応する値を返します（key == null）return getFornullKey（）; // key int hash = hash（key.hashcode（））のハッシュコード値に基づいてハッシュコードを計算します。 //（エントリ<k、v> e = table [indexfor（hash、table.length）]; e！= null; e = e = e = edext）{object k; //検索されたキーが検索されたキーと同じ場合、（e.hash == hash &&（（k = e.key）== key || key.equals（k））return e.value; } nullを返します。 }ここでは、キーに基づいて迅速に取得できる値は、ハッシュマップのデータ構造と分離できないだけでなく、エントリと関係があります。前述のように、HashMapは鍵と値をストアドプロシージャに個別に保存するのではなく、エントリオブジェクトであるキー価値全体として処理されます。同時に、値はキーの添付ファイルにのみ相当します。ストレージプロセス中に、システムはキーのハッシュコードに基づいてテーブル配列のエントリのストレージ位置を決定し、フェッチングのプロセスでは、キーのハッシュコードに従って対応するエントリオブジェクトも削除されます。
元のリンク：http：//www.cnblogs.com/chenssy/p/3521565.html
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。