20

なぜList<T>容量を2倍に増やすのですか？

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

なぜDictionary<K,V>素数を容量として使用するのですか？

private void Resize()
{
    int prime = HashHelpers.GetPrime(this.count * 2);
    int[] numArray = new int[prime];
    for (int i = 0; i < numArray.Length; i++)
    {
        numArray[i] = -1;
    }
    Entry<TKey, TValue>[] destinationArray = new Entry<TKey, TValue>[prime];
    Array.Copy(this.entries, 0, destinationArray, 0, this.count);
    for (int j = 0; j < this.count; j++)
    {
        int index = destinationArray[j].hashCode % prime;
        destinationArray[j].next = numArray[index];
        numArray[index] = j;
    }
    this.buckets = numArray;
    this.entries = destinationArray;
}

なぜそれも2を掛けないのですか？どちらも継続的なメモリ位置の検索を扱っています...正しいですか？

4

6 に答える 6

2

衝突の可能性を減らすため、ハッシュテーブルのサイズに素数を使用するのが一般的です。

コードでわかるように、ハッシュテーブルは通常、モジュロ演算を使用してエントリが属するバケットを検索します。

int index = destinationArray[j].hashCode % prime;

hashCode関数の結果がとりわけ{x、2x、3x、4x、5x、6x ...}であるとすると、これらはすべて、m個のバケットにクラスター化されます。ここでm = table_length / GreatestCommonFactor（ table_length、x）。（これを検証/導出するのは簡単です）。これで、クラスタリングを回避するために次のいずれかを実行できます。

  1. {x、2x、3x、4x、5x、6x ...}のように、別のhashCodeの倍数であるhashCodeを生成しすぎないように注意してください。ただし、hashTableに何百万ものエントリ。

  2. または、GreatestCommonFactor（table_length、x）を1に等しくすることによって、つまりtable_lengthをxと互いに素にすることによって、mをtable_lengthに等しくします。また、xがほぼ任意の数になる可能性がある場合は、table_lengthが素数であることを確認してください。

（http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.htmlから）

HashHelpers.GetPrime(this.count * 2)

素数を返す必要があります。HashHelpers.GetPrime（）の定義を見てください。

于 2013-01-30T08:20:40.790 に答える
1

ディクショナリは、GetHashCode値に応じて、すべてのオブジェクトをバケットに配置します。つまり
Bucket[object.GetHashCode() % DictionarySize] = object;
、衝突の可能性を回避するために、サイズに素数を使用します。おそらく、除数が多いサイズは、設計が不十分なハッシュコードには適していません。

于 2013-01-30T08:17:25.357 に答える
1

SOの質問から;

ディクショナリまたはハッシュテーブルは、キーのハッシュに依存して、対応するストア（配列）を検索するための小さなインデックスを取得します。したがって、ハッシュ関数の選択は非常に重要です。一般的な選択は、キーのハッシュコードを取得し（適切なランダム分布が得られるように）、コードを素数で除算し、リマインダーを使用して固定数のバケットにインデックスを付けることです。これにより、任意の大きなハッシュコードを、検索する配列を定義できる小さな数値の有界セットに変換できます。したがって、素数で配列サイズを設定することが重要です。その場合、サイズの最適な選択は、必要な容量よりも大きい素数になります。そして、それはまさに辞書の実装です。

List<T>arrayデータを格納するためにsを使用します。アレイの容量を増やすには、アレイを新しいメモリ位置にコピーする必要があります。これには時間がかかります。配列のコピーの発生を減らすために、listは容量を2倍にすると思います。

于 2013-01-30T08:28:05.637 に答える
1

私はコンピューター科学者ではありませんが...

ほとんどの場合、これはHashTableの負荷率（最後のリンクは数学の定義にすぎません）に関連しており、混乱を招かないため、数学の聴覚ではないため、次のように定義することが重要です。

loadFactor = FreeCells/AllCells

これは次のように書くことができます 

loadFactor = (AllBuckets - UsedBuckets)/AllBuckets

loadFactorハッシュマップで衝突の確率を定義します。したがって、素数を使用することにより、

..は1より大きい自然数であり、1とそれ自体以外に正の約数はありません。

ハッシュマップでの衝突のリスクを減らします（ただし、消去はしません）。

loadFactor傾向がある場合は0、より安全なハッシュマップがあるため、常に可能な限り低く保つ必要があります。MSブログによると、その値loadFactor（最適な値）は周囲にある必要があることがわかった0.72ので、それが大きくなると、最も近い素数に続いて容量を増やします。

編集

これをより明確にするために：素数を持つことで、.NETディクショナリにあるハッシュのこの具体的な実装でハッシュをできるだけ均一に分散させることができます。これは、値の取得の効率ではなく、使用されるメモリの効率と衝突リスクの低減です。

お役に立てれば。

于 2013-01-30T08:28:09.210 に答える
1

Dictionaryバケット間のハッシュコードの分散がより均一になるように、ヒューリスティックが必要です。

.NETDictionaryは素数のバケットを使用してそれを行い、次のようにバケットインデックスを計算します。

int num = this.comparer.GetHashCode(key) & 2147483647; // make hash code positive
// get the remainder from division - that's our bucket index
int num2 = this.buckets[num % ((int)this.buckets.Length)];

大きくなると、バケットの数が2倍になり、さらにいくつか追加して、数を再び素数にします。

可能なヒューリスティックはそれだけではありません。HashMapたとえば、Javaは別のアプローチを採用しています。そこにあるバケットの数は常に2の累乗であり、成長するとバケットの数が2倍になります。

resize(2 * table.length);

ただし、バケットインデックスを計算すると、ハッシュが変更されます。

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
    return h & (length-1);
}

// from put() method
int hash = hash(key.hashCode()); // get modified hash
int i = indexFor(hash, table.length); // trim the hash to the bucket count

List一方、ヒューリスティックは必要ないので、気にしませんでした。

追加Add：成長動作は、の複雑さにまったく影響しません。Dictionary、HashMapおよびListそれぞれがAddO（1）の複雑さを償却しています。

Add成長操作はO（N）を取りますが、N回しか発生しないため、成長操作を発生させるには、 N回呼び出す必要があります。N = 8の場合、Nsの実行にかかる時間にAddは次の値があります。

O（1）+ O（1）+ O（1）+ O（1）+ O（1）+ O（1）+ O（1）+ O（N）= O（N）+ O（N）= O（2N）= O（N）

したがって、NAddはO（N）を取り、次にAddO（1）を取ります。

于 2013-01-30T08:41:26.737 に答える
0

いくつかの償却された実行時間を保証するために、サイズ変更が必要な場合は、（たとえば、加法定数によって容量を増やすのではなく）一定の係数で容量を増やす必要があります。たとえば、配列ベースのリストの最後に追加または削除するにはO(1)、リストの内容をコピーするために必要な容量を増減する必要がある場合を除いて、O(n)時間がかかります。容量を一定の係数で変更すると、償却されたランタイムがまだであることが保証されますO(1)。係数の最適値は、予想される使用法によって異なります。ウィキペディアに関するいくつかの詳細情報。

プライムになるハッシュテーブルの容量を選択することは、アイテムの分散を改善するために使用されます。が素数の場合、一様分布でないbucket[hash % capacity]場合は、より一様分布になります。（その背後にある数学を与えることはできませんが、良いリファレンスを探しています。）これと最初のポイントの組み合わせは、実装が行うこととまったく同じです-容量を（少なくとも）2倍に増やし、容量は最高です。hashcapacity

于 2013-01-30T09:36:32.387 に答える