HashMapの内部実現メカニズムの編

4204 ワード

hashMap

HashMapの内部実装は、hashテーブルというデータ構造を採用しています.

   何がsh時計ですか
   hash表はまた散リストと言います.hashテーブルは、キーコード値に基づいて直接アクセスするデータ構造である.つまり、キーコード値を表の位置にマッピングすることによって記録にアクセスし、検索の速度を速める.このマッピング関数はhash関数といい、記録を保存する配列はhashテーブルといいます.
    簡単に言いますと、hash表は行列とチェーンの集合です.配列が速くて、チェーンが簡単に挿入して削除できるという利点が集積されています.

     HashMapはどのように内部で実現されますか?
     大体以下の点があります.
1下層は一つのEntry＜k,v＞配列で実装され、各Entryオブジェクトの内部には次のEntryタイプオブジェクトを指す参照が含まれている.

Entryタイプを見ると、内部にMapのK、V、hashの値と自身の引用があります.

  static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next; ///Entry              ，     Entry
        
        final int hash; 
     ………………………………………………………………}

配列を実例化した後(標準サイズは16)、hash()関数により配列内の格納位置indexを得て、筆者はこのステップをハッシュとして理解した.
ソースコードを確認してください

//              ，new   Entry  
  public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

注:デフォルトのdefault_init_capicityは16です

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        ...........
}

ここでhashTableと対比して、hashTableは直接key.hashCoe()を使ってhash値とするので、hash関数が少なくなりました.ハッシュ分布がそんなに均一ではなく、hashMapがhashTableに取って代わる最適化になります.

  static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

  とりあえずkey値が空の場合は見ません.これが空でない場合、一つのhash関数を通じてhash値を得ます.関数パラメータはkey.hashCodeです.(hashCodeはハッシュコードであることを知っています.ここではまず対象のメモリアドレスとして理解できます.詳しくは次のページをご覧ください.)そしてもう一つのindexFor()函数を呼び出して、配列中の記憶場所を得ます.
   内部の実現は結局はより一層改善されなければならない.なぜここで二つの関数を回るべきですか?hash()関数とindexFor()関数は本当に必要なindexを得ることができますか?
実はこのようにするのはハッシュをより均一にし、衝突の確率を減らすためです.各配列に値があると、チェーンテーブルに保存したい要素が少なくなりますので、できるだけ時間と空間のバランスを求めます.しかし、この二つの関数はなぜこのようになったのか、私は本当に分かりません.また、ご指導をお願いいたします!!!


    付録:ここではkeyが空の場合もあります.key値が重複している場合もあります.key値が重複している場合、私達は新しいvalue値で古いvalue値に取って代わられたと発見しやすいです.これに対して興味のある見方は深く追究してもいいです.

2解決衝突:キーキーキーが違っても、hash関数によって得られたindex値は同じかもしれないからです.このとき、同じindex値を得た要素を配列中の対応するindex値の位置の後ろに接続してもいいです.つまり、その位置をチェーンの頭の結点として、後にノードを追加します.

3配列拡張.apiによって、hashMapの構造方法は、初期容量initCapicityと、もう一つは積載因子loadFactorという2つのパラメータを持つことができ、初期容量は配列の初期サイズであることが分かります.それは積載因子というものです.apiの注釈によると.ロードファクタは、ハッシュ・テーブルが、容量が自動的に増加する前に、マルチプルなスケールに達することができる.ハッシュ・テーブルのエントリ数が、現在の容量との積を超えている場合、ハッシュ・テーブルは、内部データ構造を再構築するために、約2倍のバケット数を有することになる.筆者の理解によると、何の負荷因子などの書面名詞であっても、hash表に入れることができる数に対する制限にすぎず、この制限を超えると、配列容量を拡大し、すべての要素を並べ直す必要があるということです.この負荷係数の代わりに、例えば配列中の要素が少なすぎて、後のチェーンが長すぎると、全体がチェーンストアに偏って配列記憶の利点がなくなってしまうので、あるチェーン長が500を超えると、配列容量を拡大して、rehash操作を行う必要があります.

  void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

注:ここでthress holdはしきい値としても理解できます.ここのresizeの拡大方法と後のrehashのソースはtransferの方法です.筆者はちょっと力不足ですね.

4 rehash():配列拡張後にこの動作を実行します.元のハッシュ要素を取り出してもう一度ハッシュします.配列長が拡大したため、この結果得られたハッシュ位置は元とは違っているかもしれません.元のハッシュの要素を全部取り出すためには、このステップの操作は非常に時間がかかります.したがって、配列の初期長さを予め定めたときには、rehash()の出現を避けるために、適切な長さとローディング係数を選択したほうがいいです.

これでhashMapの内部実現メカニズムの大まかな枠組みはこうなった.

セットとMapデータ構造