Hashtable verdoppelt?

Question

Ich weiß nicht, ob der Titel sinnvoll ist, aber ich frage mich, wie sich eine Hashtabelle vergrößert, wenn Sie ihr Elemente hinzufügen?

Ist es wie die List<T>, wo es verdoppelt, wenn das Limit erreicht ist? Wenn ja, dann erstellt diese Verdopplung die Sammlung von Grund auf neu (dies kann auch für List<T> beantwortet werden, da ich nicht sicher bin, ob es das ist)?

Schließlich, wenn es tatsächlich von Grund auf neu erstellt, dann wäre diese besondere Add-Operation sehr teuer für den Benutzer, der nicht wissen würde, dass das Limit erreicht ist, richtig?

Answer 1

Ich glaube, sowohl Hashtable und Dictionary<TKey, TValue> erweitern auf die nächste Primzahl nach Verdoppelung der aktuellen Anzahl, z. 31 bis 67.

Wie ich es verstehe, ist ein Resize nicht beinhalten recomputing die Hashes (wie sie mit den Einträgen gespeichert sind), sondern umfasst jeden Eintrag in seine neue Eimer setzen, wo die Schaufel Zahl basiert sowohl auf den Hash-Code als auch auf die Bucket-Anzahl.

Sie haben nach List<T> gefragt - da ist es wirklich einfach. Die Liste wird von einem Array unterstützt, und Sie müssen nur ein neues Array mit der richtigen Größe erstellen und den Inhalt des aktuellen Arrays kopieren. Etwas wie:

private void Resize(int newCapacity) 
{ 
    T[] tmp = new T[newCapacity]; 
    Array.Copy(backingArray, tmp, backingArray.Length); 
    backingArray = tmp; 
} 

Answer 2

Die Größen werden nicht immer verdoppelt, haben aber abhängig von der Anzahl der Artikel ein variables Wachstum.

Für eine Liste ist dies nicht annähernd so teuer wie zum Beispiel eine Zeichenfolge oder ein Array neu zu erstellen, da nur die Zeiger von einer Liste zu einer anderen kopiert werden müssen, und dies kann sehr effizient erfolgen.

für ein Hashtable/Dictionary die Elemente müssen neu verteilt werden, und das kann sehr teuer sein. Am besten initialisieren Sie Ihre Hashtable mit einer geschätzten Größe im Voraus.

Answer 3

Die Hash-Tabelle Arbeiten mit Eimern, die jeweils mehrere Gegenstände halten kann (zumindest in den meisten Implementierungen gibt es einige, die andere Eimer bei Wiederverwendung von bereits verwendeten Eimer). Die Anzahl der Buckets ist normalerweise eine Primzahl, so dass die Division des Hashcodes durch die Anzahl der Buckets eine akzeptable Verteilung für "gute" Hashwerte ergibt.

Normalerweise gibt es einen bestimmten Füllfaktor, der das Hinzufügen von mehr Buckets auslöst und somit die Neuerstellung der Hashtabelle. Da die Hashwerte durch die Bucket-Anzahl dividiert werden, müssen die Instanzen entsprechend ihrem neuen Bucket-Index neu verteilt werden, was im Grunde eine Neuanlage von Grund auf ist. Für die .NET-Hashtabelle können Sie den "Ladefaktor" in some constructors angeben. Von MSDN:

Der Lastfaktor ist das maximale Verhältnis der Elemente zu Buckets. Eine kleinere Last Faktor bedeutet schnelleres Nachschlagen zu den Kosten des erhöhten Speicherverbrauchs. Ein Lastfaktor von 1,0 ist die beste Balance zwischen Geschwindigkeit und Größe.

Answer 4

aus der MSDN Seite auf Hashtable.Add():

Wenn Count geringer ist als die Kapazität von dem Hashtable ist, dieses Verfahren ein O (1) Betrieb. Wenn die Kapazität erhöht werden muss, um das neue Element aufzunehmen, wird diese Methode zu einer O (n) -Operation, wobei n Count ist.

Da List die gleiche Bemerkung hat, würde ich annehmen, dass sie intern hinsichtlich ihrer Speicherzuweisung ähnlich funktionieren.

Answer 5

warum graben nicht in reflector einige der Forschung zu tun, wenn interessiert:

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

Answer 6

Alles auf dem Hash-Implementierung hängt natürlich.

Einige Hashes verdoppeln, einige ändern ihre Größe auf eine andere beliebige Größe (z. B. die nächste Primzahl).

Die meisten Hashes müssen nach der Änderung ihrer Puffergröße, die "nur" Zeiger bewegt, aber immer noch linear mit der Hash-Größe ist, erneut aufgeräumt werden. Einige Hashes verwenden jedoch ein konsistentes Hashing, wodurch die Notwendigkeit, Elemente zu verschieben, reduziert wird (normalerweise muss nur ein kleiner Bruchteil der Elemente verschoben werden).