Hashtables fressen Speicher ?

[JJB]

Hallo,

vielleicht wurde das schon an anderer Stelle besprochen, ich hab es aber nicht gefunden.

Ich experimentiere derzeit mit verschachtelten Hashtables. Der Schlüssel ist ein Buchstabe das value eine weitere Hashtable. Es gibt pro table maximal 35 Elemente, ab der 3. Stufe gibt jedoch meist nur 2-5 Elemente. Spätestens ab der 5. Stufe gibt nur noch ein Element pro Hashtable.
An sich sollte das ein überschaubarer "Baum" sein und nicht viel Platz verschwenden.

Was mich jetzt irritiert ist, dass bei Graden ab der 5. Stufe der benötigte Speicher ausufert. Von 5 MB bei 2 Stufen und 30 MB bei 3 kommen wir sehr schnell zu fast 1 GB bei 12 Stufen, obwohl sich zwischen der 5. und der 12. Stufe nichts mehr ändert. Jede Hashtable hat nur ein Element, das wiederum nur eines enthält. Warum fressen die soviel Platz ?

Jemand einen Tip ?

 

[Norbert Eder]

Grob überschlagen:

Die Bestimmung der Größe eines Objektes ist grundsätzlich nicht so einfach. Valuetypen können mit sizeof() abgefragt werden. Über einen Umweg kann dies auch bei beliebigen Objekten gemacht werden (näherungsmäßig). Nämlich: Mit dem BinaryFormatter binär serialisieren, in einen MemoryStream schreiben und Größe auslesen.

Eine frisch initialisierte Hashtable hat demzufolge eine Größe von 240 Bytes. Fügt man nun ein Element hinzu (key = "A", value = null, wird eine Hashtable angehängt, kommt noch die Größe der Referenz hinzu) dann erhöht sich der Speicherbedarf auf 248 Bytes.

Gut. Nun nehme man einen Baum mit einer Root und 5 Ebenen. Jede Ebene besitzt 35 Knoten, dann ergeben sich pro Ebene folgende Zahlen:

1
36
1.296
46.656
1.679.616

Multipliziere das auf und du kommst auf den ungefähren Speicherbedarf. Natürlich kommt da noch ein wenig Overhead dazu, da du ja den Tree auch aufbauen musst etc.

Grundsätzlich würde ich also meinen, dass die Hashtable das absolut falsche Werkzeug dafür ist ;-)

 

[JJB]

Hallo,

Es ist wie erwähnt nicht so, dass der Baum voll ausgelastet ist. Auf der ersten Ebene gibt es bis zu 35 Elementen auf der 2. nur noch ca. 6 und in der 3. Ebene nur noch 3. Dann sind es fast nur noch einzlne. Wenn ich vom schlimmsten Fall ausgehe habe ich 35 x 6 x 3 x 2 x 1 x 1 x.... Elemente also ca 1200 bis maximal 1300. Dazu kommen die Hashtables. Fressen die schon so viel Speicher ?

Was wäre eine Alternative ? Arraylists ? Die haben keine Schlüssel. Vielleicht XML Knoten ? Mit einem Treeview habeich es probiert. Auch kein Schlüssel und keine Möglichkeit großartig Daten zu speichern. Zudem sind Elemente aus Windows.Forms auch keine Speicherfreunde.

Ich dachte Hashtables sind sehr platzsparend. Muss ich bei der Initialisierung etwas beachten ? Oder sollte ich sie regelmäßig löschen und neu erzeugen ?

 

[Norbert Eder]

Schau mal:
http://msdn2.microsoft.com/en-us/vcsharp/aa336800.aspx

Da hast du genug Informationen über Bäume drinnen. Zudem würde ich auf bewährte Algorithmen und Datenstrukturen zurückgreifen.

 

[JJB]

Mit diesen AVL, BST, Queues, Stacks oder irgendwelchen Binärbäumen fange ich nicht wirklich was an. Aber da steht was davon, dass bei fehlender Angabe der Initialisierungsgröße einer Hashtable die Table jedesmal vergrößert (verdoppelt?) wird, wenn ich einen Wert ergänze. Dies führt offenbar zum Speicherproblem. Den genauen Hintergrund dieses Loadfaktors kann ich nicht so ganz nachvollziehen.

Nicht dass ich jetzt verstehen würde, was das soll, englisches Fachchinesisch ist schwer zu durchschauen.

Ich werd jetzt mal versuchen die Schlüssel der Hashtables zu verkleinern und teste mal ob es einen Unterschied macht, wenn ich Initialisierungsgrößen benutze.

Danke !