Ich versuche mir eine gute Hash-Funktion für Strings auszudenken. Und ich dachte, es wäre eine gute Idee, die Unicode-Werte für die ersten fünf Zeichen in der Zeichenfolge zusammenzufassen (vorausgesetzt, sie haben fünf, andernfalls hören Sie dort auf, wo sie enden). Wäre das eine gute Idee oder eine schlechte?
Ich mache das in Java, aber ich würde mir nicht vorstellen, dass das einen großen Unterschied machen würde.
String
eigenen benutzenhashCode()
?Antworten:
Normalerweise Hashes würde Summen nicht tun, sonst
stop
undpots
wird den gleichen Hash haben.und Sie würden es nicht auf die ersten n Zeichen beschränken, da sonst Haus und Häuser den gleichen Hash haben würden.
Im Allgemeinen nehmen Hashs Werte an und multiplizieren sie mit einer Primzahl (erhöht die Wahrscheinlichkeit, dass eindeutige Hashes generiert werden). Sie können also Folgendes tun:
quelle
Wenn es sich um eine Sicherheitssache handelt, können Sie Java-Krypto verwenden:
quelle
Sie sollten wahrscheinlich String.hashCode () verwenden .
Wenn Sie hashCode wirklich selbst implementieren möchten:
Es ist eine schlechte Idee, nur die ersten fünf Zeichen zu verwenden . Denken Sie an hierarchische Namen wie URLs: Sie haben alle denselben Hash-Code (weil sie alle mit "http: //" beginnen, was bedeutet, dass sie in einer Hash-Map unter demselben Bucket gespeichert sind und eine schreckliche Leistung aufweisen.
Hier ist eine Kriegsgeschichte, die auf dem String hashCode von " Effective Java " umschrieben ist :
quelle
Wenn Sie dies in Java tun, warum tun Sie es dann? Rufen Sie einfach
.hashCode()
die Zeichenfolge anquelle
.hashCode()
. Verwenden Sie stattdessen einen bekannten Algorithmus.String::hashCode
wird im JDK angegeben, ist also genauso portabel wie die Existenz der Klassejava.lang.String
.Guavas
HashFunction
( Javadoc ) bietet anständiges, nicht kryptostarkes Hashing.quelle
404
ich.Diese von Nick bereitgestellte Funktion ist gut, aber wenn Sie einen neuen String (byte [] bytes) verwenden, um die Umwandlung in String durchzuführen, ist sie fehlgeschlagen. Mit dieser Funktion können Sie das tun.
Vielleicht kann das jemandem helfen
quelle
Quelle Logik hinter djb2 Hash - Funktion - SO
quelle
Es wird gemunkelt, dass FNV-1 eine gute Hash-Funktion für Strings ist.
Bei langen Zeichenfolgen (die beispielsweise länger als etwa 200 Zeichen sind) kann die MD4- Hash-Funktion eine gute Leistung erzielen . Als kryptografische Funktion wurde es vor ungefähr 15 Jahren zerstört, aber für nicht kryptografische Zwecke ist es immer noch sehr gut und überraschend schnell. Im Kontext von Java müssten Sie die 16-Bit-
char
Werte in 32-Bit-Wörter konvertieren , z. B. indem Sie solche Werte in Paare gruppieren. Eine schnelle Implementierung von MD4 in Java finden Sie in sphlib . Wahrscheinlich übertrieben im Rahmen einer Unterrichtsaufgabe, aber ansonsten einen Versuch wert.quelle
Wenn Sie die Implementierungen nach Industriestandard sehen möchten, schauen Sie sich java.security.MessageDigest an .
"Message Digests sind sichere Einweg-Hash-Funktionen, die Daten beliebiger Größe verwenden und einen Hash-Wert fester Länge ausgeben."
quelle
Hier ist ein Link , der viele verschiedene Hash-Funktionen erklärt. Im Moment bevorzuge ich die ELF-Hash-Funktion für Ihr spezielles Problem. Als Eingabe wird eine Zeichenfolge beliebiger Länge verwendet.
quelle
sdbm: Dieser Algorithmus wurde für die Datenbankbibliothek sdbm (eine gemeinfreie Neuimplementierung von ndbm) erstellt
quelle
quelle
Es ist eine gute Idee, mit ungeraden Zahlen zu arbeiten, wenn Sie versuchen, eine gute Hast-Funktion für Zeichenfolgen zu entwickeln. Diese Funktion nimmt eine Zeichenfolge und gibt einen Indexwert zurück. Bisher funktioniert sie ziemlich gut. und hat weniger Kollision. Der Index reicht von 0 bis 300, vielleicht sogar noch mehr, aber ich bin noch nicht höher geworden, selbst mit langen Worten wie "Elektromechanik".
Eine andere Sache, die Sie tun können, ist, jedes Zeichen int parse mit dem Index zu multiplizieren, wenn es wie das Wort "Bär" (0 * b) + (1 * e) + (2 * a) + (3 * r) zunimmt, das Sie erhalten Ein int-Wert zum Spielen. Die erste Hash-Funktion oben kollidiert bei "hier" und "hören", ist aber immer noch großartig darin, einige gute eindeutige Werte zu geben. Der folgende kollidiert nicht mit "hier" und "hören", weil ich jedes Zeichen mit dem Index multipliziere, wenn er zunimmt.
quelle
Hier ist eine einfache Hash-Funktion, die ich für eine von mir erstellte Hash-Tabelle verwende. Es dient im Wesentlichen zum Aufnehmen einer Textdatei und zum Speichern jedes Wortes in einem Index, der die alphabetische Reihenfolge darstellt.
Dies bedeutet im Grunde, dass Wörter gemäß ihrem ersten Buchstaben gehasht werden. Ein Wort, das mit 'a' beginnt, würde einen Hash-Schlüssel von 0 erhalten, 'b' würde 1 usw. erhalten und 'z' wäre 25. Zahlen und Symbole hätten einen Hash-Schlüssel von 26. Dies bietet einen Vorteil ;; Sie können einfach und schnell berechnen, wo ein bestimmtes Wort in der Hash-Tabelle indiziert wird, da alles in alphabetischer Reihenfolge angezeigt wird. Code finden Sie hier: https://github.com/abhijitcpatil/general
Dies wäre die Ausgabe:
quelle
Dies vermeidet jede Kollision und ist schnell, bis wir die Verschiebung in den Berechnungen verwenden.
quelle