3

N個の要素に対してHashMap/HashSetを作成するには、通常、これを行うnew HashMap((int)(N/0.75F)+1)のは面倒です。

なぜライブラリはそもそもこれをnew HashMap(N)処理せず、この計算を処理するように（N個の要素まで再ハッシュすべきではない）初期化を許可するの(int)(N/0.75F)+1ですか？

4

3 に答える 3

2

アップデート

変更された質問を反映するように更新します。いいえ、そのような標準 API はありませんが、Maps.newHashMapWithExpectedSize(int)guavaはメソッドがあるようです:

成長することなく要素を保持するHashMapのに十分な「初期容量」を持つインスタンスを作成します。expectedSize

(int)(N/0.75F)+1 に初期化する必要があります

いいえ、ありません。HashMapother から新規作成する場合Map、HashMap既定では最初に容量が計算されます。

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}

要素を 1 つずつ追加する場合も、同じプロセスが発生します。

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        //...
    }

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

コンストラクターを使用する唯一の理由HashMap(int initialCapacity, float loadFactor)は、 に格納する要素の数が最初からわかっている場合です。これによりHashMap、後でサイズ変更や再ハッシュを回避できます (マップは最初から正しいサイズです)。

興味深い実装の詳細の 1 つは、初期容量が最も近い 2 のべき乗にトリミングされることです (参照:なぜ ArrayList は 1.5 の割合で増加しますが、Hashmap の場合は 2 ですか? ):

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

したがって、HashMap定義どおりの正確な容量が必要な場合は、2 の累乗を使用してください。

別のものを選択するとloadFactor、スペースとパフォーマンスを交換できます。値が小さいほど、メモリが増えますが、衝突が少なくなります。

于 2012-11-11T09:18:16.437 に答える
1

次のプログラムを実行しました

public static void main(String... args) throws IllegalAccessException, NoSuchFieldException {
    for (int i = 12; i < 80; i++) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>((int) Math.ceil(i / 0.75));
        int beforeAdding = Array.getLength(getField(map, "table"));
        for (int j = 0; j < i; j++) map.put(j, j);
        int afterAdding = Array.getLength(getField(map, "table"));
        map.put(i, i);
        int oneMore = Array.getLength(getField(map, "table"));
        System.out.printf("%,d: initial %,d, after N %,d, after N+1 %,d%n ",
                i, beforeAdding, afterAdding, oneMore);
    }
}

private static <T> T getField(Map<Integer, Integer> map, String fieldName) throws NoSuchFieldException, IllegalAccessException {
    Field table = map.getClass().getDeclaredField(fieldName);
    table.setAccessible(true);
    return (T) table.get(map);
}

印刷する

 12: initial 16, after N 16, after N+1 32
 13: initial 32, after N 32, after N+1 32
 .. deleted ..
 24: initial 32, after N 32, after N+1 64
 25: initial 64, after N 64, after N+1 64
 .. deleted ..
 47: initial 64, after N 64, after N+1 64
 48: initial 64, after N 64, after N+1 128
 49: initial 128, after N 128, after N+1 128
 .. deleted ..
 79: initial 128, after N 128, after N+1 128

これは、デフォルトの初期化子の初期容量が次の 2 の累乗に丸められることを示しています。この値の問題は、これを最終的なサイズにしたい場合、サイズ変更を避けたい場合は負荷係数を考慮する必要があることです。理想的には、Map コピー コンストラクターが行うように、そうする必要はありません。

于 2012-11-11T11:11:03.317 に答える
0

要素を追加すると、ほとんどの実装は自動的に大きくなります。ほとんどの実装のパフォーマンスも、コンテナーがいっぱいになると低下する傾向があります。そのため、そもそも負荷率があります。空きスペースを残すことです。

于 2012-11-11T09:08:35.007 に答える