2

容量が増えると、ハッシュテーブルが正しいインデックスをどのように見つけるのか疑問に思いました。たとえば、デフォルトの容量が10のハッシュテーブルがあるとします。次に、（key、value）ペア[14、"hello1"]を追加する必要があります。

以下のインデックスメカニズムを使用して上記のキー「14」に対して取得するインデックスは「4」です。したがって、ハッシュテーブルはこの（key、value）ペアをインデックス4内に保存します。

int index = key.GetHashCode() % 10

ここで、ハッシュテーブルにアイテムを追加し続け、負荷率に到達します。それでは、サイズを変更します。そして、20に急いでサイズ変更すると仮定しましょう。

次に、古いキー「14」をこのハッシュテーブルで検索します。そして、インデックスメカニズムに従って、このキーのインデックスを14として取得します。したがって、インデックス14からハッシュテーブルの検索を開始しますが、理想的にはインデックス4にあります。

だから私の質問は、ハッシュテーブルがサイズ変更時に既存のキーインデックスをどのように追跡するかです。または、ハッシュテーブルはサイズ変更時に既存のすべてのキーを再ハッシュしますか？

4

2 に答える 2

2

ハッシュテーブルを読みたいと思うかもしれませんが、私が見逃していると思う概念は次のとおりです。

  • 「asdf」などの特定のキーには、特定の32ビットintハッシュコードがあります。
  • To get the position within indexed storage, you apply a modulus (%) of hashCode % length -- so if you grow your table from 10 to 20, the result changes to a new index. Implementations will of course go and make sure each existing entry is in the proper bucket in the new table.
于 2012-12-10T01:58:14.710 に答える
1

.Netの共有ソースCLI実装を調べましたが、拡張時にエントリが再ハッシュされているようです。ただし、.GetHashCode（）を使用してHashCodeを再計算する必要はありません。

実装を見るexpand()と、次の手順が実行される方法がわかります。

  1. 一時的なバケット配列が作成され、現在のサイズの2倍を超える最小の素数にサイズ設定されます。
  2. 新しいアレイは、古いバケットアレイから再ハッシュすることで移入されます。

。

for (nb = 0; nb < oldhashsize; nb++)
{
    bucket oldb = buckets[nb];
    if ((oldb.key != null) && (oldb.key != buckets))
    {
        putEntry(newBuckets, oldb.key, oldb.val, oldb.hash_coll & 0x7FFFFFFF);
    }
}



private void putEntry (bucket[] newBuckets, Object key, Object nvalue, int hashcode)
{
    BCLDebug.Assert(hashcode >= 0, "hashcode >= 0");  // make sure collision bit (sign bit) wasn't set.

    uint seed = (uint) hashcode;
    uint incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)newBuckets.Length - 1)));

    do 
    {
        int bucketNumber = (int) (seed % (uint)newBuckets.Length);

        if ((newBuckets[bucketNumber].key == null) || (newBuckets[bucketNumber].key == buckets)) 
        {
            newBuckets[bucketNumber].val = nvalue;
            newBuckets[bucketNumber].key = key;
            newBuckets[bucketNumber].hash_coll |= hashcode;
            return;
        }
        newBuckets[bucketNumber].hash_coll |= unchecked((int)0x80000000);
        seed += incr;
        } while (true);
    }
}

新しいアレイが構築され、以降の操作で使用されます。

また、Hashtable.Add（）に関するMSDNから：

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

于 2012-12-10T01:57:58.480 に答える