2

タイトルの意味がわからないのですが、アイテムを追加するとハッシュテーブルがどのように拡大するのか気になります。

List<T>限界に達すると2倍になるようなものですか？もしそうなら、この倍増はコレクションをゼロから再作成しList<T>ますか?

最後に、実際にゼロから再作成する場合、この特定の追加操作は、制限に達したことを知らないユーザーにとって非常に高価になりますよね?

4

6 に答える 6

5

私は両方を信じてHashtable、Dictionary<TKey, TValue>現在の数を2倍にした後、次の素数、たとえば31から67に拡張します。

私が理解しているように、サイズ変更では、ハッシュを再計算する必要はありません（エントリとともに保存されるため）が、各エントリを新しいバケットに配置する必要があります。バケット番号は、ハッシュコードとバケット数の両方に基づいています。

あなたは質問しましたList<T>-それは本当に簡単です。リストは配列に裏打ちされており、適切なサイズの新しい配列を作成し、現在の配列の内容をコピーする必要があります。何かのようなもの：

private void Resize(int newCapacity)
{
    T[] tmp = new T[newCapacity];
    Array.Copy(backingArray, tmp, backingArray.Length);
    backingArray = tmp;
}
于 2009-04-16T19:16:20.517 に答える
1

ハッシュテーブルはバケットを使用して機能します。バケットはそれぞれ複数のアイテムを保持できます（少なくともほとんどの実装では、すでに使用されているバケットの場合に他のバケットを再利用するものもあります）。バケットの数は通常素数であるため、ハッシュコードをバケットの数で割ると、「適切な」ハッシュの許容可能な分布が返されます。

通常、バケットの追加、したがってハッシュテーブルの再構築をトリガーする特定のフィルファクターがあります。ハッシュはバケット数で除算されるため、インスタンスは新しいバケットインデックスに従って再配布する必要があります。これは、基本的に最初から再作成されます。

.NETハッシュテーブルの場合、一部のコンストラクターで「負荷率」を指定できます。MSDNから：

負荷率は、要素とバケットの最大比率です。負荷率が小さいということは、メモリ消費量が増える代わりに、ルックアップが高速になることを意味します。負荷率1.0は、速度とサイズの最適なバランスです。

于 2009-04-16T19:17:14.853 に答える
0

サイズは常に2倍になるとは限りませんが、アイテムの数に応じてサイズが大きくなります。

リストの場合、これは、たとえば文字列や配列を再作成するほどコストがかかりません。これは、あるリストから別のリストにポインタをコピーするだけでよく、これを非常に効率的に実行できるためです。

ハッシュテーブル/辞書の場合、アイテムを再配布する必要があり、これは非常に高額になる可能性があります。事前に推定サイズでハッシュテーブルを初期化するのが最善です。

于 2009-04-16T19:14:45.000 に答える
0

Hashtable.Add（）のMSDNページから：

Countがハッシュテーブルの容量よりも少ない場合、このメソッドはO（1）操作です。新しい要素に対応するために容量を増やす必要がある場合、このメソッドはO（n）演算になります。ここで、nはCountです。

Listにも同じ意見があるので、メモリ割り当てに関しては内部的に同じように機能すると思います。

于 2009-04-16T19:18:17.407 に答える
0

興味があれば、リフレクターを掘り下げて調査してみませんか。

private void Insert(object key, object nvalue, bool add)
{
    uint num;
    uint num2;
    if (key == null)
    {
        throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
    }
    if (this.count >= this.loadsize)
    {
        this.expand();
    }
    else if ((this.occupancy > this.loadsize) && (this.count > 100))
    {
        this.rehash();
    }
    uint num3 = this.InitHash(key, this.buckets.Length, out num, out num2);
    int num4 = 0;
    int index = -1;
    int num6 = (int) (num % this.buckets.Length);
Label_0071:
    if (((index == -1) && (this.buckets[num6].key == this.buckets)) && (this.buckets[num6].hash_coll < 0))
    {
        index = num6;
    }
    if ((this.buckets[num6].key == null) || ((this.buckets[num6].key == this.buckets) && ((this.buckets[num6].hash_coll & 0x80000000L) == 0L)))
    {
        if (index != -1)
        {
            num6 = index;
        }
        Thread.BeginCriticalRegion();
        this.isWriterInProgress = true;
        this.buckets[num6].val = nvalue;
        this.buckets[num6].key = key;
        this.buckets[num6].hash_coll |= (int) num3;
        this.count++;
        this.UpdateVersion();
        this.isWriterInProgress = false;
        Thread.EndCriticalRegion();
    }
    else if (((this.buckets[num6].hash_coll & 0x7fffffff) == num3) && this.KeyEquals(this.buckets[num6].key, key))
    {
        if (add)
        {
            throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", new object[] { this.buckets[num6].key, key }));
        }
        Thread.BeginCriticalRegion();
        this.isWriterInProgress = true;
        this.buckets[num6].val = nvalue;
        this.UpdateVersion();
        this.isWriterInProgress = false;
        Thread.EndCriticalRegion();
    }
    else
    {
        if ((index == -1) && (this.buckets[num6].hash_coll >= 0))
        {
            this.buckets[num6].hash_coll |= -2147483648;
            this.occupancy++;
        }
        num6 = (int) ((num6 + num2) % ((ulong) this.buckets.Length));
        if (++num4 < this.buckets.Length)
        {
            goto Label_0071;
        }
        if (index == -1)
        {
            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed"));
        }
        Thread.BeginCriticalRegion();
        this.isWriterInProgress = true;
        this.buckets[index].val = nvalue;
        this.buckets[index].key = key;
        this.buckets[index].hash_coll |= (int) num3;
        this.count++;
        this.UpdateVersion();
        this.isWriterInProgress = false;
        Thread.EndCriticalRegion();
    }
}
于 2009-04-16T19:18:34.617 に答える
0

もちろん、それはすべてハッシュの実装に依存します。

ハッシュが2倍になるものもあれば、サイズを他の任意のサイズ（たとえば、次の素数）に変更するものもあります。

ほとんどのハッシュは、バッファサイズを変更した後に再ハッシュが必要になります。これは、ポインタを「移動するだけ」ですが、ハッシュサイズに比例します。ただし、一部のハッシュではコンシステントハッシュを使用するため、要素を移動する必要が少なくなります（通常、移動する必要があるのは要素のごく一部のみです）。

于 2009-04-16T19:18:37.487 に答える