C# Dictionary Memory Management

Question

Ich habe eine Dictionary<string,int>, die das Potenzial hat, mehr als 10 Millionen eindeutige Schlüssel enthalten. Ich versuche, die Menge des Gedächtnisses zu reduzieren, die das dauert, während ich noch die Funktionalität des Wörterbuchs beibehalte.

Ich hatte die Idee, einen Hash der Zeichenfolge als eine lange stattdessen speichern, dies verringert die apps Speicherauslastung auf einen akzeptablen Betrag (~ 1,5 Gig bis ~ 0,5 GB), aber ich fühle mich nicht sehr gut meine Methode dafür.

long longKey= 
BitConverter.ToInt64(cryptoTransformSHA1.ComputeHash(enc.GetBytes(strKey)), 0); 

Grundsätzlich zerhackt dies das Ende einer SHA1 Hash-off, und setzt das erste Stück davon zu einem langen, die ich dann als Schlüssel verwendet werden. Dies funktioniert zumindest für die Daten, mit denen ich gerade teste, aber ich glaube nicht, dass dies eine sehr zuverlässige Lösung ist, da die Wahrscheinlichkeit von Schlüsselkollisionen erhöht ist.

Gibt es andere Möglichkeiten, den Speicherbedarf des Wörterbuchs zu reduzieren, oder ist die Methode, die ich oben habe, nicht so schrecklich, wie ich denke, dass es ist?

[Bearbeiten] Um zu verdeutlichen, muss ich die Fähigkeit zum Nachschlagen eines Wertes im Wörterbuch mit einer Zeichenfolge beibehalten. Das Speichern der tatsächlichen Zeichenfolge im Wörterbuch erfordert viel Speicherplatz. Was ich stattdessen tun möchte, ist eine Dictionary<long,int> verwenden, wobei die lange ist das Ergebnis einer Hash-Funktion auf der Zeichenfolge.

Answer 1

Also habe ich etwas Ähnliches in letzter Zeit und aus einer bestimmten Reihe von Gründen, die ziemlich einzigartig für meine Anwendung sind habe keine Datenbank benutzt. Tatsächlich habe ich versucht, keine Datenbank mehr zu benutzen. Ich habe festgestellt, dass GetHashCode in 3.5 deutlich verbessert ist. Eine wichtige Anmerkung, speichern Sie nie konsequent die Ergebnisse von GetHashCode. NIEMALS. Es ist nicht garantiert, dass sie zwischen den Versionen des Frameworks konsistent sind.

Sie müssen also wirklich eine Analyse Ihrer Daten durchführen, da verschiedene Hash-Funktionen besser oder schlechter auf Ihren Daten funktionieren. Sie müssen auch Geschwindigkeit berücksichtigen. Als allgemeine Regel sollten kryptografische Hash-Funktionen nicht viele Kollisionen aufweisen, selbst wenn sich die Anzahl der Hashes auf Milliarden beläuft. Für Dinge, die ich einzigartig sein muss, verwende ich normalerweise SHA1 Managed. Im Allgemeinen hat die CryptoAPI eine schreckliche Leistung, selbst wenn die zugrundeliegenden Hash-Funktionen gut funktionieren.

Für einen 64-Bit-Hash verwende ich derzeit Lookup3 und FNV1, die beide 32-Bit-Hashes sind, zusammen. Damit eine Kollision stattfinden kann, müssten beide kollidieren, was mathematisch unwahrscheinlich ist und ich habe nicht über 100 Millionen Hashes gesehen. Sie können den Code im Internet öffentlich verfügbar finden.

Führen Sie noch Ihre eigene Analyse durch. Was für mich funktioniert hat, funktioniert möglicherweise nicht für Sie. Tatsächlich verwenden verschiedene Anwendungen mit unterschiedlichen Anforderungen in meinem Büro tatsächlich unterschiedliche Hash-Funktionen oder Kombinationen von Hash-Funktionen.

Ich würde jede unbewiesene Hash-Funktionen vermeiden. Es gibt so viele Hash-Funktionen wie Leute, die denken, dass sie sie schreiben sollten. Führen Sie Ihre Forschung durch und testen Sie den Test.

Answer 2

Warum verwenden Sie nicht einfach GetHashCode(), um einen Hash der Zeichenfolge zu erhalten?

Answer 3

Mit Hashtable-Implementierungen, mit denen ich in der Vergangenheit gearbeitet habe, bringt der Hash Sie in einen Bucket, der oft eine Linkliste von anderen Objekten ist, die den gleichen Hash haben. Hashes sind nicht einzigartig, aber sie sind gut genug, um Ihre Daten in sehr überschaubare Listen aufzuteilen (manchmal nur 2 oder 3), die Sie dann durchsuchen können, um Ihren tatsächlichen Artikel zu finden.

Der Schlüssel zu einem guten Hash ist nicht seine Eindeutigkeit, sondern seine Geschwindigkeit und Verteilungsfähigkeiten ... Sie möchten, dass es so gleichmäßig wie möglich verteilt wird.

Answer 4

Übrigens, kryptographische Hash/Hash-Funktionen sind außergewöhnlich schlecht für Wörterbücher. Sie sind groß und langsam. Durch die Lösung des einen Problems (Größe) haben Sie nur ein anderes, schwerwiegenderes Problem eingeführt: Die Funktion verteilt die Eingabe nicht mehr gleichmäßig und zerstört somit die wichtigste Eigenschaft eines guten Hashes für die Annäherung an die kollisionsfreie Adressierung (z du scheinst dich selbst bemerkt zu haben).

/BEARBEITEN: Wie Andrew bemerkt hat, GetHashCode ist die Lösung für dieses Problem, da das seine beabsichtigte Verwendung ist. Und wie in einem echten Wörterbuch müssen Sie um Kollisionen herum arbeiten. Eines der besten Systeme dafür ist double hashing. Leider ist der einzige 100% zuverlässige Weg, die ursprünglichen Werte tatsächlich zu speichern. Andernfalls hätten Sie eine unendliche Komprimierung erstellt, von der wir wissen, dass sie nicht existieren kann.

Answer 5

Haben Sie bei 10 Millionen Aufzeichnungen die Verwendung einer Datenbank mit einem nicht gruppierten Index in Betracht gezogen? Datenbanken haben viel mehr Tricks für diese Art von Sache im Ärmel.

Hashing, per definitionem und unter jedem Algorithmus, hat das Potenzial von Kollisionen - besonders bei hohen Volumina. Je nach Szenario würde ich sehr vorsichtig sein.

Die Verwendung der Strings könnte Platz beanspruchen, ist aber zuverlässig ...wenn Sie auf x64 sind, muss dies nicht zu groß sein (obwohl es definitiv als "groß"; -p) zählt

Answer 6

Gehen Sie einfach SQLite. Sie werden es wahrscheinlich nicht übertreffen, und selbst wenn Sie es tun, wird es wahrscheinlich nicht die Zeit/Aufwand/Komplexität wert sein.

SQLite.