eine eindeutige Nummer für eine Zeichenfolge in Java-Konstrukt

StackOverflow https://stackoverflow.com/questions/3037440

Frage

Wir haben eine Anforderung des Lesens / mehr als 10 Millionen Strings in eine Datei zu schreiben. wir wollen nicht, auch Duplikate in der Datei. Da die Saiten in einer Datei so schnell gespült werden würde, wie sie sind lesen wir es nicht im Speicher gehalten wird.

Wir können nicht hashcode verwenden aufgrund von Kollisionen in der Hash-Code, aufgrund derer wir einen String als Duplikat verpassen könnte. Zwei weitere Ansätze, die ich in meinem googeln gefunden:

1. Verwenden Sie eine Nachricht Algorithmus wie MD5 Digest -. Aber es könnte zu teuer sein, zu berechnen und zu speichern

2.Use ein Prüfsummen-Algorithmus. [Ich bin nicht sicher, ob dies erzeugt einen eindeutigen Schlüssel für eine String- kann jemand bitte bestätigen]

Gibt es einen anderen Ansatz verfügbar. Danke.

War es hilfreich?

Lösung

Wenn Sie in Ordnung mit mikroskopischer Risiko von Kollisionen, könnten Sie einige Hash-Funktion wie MD5 verwenden, wie Sie vorschlagen, und verlassen sich auf die Hash-Werte.

Eine weitere Alternative, die möglicherweise mit einem größeren Speicherbedarf, der bereits begegnet Strings zu speichern, in einem trie (eine spezielle Art von Baum).

Update: Eine weitere Alternative wäre ein verwenden Bloom-Filter . Dies beruht jedoch nach wie vor auf Hashing aber kann eingestellt werden, um eine beliebig kleine Wahrscheinlichkeit von Kollisionen zu haben.

Andere Tipps

Speichern von 10 Millionen Strings im Speicher ist in der Tat viel, so dass ich den Grund zu schreiben, es zu Datei sofort anstelle des Speicherns in z.B. verstehen ein TreeSet<String> zuerst, aber wobei möchten Sie die 10 Millionen eindeutigen numerischen Tasten speichern, die Sie mit vergleichen wollen? Wenn Sie behalten mögen es unique und numerische (was viel weggeworfener base / radix als Buchstaben), können Sie nicht den Schlüssel kürzer als die Zeichenfolge bereits selbst ist, so dass Sie nicht speichern. Oder vielleicht bei höchster Datenkomprimierung wie GZIP, aber dies würde nur vielen Aufwand hinzufügen. MD5 ist auch nicht angebracht, da zwei verschiedene Strings können den gleichen Hash ergeben.

Ich sehe keine bessere Lösung für diesen wirklich als ein anständiges RDBMS (SQL-Datenbank), in der Sie die Spalte als UNIQUE gesetzt und die Einschränkungsverletzung entsprechend zu behandeln. Ein RDBMS ist sehr für diese Art von Aufgaben optimiert.

Wenn Sie wirklich keine Datenbank betrachten können, dann müssen Sie die Datei für jeden vorhandenen Eintrag vor dem Schreib- / bündig neu zu lesen. Vielleicht nicht sehr schnell, aber sicher Speicher effizient.

Es gibt keine Möglichkeit, eine Funktion zu machen, die einen eindeutigen Schlüssel für eine Zeichenfolge erzeugen würden, die kürzer ist als die Zeichenfolge ist.
Es gibt Datenstrukturen, die Ihre Aufgabe lösen können. B-Baum könnte passen, wenn Sie Daten groß genug ist. Je nach Art Ihrer Eingabe, könnte es effektivere Wege sein.

Reliably Duplikate zu entfernen, ist ziemlich so schwierig, wie die Datei zu sortieren. Als eine andere Antwort gibt, wird es keine Möglichkeit garantiert genau Duplikate ohne halten eine vollständige Kopie der einzelnen Strings im Speicher zu erfassen, die genau zu sein scheint, was Sie zu vermeiden versuchen.

Sie könnten ein im Speicher halten oder On-Disk-Index von Hashcodes, und verwenden Sie diese für den Vergleich tatsächliche Strings aus Dateispeichern abgerufen werden, aber dies würde im Wesentlichen verdoppeln, was eine Datenbank in der Lage sein würde, für Sie tun.

Eine Alternative ist, um die Datei nach der Bearbeitung, sobald es fertig ist. Der UNIX-Art Befehl ist ziemlich gut bei großen Dateien ( Wie ? der UNIX-Befehl sort könnte Art eine sehr große Datei ), so dass ich den Standard-UNIX-Kommandozeilen-Ansatz zur Arbeit vernünftigerweise erwarten: 

    sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt

(Beachten Sie, dass Dateien zuerst sortiert werden müssen, bevor zu uniq vorbei Duplikate zu entfernen).

Wenn Sie diese Tools nicht haben (oder Äquivalente) zur Verfügung, dann können Sie immer versuchen, eine Variante eines externen merge Umsetzung Art selbst.

Wenn die Saiten von einem festen Pool von möglichen Strings (N) sind, dann können Sie minimal perfekter Hashing ein Array 0 ... N-1 zu erstellen. Eine Null in dem durch die perfekten Hash-Funktion Mittel bestimmt Schlitz hat die Zeichenfolge nicht so weit gesehen.

Im übrigen sind die nur effektiv richtige Mittel außerhalb von viel des Speichers und die Lösungen vorgeschlagen, so weit wieder lesen Sie die Datei vor der Entscheidung, die Zeichenfolge, um es zu schreiben.

Sie können dies tun, so effizient wie möglich durch Speicherzuordnung Teile der Datei.

Ich denke wirklich die beste Lösung ist - wie jemand anders bereits vorgeschlagen - eine Datenbank zu verwenden.

Wenn Sie aus irgendeinem Grund keine Datenbank verwenden können, können Sie noch einen Hash-Code verwenden. Sicher gibt es Kollisionen. Nur einige Code hinzufügen, so dass, wenn Sie ein Duplikat hashcode, Ihr Programm überprüft die Datei erfassen, um festzustellen, ob es sich um eine echte doppelte oder eine Kollision ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top