2

Java HashMap のソース コードから、スペースのしきい値に達すると、そのスペースが 2 倍に拡張されることは明らかです。

6 つの要素すべてがリンクされた方法で同じインデックスの下に格納されるユース ケースについて考えました。7 番目の要素が到着すると、しきい値 7 (10*.75) の HashMap (サイズ 10) が展開されます。ここでは、すべてが 1 つのインデックスの下に保存されるため、実際には拡張の必要はありません。

親切に私を教えてください

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

        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);
            table = newTable;
            threshold = (int)(newCapacity * loadFactor);
        }
4

3 に答える 3

3

HashMapはこれらのエントリを保持できるため、サイズを変更する必要はないと言います。

ただし、HashMap理想的には一定のアクセス時間を提供する必要があります ( O(1))。このアクセス時間を提供しようとするために、サイズ変更が行われます。バケットを再編成することにより、キーのルックアップは理想的には値が 1 つだけのバケットを参照する必要があります (エントリのリストを繰り返し処理することを避けるため)。

メソッドには、次のget()行があります。

for (Entry<K,V> e = table[indexFor(hash, table.length)];

HashMap はindexFor()メソッドを使用してバケットを識別し、バケットを反復処理して一致するキーを見つけます。これを最適化するために、反復は理想的には 1 回だけ行う必要があります (バケット ルックアップを避けることはできません)。

intこれは、ハッシュコードが理想的には範囲 (2^31-1)に均等に分散されていることを示しています。オブジェクトのハッシュコードを定数 (たとえば 1) にすることはできますが、HashMap はすべてのエントリを 1 つのバケットにダンプする以外に何もできないことがわかり、その結果、パフォーマンスが影響を受けます。

于 2012-12-27T10:26:08.807 に答える
1

それは単なる設計上の決定です。おそらく、マップは取得と保存が非常に高速である必要があり、非常に多くのエントリをリンクすると、パフォーマンスに影響するという事実に基づいています。したがって、再ハッシュすると、アイテムが 1 つのバケットだけにリンクされたままになるのではなく、おそらくバケット全体にアイテムがまばらになります。

于 2012-12-27T10:30:22.137 に答える
0

の取引です。サイズが小さいときに同じバケットにあるすべての要素は、サイズが大きくなると分散します。これにより、パフォーマンスが向上します。

于 2014-09-11T18:31:21.657 に答える