hashMapソースの分析と原理

前言
hashMapは普段の仕事や面接でよく使われていますが、いくつかの面から記録します.

ハッシュテーブル

とは

HashMap実現原理

なぜHashMapの配列長は2の次べき乗に違いないのか.

1.ハッシュ表とは
ハッシュ・テーブルについて議論する前に、他のデータ構造が追加、検索などの基礎操作でパフォーマンスを実行していることを概説します.
配列:連続したストレージユニットを使用してデータを格納します.指定されたインデックスの検索では、時間複雑度はO(1)である.与えられた値で検索するには、配列を巡回する必要があり、与えられたキーワードと配列要素を逐一比較する必要があり、時間の複雑度はO(n)である.もちろん、秩序配列については、二分検索、補間検索、フィボナッチ検索などの方法を採用することができ、検索の複雑さをO(logn)に向上させることができる.一般的な挿入削除操作では,配列要素の移動に関し,その平均複雑度もO(n)である.
リニアチェーンテーブル:チェーンテーブルの新規作成、削除などの操作(指定された操作位置が見つかった後)については、ノード間の参照を処理するだけでよいが、時間的複雑度はO(1)であり、検索操作はチェーンテーブルを巡回して逐一比較する必要があり、複雑度はO(n)である
二叉木:相対的にバランスのとれた秩序ある二叉木に対して、挿入、検索、削除などの操作を行い、平均複雑度はO(logn)である.
ハッシュテーブル:上記のいくつかのデータ構造に比べて、ハッシュテーブルに追加、削除、検索などの操作を行い、性能が非常に高く、ハッシュ競合を考慮せずに、1回の位置決めで完了し、時間の複雑さはO(1)であり、次にハッシュテーブルがどのように驚くべき定数次O(1)を実現しているかを見てみましょう.
データの格納構造は2つの方法しかないことを知っています.順序格納構造とチェーン格納構造(スタック、キュー、ツリー、図などは論理構造から抽象化され、メモリにマッピングされ、この2つの物理組織形式)です.ハッシュテーブルはこの特性を利用しており,ハッシュテーブルの主幹は配列である.
たとえば、エレメントを追加または検索するには、現在のエレメントのキーワードを関数によって配列の位置にマッピングし、配列の下に一度位置決めすることで操作を完了します.
格納場所=f(キーワード)
ここで,この関数fは一般にハッシュ関数と呼ばれ,この関数の設計の良し悪しはハッシュテーブルの優劣に直接影響する.たとえば、ハッシュ・テーブルで挿入操作を実行します.
検索操作は同じで、ハッシュ関数で実際の記憶アドレスを計算し、配列から対応するアドレスを取り出すとよい.
ハッシュ競合
しかし、万事完璧ではありません.もし2つの異なる要素があれば、ハッシュ関数によって得られた実際の記憶アドレスが同じであればどうしますか.すなわち,ある要素をハッシュ演算して記憶アドレスを取得し,挿入しようとすると,他の要素に占有されていることが分かったが,これはいわゆるハッシュ衝突,すなわちハッシュ衝突である.前述したように、ハッシュ関数の設計は極めて重要であり、良いハッシュ関数は計算が簡単でハッシュアドレスの分布が均一であることをできるだけ保証するが、配列は連続的な固定長のメモリ空間であり、どんなに良いハッシュ関数でも得られるストレージアドレスが絶対に衝突しないことを保証することはできないことを明らかにする必要がある.では、ハッシュ衝突はどのように解決されますか?ハッシュ競合の解決策は、オープン・アドレス法(競合が発生した場合、次の未占有のストレージ・アドレスを探し続ける)、再ハッシュ関数法、チェーン・アドレス法、HashMapはチェーン・アドレス法、すなわち配列+チェーン・テーブルを採用する方法である.
HashMap実現原理
HashMapのメインクラスはEnty配列(jdk 1.7)であり、各Entyにはキー値ペア(key-value)が含まれています.ソースコードを見てみましょう.

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

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

したがって、HashMapの全体的な構造は以下の通りである.
簡単に言えば、HashMapは配列+チェーンテーブルからなり、配列はHashMapの本体であり、チェーンテーブルは主にハッシュ競合を解決するために存在し、位置決めされた配列位置にチェーンテーブル(現在のentryのnextがnullを指す)が含まれていない場合、検索、追加などの操作は速く、1回のアドレスだけでよい.位置決めされた配列にチェーンテーブルが含まれている場合、追加操作の場合、その時間複雑度はO(n)であり、まずチェーンテーブルを遍歴し、存在するか上書きするか、そうでないかが新規である.検索操作では、チェーンテーブルを巡回し、keyオブジェクトのequalsメソッドで1対ずつ検索する必要があります.したがって,性能を考慮すると,HashMapのチェーンテーブルが少ないほど性能がよくなる.その他の重要なフィールド

//     key-value      
transient int size;
//  ， table == {} ，       （       16）； table    ，    table       ，threshold    capacity*loadFactory。HashMap          threshold，       
int threshold;
//    ，   table       ，   0.75
final float loadFactor;
//      ，  HashMap     ，  HashMap     ，             HashMap        （  put，remove   ），      ConcurrentModificationException
transient int modCount;

HashMapには4つのコンストラクタがあり、他のコンストラクタではinitialCapacityとloadFactorの2つのパラメータがユーザーに入力されていない場合はデフォルト値が使用されます.
initialCapacityのデフォルトは16、loadFactoryのデフォルトは0.75です.
そのうちの1つを見てみましょう

public HashMap(int initialCapacity, float loadFactor) {
　　　　　//              ，      MAXIMUM_CAPACITY = 1<<30(230)
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
　　　　　
    init();//init   HashMap       ，        linkedHashMap        
}

上記のコードから、通常のコンストラクタでは、配列tableにメモリ領域を割り当てるのではなく(Mapを指定するコンストラクタの例外として参照される)、put操作を実行するときにtable配列が本当に構築されることがわかります.
OK、次にput操作の実現を見てみましょう

public V put(K key, V value) {
    //  table      {}，      （ table        ），   threshold，  threshold initialCapacity    1<<4(24=16)
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
   //  key null，     table[0] table[0]     
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);// key hashcode     ，      
    int i = indexFor(hash, table.length);//   table      
    for (Entry e = table[i]; e != null; e = e.next) {
    //          ，      。  value   value，    value
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;//       ， HashMap        ，      
    addEntry(hash, key, value, i);//    entry
    return null;
}

まずinflateTableという方法を見てみましょう

 
 private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);//capacity   2   
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//   threshold  ， capacity*loadFactor MAXIMUM_CAPACITY+1    ，capaticy      MAXIMUM_CAPACITY，  loadFactor  1
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

inflateTableこの方法は、ホスト配列tableのメモリに記憶領域を割り当てるために使用され、roundUpToPowerOf 2(toSize)によって、capacityがtoSizeより大きいか、またはtoSizeに最も近い2次べき乗、例えばtoSize=13である場合、capacity=16であることを保証することができる.to_size=16,capacity=16;to_size=17,capacity=32.

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

roundUpToPowerOf 2でのこの処理により、配列長が2の二次べき乗となるようにする、Integer.highestOneBitは、一番左のbit(他のbitビットは0)を取得するための数値である.
hash関数

    //         ，       ，     ， key hashcode                                   
final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    
    

以上hash関数で算出した値をindexForでさらに処理して実際の記憶位置を取得する
/**

 *       
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

h&(length-1)は、取得したindexが配列範囲内にあることを保証し、例えば、デフォルト容量16、length-1=15、h=18をバイナリ計算に変換する

 1  0  0  1  0
&   0  1  1  1  1
__________________
    0  0  0  1  0    = 2

最終的に算出されたindex=2.一部のバージョンでは、ここでの計算には型取り演算が使用され、indexが配列範囲内にあることも保証されていますが、ビット演算はコンピュータにとってより性能が高い(HashMapにはビット演算が大量にある)
したがって、最終的な格納場所の決定プロセスは、次のようになります.
addEntryの実装を見てみましょう.
void addEntry(int hash, K key, V value, int bucketIndex) {

    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// size      threshold，               
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

以上のコードから分かるように,ハッシュ競合が発生しsizeが閾値より大きい場合には配列拡張が必要であり,拡張が必要な場合には,前の配列の2倍の長さの新しい配列を新規作成し,現在のEntry配列の要素をすべて転送し,拡張後の新しい配列の長さは前の2倍であるため,拡張は相対的にリソース消費の操作である.
なぜHashMapの配列長は2の次べき乗に違いないのか.
上記のresizeメソッドを引き続き見てみましょう

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

配列が拡張され、配列長が変化し、格納位置index=h&(length-1)ではindexが変化する可能性があります.indexを再計算する必要があります.まずtransferという方法を見てみましょう.

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
　　　　　//for      ，      ，        ，              （         ，           ）
        for (Entry e : table) {
            while(null != e) {
                Entry next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
　　　　　　　　　 //   entry next         ,newTable[i]     ，      entry ，   entry ，         。
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

この方法は古い配列のデータをチェーンテーブルごとに遍歴し,新しい拡張後の配列に投げ込み,我々の配列インデックス位置の計算はkey値のhashcodeに対してhashスクランブル演算を行った後,length−1とビット演算を行うことによって最終配列インデックス位置を得る.
hashMapの配列長は必ず2の次べき乗を保持し、例えば16のバイナリは10000を表し、length-1は15であり、バイナリは01111であり、同理拡張後の配列長は32であり、バイナリは100000を表し、length-1は31であり、バイナリは011111を表す.下図からも低位がすべて1であることが保証され、拡張後には1桁の差しかないことがわかる.最も左のビットが多くなった1であり、h&(length-1)を通過する際に、hに対応する最も左の差分が0であれば、得られる新しい配列インデックスと古い配列インデックスが一致することが保証される(これまでハッシュされていた古い配列のデータビットを大幅に減少させて再変換する)
また、配列長は2の次べき乗を維持し、length-1の下位はすべて1であり、得られる配列インデックスindexはより均一になります.例えば、次のようにします.
上の&演算では,高位は結果に影響を及ぼさないことが分かった(hash関数が種々のビット演算を用いるのも,低位をよりハッシュさせるためである可能性がある),下位ビットbitのみに注目し,下位ビットがすべて1であれば,h下位部分ではいずれのビットの変化も結果に影響を及ぼす,すなわちindex=21という記憶位置を得るにはhの下位ビットはこの組合せしかない.これも配列長が2の次べき乗に設計されなければならない理由である.
2の次べき乗でなければ,すなわち低位がすべて1ではない場合,index=21,hの低位部分が一意性を持たなくなるようにハッシュ衝突の確率が大きくなるとともに,indexに対応するこのbitビットがどうしても1に等しくならず,対応する配列位置も無駄になる.
getメソッド

  public V get(Object key) {
    　　　　 //  key null,    table[0]      。
            if (key == null)
                return getForNullKey();
            Entry entry = getEntry(key);
            return null == entry ? null : entry.getValue();
     }
     
     

getメソッドはkey値で対応するvalueを返し、keyがnullの場合はtable[0]で直接検索します.getEntryというメソッドをもう一度見てみましょう
etメソッドはkey値で対応するvalueを返し、keyがnullの場合はtable[0]で直接検索します.getEntryというメソッドをもう一度見てみましょう
getメソッドの実装は比較的簡単であり、key(hashcode)-->hash-->indexFor-->最終インデックス位置、対応する位置table[i]を見つけるあ、チェーンテーブルがあるかどうかを確認し、チェーンテーブルを巡回し、keyのequalsメソッドで対応するレコードを検索します.配列位置に位置してからチェーンテーブルを巡回していると思う人がいるので注意しましょう.e.hash==hashという判断は必要なく、equalsのみで判断すればいいのです.そうではありません.受信したkeyオブジェクトがequalsメソッドを書き換えた場合、equalsメソッドは書き換えられませんhashCodeの書き換えがあり、このオブジェクトがこの配列位置に位置している場合、equalsのみで判断すると等しいかもしれないが、hashCodeと現在のオブジェクトが一致しない場合、ObjectのhashCodeの約束に従って現在のオブジェクトを返すことができずnullを返すべきであり、後の例ではさらに説明する.
ここでは、以下を参照してください.https://www.cnblogs.com/cheng...