Vor kurzem habe ich an einem Interview teilgenommen und eine gute Frage bezüglich Hash-Kollisionen gestellt.
Frage: Wenn Sie eine Liste von Strings angeben, drucken Sie die Anagramme zusammen aus.
Beispiel:
i / p: {Akt, Gott, Tier, Hund, Katze}
o / p: handeln, Katze, Hund, Gott
Ich möchte hashmap erstellen und das Wort als Schlüssel und Wert als Liste von Anagrammen setzen
Um eine Kollision zu vermeiden, möchte ich einen eindeutigen Hash-Code für Anagramme generieren, anstatt das sortierte Wort als Schlüssel zu sortieren und zu verwenden.
Ich bin auf der Suche nach einem Hash-Algorithmus, der sich um eine Kollision kümmert, anstatt eine Verkettung zu verwenden. Ich möchte, dass der Algorithmus den gleichen Hash-Code sowohl für act als auch für cat erzeugt ..., so dass er das nächste Wort zur Werteliste hinzufügt
Kann jemand einen guten Algorithmus vorschlagen?
Hashing mit der sortierten Zeichenkette ist ziemlich nett, ich hätte das wahrscheinlich getan, aber es könnte in der Tat langsam und umständlich sein. Hier ist ein weiterer Gedanke, nicht sicher, ob es funktioniert: Wählen Sie eine Primzahl, so klein wie Sie möchten, die gleiche Größe wie Ihr Zeichensatz, und erstellen Sie eine schnelle Mapping-Funktion von Ihren Zeichen zu diesem. Dann ordnen Sie für ein gegebenes Wort jedes Zeichen in die passende Primzahl und multiplizieren. schließlich Hash mit dem Ergebnis.
Dies ist sehr ähnlich dem, was Heuster vorgeschlagen hat, nur mit weniger Kollisionen (eigentlich glaube ich, dass es keine falschen Kollisionen geben wird, wenn man die Einmaligkeit der Primzahlzerlegung einer Zahl berücksichtigt).
einfach z.B. -
%Vor%[Bearbeiten]
Ein paar Worte über die Eindeutigkeit - jede ganze Zahl hat eine einzige Aufschlüsselung nach Multiplikationen von Primzahlen. Wenn Sie also einen Integer-Schlüssel im Hash angeben, können Sie tatsächlich alle möglichen Strings rekonstruieren, die zu ihm hasen und nur diese Wörter. Zerbrich einfach in Primzahlen, p1 ^ n1 * p2 ^ n2 * ... und wandle jedes Prim in das passende Char um. Das Zeichen für p1 würde n1 mal erscheinen, und so weiter. Du kannst keine neue Primzahl erhalten, die du nicht explizit benutzt hast, denn Prime bedeutet, dass du es durch Multiplikation mit anderen Primzahlen nicht erreichen kannst.
Das bringt eine weitere mögliche Verbesserung - wenn Sie die Zeichenfolge konstruieren können, müssen Sie nur die Permutationen markieren, die Sie beim Auffüllen des Hashs gesehen haben. Da die Permutationen nach lexikographischer Reihenfolge geordnet werden können, können Sie jede durch eine Zahl ersetzen. Dies würde den Platz zum Speichern der tatsächlichen Zeichenfolgen in dem Hash speichern, würde jedoch mehr Berechnungen erfordern, so dass es nicht notwendigerweise eine gute Entwurfsauswahl ist. Dennoch macht es die ursprüngliche Frage für Interviews noch etwas komplizierter:)
Hash-Funktion: Weisen Sie jedem Zeichen primäre Nummern zu. Bei der Berechnung des Hash-Codes wird die Primzahl, die diesem Zeichen zugewiesen ist, mit dem vorhandenen Wert multipliziert. Nun erzeugen alle Anagramme denselben Hash-Wert.
ex: a - 2, c - 3 t - 7
Hash-Wert von cat = 3 * 2 * 7 = 42 Hash-Wert von act = 2 * 3 * 7 = 42 Drucken Sie alle Strings, die denselben Hash-Wert haben (Anagramme haben denselben Hash-Wert)
Kleine praktische Optimierung, würde ich für die obige Hash-Methode vorschlagen:
Weisen Sie den Vokalen und dann den am häufigsten vorkommenden Konsonanten die kleinste Primzahl zu. Ex : e: 2 a: 3 i: 5 o: 7 u: 11 t: 13 und so weiter ...
Auch die durchschnittliche Wortlänge für Englisch ist: ~ 6
Außerdem sind die obersten 26 Primzahlen weniger als 100 [2,3,5,7, .., 97]
Folglich würde Ihr Hash im Durchschnitt einen Wert um 100 ^ 6 = 10 ^ 12 erzeugen.
Es gibt also sehr viel weniger Kollisionschancen, wenn Sie die Primzahl für Modulo größer als 10 ^ 12 nehmen.
Die anderen Poster haben vorgeschlagen, Zeichen in Primzahlen umzuwandeln und sie zu multiplizieren. Wenn Sie dieses Modulo eine große Primzahl machen, erhalten Sie eine gute Hash-Funktion, die nicht überläuft. Ich testete den folgenden Ruby-Code gegen die Unix-Wortliste der meisten englischen Wörter und fand keine Hash-Kollisionen zwischen Wörtern, die keine Anagramme voneinander sind. (Unter MAC OS X befindet sich diese Datei hier: / usr / share / dict / words.)
Meine word_hash-Funktion nimmt den Ordinalwert jedes Zeichenmods 32 an. Dadurch wird sichergestellt, dass Groß- und Kleinbuchstaben den gleichen Code haben. Die große Primzahl, die ich benutze, ist 2 ^ 58 - 27. Jede große Primzahl wird so lange dauern, wie sie weniger als 2 ^ 64 / A ist, wobei A meine Alphabetgröße ist. Ich verwende 32 als meine alphabetische Größe, das bedeutet, dass ich keine größere Zahl als etwa 2 ^ 59 - 1 verwenden kann. Da ruby ein Bit für das Vorzeichen und ein zweites Bit verwendet, um anzuzeigen, ob der Wert eine Zahl oder ein Objekt ist Ich verliere ein bisschen über andere Sprachen.
%Vor%Die obige Komplexität scheint sehr fehl am Platz! Sie brauchen keine Primzahlen oder Hashes. Es ist nur drei einfache Ops:
Zwei Iterationen und zwei Sortierungen genügen!
In Scala ist es genau eine Codezeile :
%Vor%Oder, wie die ursprüngliche Frage impliziert, wollen Sie nur Fälle, in denen die Anzahl & gt; 1, es ist nur ein bisschen mehr:
%Vor%