ハッシュマップの展開メカニズムは何ですか?

ハッシュマップの拡張メカニズムは、容量を再計算し、元の配列を新しい配列に置き換えることです。元の配列のすべてのデータを再計算し、新しい配列を挿入し、新しい配列をポイントします。配列が容量拡張前の最大値に達している場合は、しきい値を最大の整数に直接設定して返します。

#このチュートリアルの動作環境: Windows7 システム、Java8、Dell G3 コンピューター。

サイズ変更とは何ですか?

容量拡張 (サイズ変更): 容量を再計算し、継続的に HashMap オブジェクトに要素を追加します。HashMap オブジェクト内の配列がそれ以上の要素を読み込むことができない場合、オブジェクトは、より多くの要素を収容できるようにするための配列の長さ。もちろん、Java では配列を自動的に拡張することはできません。その方法は、既存の容量の小さい配列を新しい配列に置き換えることです。水を入れるために小さなバケツを使用するのと同じように、より多くの水を保持したい場合は、より大きなバケットに変更します。

容量はいつ拡張されますか?

コンテナに要素を追加する際に、現在のコンテナ内の要素の数が判定され、それがしきい値(threshold)以上であれば、つまりその数が判定されます。現在のコンテナ内の要素の数が現在の配列の長さを超えています。負荷係数の値を乗算すると、自動的に拡張されます。

ハッシュマップ拡張の原理

ハッシュマップ拡張は、容量を再計算し、ハッシュマップに要素を継続的に追加することです。ハッシュマップが新しい要素をロードできない場合、オブジェクトはより多くの要素を収容できるように配列容量を拡張する必要があります。

HashMap の容量拡張特性では、負荷率が大きいほどスペース使用率が高く、拡張前に埋める必要がある要素が多くなり、PUT 操作が速くなりますが、リンクされたリストは長く渡されやすく、ハッシュの衝突確率が高く、get 操作が遅くなります。ロード係数が小さいほど、取得操作が速くなり、リンクされたリストが短くなり、ハッシュ衝突の可能性が低くなります。ただし、スペースの使用率は低いです。 put 要素が多すぎると頻繁に拡張が発生し、パフォーマンスに影響を与えます。

HashMap の容量拡張原理: Hashmap メソッドは、元の配列を新しい配列に置き換え、元の配列内のすべてのデータを再計算し、新しい配列を挿入します。そして、新しい配列をポイントします。拡張前に配列が最大値に達している場合、しきい値は最大の整数に直接設定されて返されます。

拡張プロセス

以下では、ソース コード、画像、およびテキストの説明を使用して、ハッシュマップ。

/**
 * HashMap 添加节点
 *
 * @param hash        当前key生成的hashcode
 * @param key         要添加到 HashMap 的key
 * @param value       要添加到 HashMap 的value
 * @param bucketIndex 桶，也就是这个要添加 HashMap 里的这个数据对应到数组的位置下标
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    //数组扩容条件：1.已经存在的key-value mappings的个数大于等于阈值
    //             2.底层数组的bucketIndex坐标处不等于null
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//扩容之后，数组长度变了
        hash = (null != key) ? hash(key) : 0;//为什么要再次计算一下hash值呢？
        bucketIndex = indexFor(hash, table.length);//扩容之后，数组长度变了，在数组的下标跟数组长度有关，得重算。
    }
    createEntry(hash, key, value, bucketIndex);
}

/**
 * 这地方就是链表出现的地方，有2种情况
 * 1，原来的桶bucketIndex处是没值的，那么就不会有链表出来啦
 * 2，原来这地方有值，那么根据Entry的构造函数，把新传进来的key-value mapping放在数组上，原来的就挂在这个新来的next属性上了
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K, V> e = table[bucketIndex];
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);
    size++;
}

上記の addEntry メソッドでは、サイズ (現在のコンテナー内の要素の数) がしきい値 (配列の長さと負荷係数を掛けた値) 以上で、基になる配列のbucketIndex 座標がnull に等しい場合、Expansion (resize) が実行されます。そうしないと、拡張は行われません。

以下では、 拡張プロセスに焦点を当てます:

void resize(int newCapacity) {   //传入新的容量
    Entry[] oldTable = table;    //引用扩容前的Entry数组
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
        threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
        return;
    }

    Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
    transfer(newTable); 此行有遗漏，勘误见下面引用   //！！将数据转移到新的Entry数组里
    table = newTable;                           //HashMap的table属性引用新的Entry数组
    threshold = (int) (newCapacity * loadFactor);此行有遗漏，勘误见下面引用//修改阈值
}

wenni328 ブロガーによって修正されました: transfer(newTable); ==> transfer(newTable, initHashSeedAsNeeded(newCapacity));
threshold = (int) (newCapacity *loadFactor); ==> しきい値 = ( int)Math.min(newCapacity *loadFactor, MAXIMUM_CAPACITY 1);

展開前に、まず展開前の配列の参照アドレスを取得してoldTable変数に格納し、長さが拡張前の配列の容量が int 型に格納される最大値に達した場合、配列の容量が最大値に達し拡張できないため、拡張は中止されます。

下の図は、プログラムが Entry[] newTable = new Entry[newCapacity]; コードを実行した後の状態を示しています:

## ここでは、大容量 配列は、既存の配列を小さい容量に置き換えるために使用され、transfer() メソッドは、元の Entry 配列の要素を新しい Entry 配列にコピーします。

void transfer(Entry[] newTable) {
    Entry[] src = table;                   //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            do {
                Entry<K, V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                e.next = newTable[i]; //标记[1]
                newTable[i] = e;      //将元素放在数组上
                e = next;             //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

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

newTable[i] の参照は e.next に割り当てられます。つまり、

は単一リンクリストの先頭挿入メソッドを使用します、同じ位置の新しい要素は常にこのようにして、インデックスに最初に配置された要素は、最終的にエントリ チェーンの最後に配置されます (ハッシュの競合が発生した場合)。古い配列内の同じエントリ チェーン内の要素は、インデックス位置を再計算した後、新しい配列内の異なる位置に配置される場合があります。

転送プロセスを以下の図の形式で説明します (以下の図の赤い文字は上の図との違いを示します。以下の図はこのようなもので、赤い文字の説明は省略されます)繰り返し)

以下の図は、プログラムが src[j] = null; コードを実行した後の状態を示しています (これは最初のループ中の状態です)。

まず、配列 table[] の参照アドレスを配列 src[] に代入します。

次に、Entry e = src[j]; は、src[j]位置の連結リストを変数 e に転送して保存します。 src[j] のリンク リストは保存用に e に与えられているため、大胆に src[j]=null; を設定して、ガベージ コレクションを待つことができます。

下の図は、プログラムが Entry next = e.next; コードを実行した後の状態を示しています (これは最初のループ中の状態です)。

最初に e.next の値が next 変数にバックアップされますが、後続のコードで e.next のポインタが変更されるため、ここに e.next の値がバックアップされます。

下の図は、プログラムが e.next = newTable[i]; コードを実行した後の状態を示しています (これは最初のループ中の状態です)。

newTable[3] の値が null であるため、上の図に示すように、e.next は null になります。

下の図は、プログラムが newTable[i] = e; コードを実行した後の状態を示しています (これは最初のループ中の状態です)。

次の図は、プログラムが e = next; コードを実行した後の状態を示しています (これは最初のループ中の状態です):

上に示すように、Entry1このノードは newTable に正常に挿入され、サイクルの最後では e!=null と判定されるため、すべてのノードが newTable に移動されるまで上記の処理が繰り返されます。

概要

展開は特にパフォーマンスを重視する操作であるため、プログラマが HashMap を使用するときは、マップのサイズを推定し、初期化時にそれを指定します。頻繁なマップ拡張を避けるためのおおよその値。

負荷係数は変更することも、1 より大きくすることもできますが、よほど特殊な状況でない限り、簡単に変更しないことをお勧めします。

HashMap はスレッド安全ではありません。並行環境で HashMap を同時に操作しないでください。ConcurrentHashMap を使用することをお勧めします。

JDK1.8 では、HashMap のパフォーマンスを大幅に最適化するために赤黒ツリーが導入されています。

プログラミング関連の知識について詳しくは、

プログラミング教育

をご覧ください。 ！

以上がハッシュマップの展開メカニズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。