HashMap実現原理復習

1.HashMapの内部実現メカニズム
HashMapはデータ構造におけるハッシュテーブル(Hash Table)の実装であり、Hashテーブルはハッシュリストとも呼ばれる.Hashテーブルは、キーキーキーキーキーに基づいて対応する値Valueにアクセスするデータ構造であり、1つのマッピング関数によってキーをテーブルの1つの位置にマッピングしてその位置の値にアクセスし、検索の速度を速める.このマッピング関数をHash関数と呼び,記録を格納する配列をHashテーブルと呼ぶ.
Javaでは、HashMapの内部実装はチェーンテーブルと配列の利点を組み合わせており、リンクノードのデータ構造はEntryであり、各Entryオブジェクトの内部には次のEntryタイプのオブジェクトへの参照が含まれています.以下のコードに示します.

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

HashMapのコンストラクション関数では、次のコードに示すように、Entryテーブルが配列として明示されていることがわかります.

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

上記のコンストラクション関数では、デフォルトのDEFAULT_INITIAL_CAPACITY値16,DEFAULT_LOAD_FACTORの値は0.75です.putの1つの要素がHashMapに除去されると、その内部は以下のように実現される.

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

put関数でハッシュ値を1つのhash関数で得ることが分かるが,HashTableは実装時にhashCodeをハッシュ値として直接用いるため,HashTableの代わりにHashMapを用いることに一定の最適化があることを指摘する必要がある.
put関数で使用される2つの関数hashとindexForの実装は、それぞれ次のとおりです.

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);  
    }  

hash関数がなぜこのように設計されるのかについては,特定のハッシュ関数の設計問題に関し,ハッシュアルゴリズムの時間的複雑さを考慮するとともに,配列上の各位置にできるだけ値を持たせ,時間と空間の最適化を求める必要がある.
indexFor関数は、index値をlength-1に制限する巧みな演算を使用します.
もちろん,hash関数が競合する場合,同じkeyに対応するhash値が同じである可能性があり,hash値が同じ要素がリンクで格納され,HashMapのgetメソッドはvalueを取得する際にチェーンテーブルを遍歴し,key値が一致するvalueを取り出す.
2.Hashの実現
主にハッシュアルゴリズムと衝突の解決である.
3.いつReHash
HashMapの内部実装メカニズムを紹介する際に2つのパラメータについて言及した,DEFAULT＿INITIAL_CAPACITYとDEFAULT_LOAD_FACTOR,DEFAULT_INITIAL_CAPACITYはtable配列の容量、DEFAULT_LOAD_FACTORは、ハッシュ競合を最大限に回避し、HashMap効率を向上させるために設定された影響因子であり、DEFAULT_を乗算するINITIAL_CAPACITYでは閾値thresholdが得られ,HashMapの容量がthresholdに達すると拡張が必要となり,このときReHash操作が行われ,次のaddEntry関数の実装が見られ,sizeがthresholdに達するとresize関数を呼び出して拡張が行われる.

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

拡張の過程でReHash操作を行う必要があるが,これは非常に時間がかかり,実際にはできるだけ避けるべきである.