Was macht ein Hashset beim Initialisieren einer Sammlung mit Speicher?

Question

Ich stolperte über das folgende Problem.
Ich möchte ein hashset mit allen Zahlen von 1 bis 100.000.000. Ich habe versucht, den folgenden Code:

var mySet = new HashSet<int>(); 
for (var k = 1; k <= 100000000; k++) 
    mySet.Add(k); 

Dieser Code machen es nicht, da ich einen Speicherüberlauf rund um die 49mil irgendwo bekam. Das war auch ziemlich langsam und das Gedächtnis wuchs übermäßig.

Dann habe ich das versucht.

var mySet = Enumerable.Range(1, 100000000).ToHashSet(); 

wo ToHashSet() ist der folgende Code:

public static HashSet<T> ToHashSet<T>(this IEnumerable<T> source) 
{ 
    return new HashSet<T>(source); 
} 

ich wieder einen Speicherüberlauf bekam aber ich konnte mehr Zahlen setzen in dann mit dem vorherigen Code.

Die Sache, die Arbeit tut, ist die folgende:

var tempList = new List<int>(); 
for (var k = 1; k <= 100000000; k++) 
    tempList.Add(k); 

var numbers = tempList.ToHashSet(); 

Es dauert etwa 800 ms auf meinem System nur den tempList zu füllen, wo die Enumerable.Range() nur 4 Ticks nimmt!

Ich brauche diese HashSet oder sonst würde es zu viel Zeit brauchen, um Werte zu suchen (ich brauche es O (1)) und es wäre toll, wenn ich das am schnellsten machen könnte.

Nun ist meine Frage:
Warum verursachen die ersten beiden Methoden einen Speicherüberlauf, wo die dritte nicht?

Gibt es etwas spezielles HashSet mit dem Speicher beim Initialisieren?

Mein System hat 16GB Speicher, so dass ich ziemlich überrascht war, als ich die Überlauf-Ausnahmen bekam.

Answer 1

Wie bei anderen Kollektionstypen erhöht das HashSet automatisch seine Kapazität, wenn Sie Elemente hinzufügen. Wenn Sie eine große Anzahl von Elementen hinzufügen, führt dies zu einer großen Anzahl von Neuzuweisungen.

Wenn Sie es mit einem Konstruktor initialisieren, die eine IEnumerable<T> nimmt, wird er prüfen, ob die IEnumerable<T> in der Tat ist ein ICollection<T>, und wenn ja, initialisiert die Fähigkeit des HashSet auf die Größe der Sammlung.

Dies ist, was passiert in Ihrem dritten Beispiel - Sie fügen eine List<T>, die auch eine ICollection<T> ist, so dass Ihre HashSet eine Anfangskapazität gleich der Größe der Liste gegeben wird, so dass keine Umverteilungen erforderlich sind .

Sie werden noch effizienter, wenn Sie den List<T> Konstruktor verwenden, die einen Kapazitätsparameter nimmt, da dies Umschichtungen zu vermeiden, wenn die Liste Gebäude:

var noElements = 100000000; 
var tempList = new List<int>(noElements); 
for (var k = 1; k <= noElements; k++) 
    tempList.Add(k); 

var numbers = tempList.ToHashSet(); 

Wie für den Systemspeicher; Überprüfen Sie, ob dies ein 32-Bit- oder ein 64-Bit-Prozess ist. Ein 32-Bit-Prozess verfügt über maximal 2 GB Arbeitsspeicher (3 GB, wenn Sie den Startschalter/3GB verwendet haben).

Im Gegensatz zu anderen Sammlungstypen (z.List<T>, Dictionary<TKey,TValue>), HashSet<T> hat keinen Konstruktor, der einen capacity Parameter verwendet, um die Anfangskapazität festzulegen. Wenn Sie eine mit einer großen Anzahl von Elementen initialisieren möchten, besteht die effizienteste Methode wahrscheinlich darin, zuerst die Elemente zu einem Array oder List<T> mit der entsprechenden Kapazität hinzuzufügen und dann dieses Array oder diese Liste an den HashSet<T>-Konstruktor zu übergeben.

Answer 2

HashSet wächst durch Verdoppelung, und diese Zuweisung bewirkt, dass der verfügbare Speicher überschritten wird.

Auf einem 64-Bit-System ein HashSet nach oben von 89 Millionen Artikeln halten kann.

Auf einem 32-Bit-System die Grenze liegt bei etwa 61700000 Artikel.

Deshalb sollten Sie Speicherüberlauf Ausnahme

für weitere Informationen

http://blog.mischel.com/2008/04/09/hashset-limitations/

Answer 3

Ich denke, HashSet<T> bekommen, wie die meisten .net Sammlungen, verwendet das Array für Wachstum Verdoppelung Strategie. Leider gibt es keine Konstruktorüberladungen, die eine Kapazität beanspruchen.

Aber wenn es für ICollection<T> prüft und verwendet ICollection<T>.Count als Anfangskapazität können Sie eine rudimentäre Implementierung von ICollection<T> implementieren, die GetEnumerator() und Count implementiert. Auf diese Weise können Sie direkt die HashSet<T> füllen, ohne eine temporäre List<T> zu materialisieren.

Answer 4

Wenn Sie 100 setzen Millionen Ints in eine Hashset, die 1,5 GB (meine Maschine) verbrauchen Wenn Sie eine Bool erstellen [100000000], wo Sie jede Zahl festgelegt haben Sie auf true hatte es dauert nur 100 MB und auch nachschlägt schneller als ein Hashset. Dies nimmt den Ints-Bereich von 0-100000000