HashMapの原理分析

前言
HashMapは開発でよく用いられるキー値対集合クラスであり,使用中はput,getのみであることが多いが,本稿ではソースコードを検討した後のHashMapの原理解析は本人の個人的な理解であり,参考に供する(本原理はjdk 8バージョンのHashMap)
一、HashMapの概要
ハッシュ表に基づくMapインタフェースの実装.このインプリメンテーションでは、オプションのマッピング操作がすべて提供され、null値とnullキーを使用できます.HashMapは実際には配列+チェーンテーブル(1.8赤と黒の木を加えて検索性能を向上させる)で構成されており、デフォルトの長さ16の配列を初期化し、ルールに基づいてどの位置に配置するかを計算します.
二、Hash原理の簡単な説明
put操作
キー値がキー値に対してHashMapに挿入される場合は、次の操作を行います.

keyのhash値を計算し、hash値の高い16ビットを一定に保ち、低い16ビットを高い16と異ならせ、新しいhash数を得る(この操作はhash衝突を減らすためである).

hash値と現在のHashMap長さ-1(ビット数が0から始まるので-1)をビットと操作し、格納されたindexを得る.

は、その位置に既にノード(すなわちhash値が衝突しているかどうか)があるかどうかを判断し、なしで、Nodeノードオブジェクトを作成してキー値対key-valueを入れる.はい、hash値が同じかどうかを判断します.同じです.新しいノードは古いノードをカバーしています.違います.新しいノードは元のノードオブジェクトの後ろにリンクされています.チェーンテーブルオブジェクトを構成してその位置に入れます(赤黒ツリーオブジェクトでもあります).これは簡単に言えば、この位置がなければNodeノードを入れ、あり、keyが同じで上書きし、あるがkeyが異なるので、今回入れたNodeと元のチェーンテーブルを結合して変更位置に

を置く.

投入終了後、現在のHashMapの容量が臨界値(現在長x 0.75)より大きく、大きくないか、終了かを判断する.より大きい、拡張(現在の長さx 2)し、各ノード位置

をさらに再計算する.
getアクション
HashMapのvalueをキーキーで取得すると、次のようになります.

の前の2ステップはputの1と2と同じで、keyに基づいてhashと位置を計算します.

は、その位置のオブジェクトをnullとして取得し、nullを返す.nullではなく、そのオブジェクトのhashがkeyのhashと同じかどうかを判断し、同じノードのvalueを返し、異なるオブジェクトがチェーンテーブルまたは赤黒ツリーNodeであるかどうかを判断する.
remove操作
removeには複数のリロード方法がありますが、最後の処理はkeyで操作されます.

の前の2ステップはputの1と2と同じで、keyに基づいてhashと位置を計算します.

はgetと動作し、nodeが見つかった位置を空にするか、チェーンテーブル上で削除するか、ツリー上で削除するかにすぎない.

三、Hashソースの詳細
put操作
put方式の実際の内部呼び出しはputVal()メソッドで実現されるので、putVal()のソースコードを直接貼り付けます.

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

論理の詳細:

は、hashmapにおける配列オブジェクトが空であるかどうか、空であるかどうかを判断し、初期化は長さ16の配列を作成する.

p=tab[i=(n-1)&hash])==nullは対応する配列位置を得て、その位置が空であるかどうかを判断し、空のためにkey-valueおよびhash値を直接作成してオブジェクトを入れる(すなわちnewNode(hash,key,value,null))位置を作成する.説明:作成されたノードオブジェクトには、リンクの別のノード

を指すnext属性を持つチェーンテーブル機能があります.

この位置は空ではなく、対象のhash値、keyが新しく入力されたものと同じかどうかを判断し、同じ説明が同じkeyである場合、古いvalueを上書きする.

この位置は空ではなく、オブジェクトのhash値、keyは新しく入力されたものとは異なり、その位置のオブジェクトタイプがtreeNodeであるか否かを判断し、hash、key、valueをtreeNodeに追加する.

この位置は空ではなく、オブジェクトのhash値、keyは新しく入力されたものとは異なり、この位置におけるオブジェクトタイプもtreeNodeではないと判断すると、チェーンテーブルオブジェクトとなり、新しく入力されたkey-valueおよびhash値をnewNode(hash,key,value,null)としてチェーンテーブルオブジェクトの末端に置き、チェーンテーブル長さが7を超えるか否かを判断し、7を超えるとチェーンテーブルを赤黒ツリーTreeNodeに変換し、検索性能を向上するための

mapに着信keyが存在する場合、すなわちコード中のif(e!=null){...}は、処理後map中の配列中の実際のオブジェクトの個数が変化していないことを示し、これはe中の古い値を新しい値に置き換え、古い値を返し、ps:ここで新しい古い値を置き換え、主に第3ステップでサービスされ、3中の置換ロジックはここで実現され、実際のオブジェクトの個数が変化していないため、したがって、次のリセット配列サイズを実行しない論理を直接返す.

配列にオブジェクトを追加すると、現在の実際のオブジェクトの個数が臨界値(配列長x 0.75)より大きいかどうか、拡張配列サイズ(2倍)より大きいかどうか、拡張後のオブジェクト位置調整、より小さいかどうかを判断し、

を終了する.
get操作とremove操作
クラスはput、getのコードロジックはputの逆操作であり、removeのコードロジックはgetとほぼ同じであり、取り出し値を削除に変更するにすぎない.
個人ブログホームページ-微博-Github