Gute Hash-Funktion für Strings

159

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.

Leif Andersen
quelle
4
Gute Hash-Funktionen hängen stark von der Eingabe in den Hash und den Anforderungen des Algorithmus ab. Ein solcher Hash ist nicht sehr gut, wenn beispielsweise alle Zeichenfolgen mit denselben fünf Zeichen beginnen. Es wird auch dazu neigen, zu einer Normalverteilung zu führen.
WhirlWind
1
Mögliches Duplikat von 98153
Michael Mrozek
14
Warum kannst du nicht die Stringeigenen benutzen hashCode()?
Bart Kiers
@WhirlWind, stimmt, ich bin mir nicht sicher, was die Zeichenfolgen haben werden, ansonsten wird es wahrscheinlich englischen Text geben.
Leif Andersen
@Barl, hauptsächlich, weil mein Professor uns sagte, wir sollten unseren eigenen Hash-Funktor implementieren ... und der Grund, warum ich Java nicht verwenden wollte, war, dass es generisch war und ich mir vorstellen würde, dass ein spezifischerer Hash-Funktor besser wäre.
Leif Andersen

Antworten:

159

Normalerweise Hashes würde Summen nicht tun, sonst stopund potswird 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:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}
jonathanasdf
quelle
@jonathanasdf Wie kannst du sagen, dass es dir immer einen eindeutigen Hash-Schlüssel gibt? Gibt es einen mathematischen Beweis? Ich denke, wir müssen einen Hash-Mod mit einer anderen größeren Primzahl nehmen, sonst tritt ein Überlaufproblem auf.
Devsda
17
@devsda Er sagte nicht immer einzigartig, er sagte eher, einzigartig zu sein. Eine schnelle Suche bei Google zeigt diesen Artikel: computlife.wordpress.com/2008/11/20/… erklärt, warum 31 für das Hashing von Java-Zeichenfolgen verwendet wurde. Es gibt keinen mathematischen Beweis, aber er erklärt das allgemeine Konzept, warum Primzahlen besser funktionieren.
Pharap
2
Vielen Dank für die Klärung der Idee, besseres Hashing zu machen. Nur zur doppelten Überprüfung - Der Rückgabewert hashCode () wird von Java verwendet, um vor dem Speichern des Objekts einem Tabellenindex zuzuordnen. Wenn also hashCode () m zurückgibt, führt es so etwas wie (m mod k) aus, um einen Index der Tabelle der Größe k zu erhalten. Ist das richtig?
Mit dem
1
"hash = hash * 31 + charAt (i);" erzeugt den gleichen Hash für Spot, Tops, Stop, Opts und Pots.
Jack Straub
1
@maq Ich glaube du bist richtig. Ich weiß nicht, was ich gedacht habe.
Jack Straub
139

Wenn es sich um eine Sicherheitssache handelt, können Sie Java-Krypto verwenden:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

quelle
93
Nett. Ich habe eine Anwendung für maschinelles Lernen, die statistische NLP über einen großen Korpus durchführt. Nach einigen ersten Durchgängen der morphologischen Normalisierung der ursprünglichen Wörter im Text werfe ich die Zeichenfolgenwerte weg und verwende stattdessen Hash-Codes. In meinem gesamten Korpus gibt es ungefähr 600.000 eindeutige Wörter, und mit der Standard-Java-Hashcode-Funktion habe ich ungefähr 3,5% Kollisionen erhalten. Wenn ich jedoch den Zeichenfolgenwert SHA-256 und dann einen Hashcode aus der verdauten Zeichenfolge generiere, beträgt das Kollisionsverhältnis weniger als 0,0001%. Vielen Dank!
Benjaminism
3
Vielen Dank für die Bereitstellung von Informationen zu Kollisionen und Anzahl der Wörter. Sehr hilfreich.
Philipp
19
@benjismith Einer von einer Million ist viel zu groß ... ist "weniger als 0,0001%" eine schräge Art, "genau 0" zu sagen? Ich bezweifle wirklich, dass Sie eine SHA-256-Kollision gesehen haben, weil dies nirgendwo und nie beobachtet wurde. nicht einmal für 160-Bit-SHA-1. Wenn Sie zwei Zeichenfolgen haben, die denselben SHA-256 erzeugen, würde die Sicherheitsgemeinschaft sie gerne sehen. Sie werden weltberühmt sein ... auf sehr dunkle Weise. Siehe Vergleich der SHA-Funktionen
Tim Sylvester
7
@ TimSylvester, du hast es falsch verstanden. Ich habe keine SHA-256-Kollisionen gefunden. Ich habe den SHA-256 berechnet und dann die resultierenden Bytesequenzen in eine typische Java "hashCode" -Funktion eingespeist, weil ich einen 32-Bit-Hash benötigte. Dort habe ich die Kollisionen gefunden. Nichts Bemerkenswertes :)
Benjaminism
1
Gibt es nicht einen Unterschied zwischen "Hashing" und "Verschlüsselung"? Ich verstehe, dass MessageDigest eine Einweg-Hashing-Funktion ist, oder? Als ich die Funktion verwendete, bekam ich die Hash-Zeichenfolge als viele Junk-UTF-Zeichen, als ich die Datei in LibreOffice öffnete. Ist es möglich, die Hash-Zeichenfolge als zufällige Gruppe alphanumerischer Zeichen anstelle von Junk-UTF-Zeichen abzurufen?
Nav
38

Sie sollten wahrscheinlich String.hashCode () verwenden .

Wenn Sie hashCode wirklich selbst implementieren möchten:

Versuchen Sie nicht, wesentliche Teile eines Objekts von der Hash-Code-Berechnung auszuschließen, um die Leistung zu verbessern - Joshua Bloch, Effective Java

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 :

Die in allen Releases vor 1.2 implementierte String-Hash-Funktion untersuchte höchstens 16 Zeichen, die gleichmäßig über den String verteilt waren, beginnend mit dem ersten Zeichen. Bei großen Sammlungen hierarchischer Namen, wie z. B. URLs, zeigte diese Hash-Funktion ein schreckliches Verhalten.

Frederik
quelle
1
Wenn man eine Double-Hash-Sammlung verwendet, kann es sich lohnen, wenn der erste Hash wirklich schnell und schmutzig ist. Wenn man tausend lange Zeichenfolgen hat, von denen die Hälfte a von einer miesen Funktion einem bestimmten Wert zugeordnet wird und die andere Hälfte bestimmten Werten zugeordnet ist, wäre die Leistung in einer Tabelle mit einem einzelnen Hash schlecht, die Leistung in einer Doppel-Hash-Tabelle jedoch schlecht. Die Hash-Tabelle, bei der der zweite Hash die gesamte Zeichenfolge untersuchte, könnte fast doppelt so hoch sein wie eine einfach gehashte Tabelle (da die Hälfte der Zeichenfolgen nicht vollständig gehasht werden müsste). Keine der Standard-Java-Sammlungen führt jedoch doppeltes Hashing durch.
Supercat
Die effektive Java-Verbindung ist unterbrochen @Frederik
KGs
17

Wenn Sie dies in Java tun, warum tun Sie es dann? Rufen Sie einfach .hashCode()die Zeichenfolge an

Pyrolistisch
quelle
2
Ich mache es als Teil der Klasse und ein Teil der Aufgabe besteht darin, mehrere verschiedene Hash-Funktionen zu schreiben. Der Professor sagte uns, wir sollten Hilfe von außen für die "besseren" bekommen.
Leif Andersen
20
Wenn Sie möchten, dass Ihre Version über JVM-Versionen und -Implementierungen hinweg konsistent ist, sollten Sie sich nicht darauf verlassen .hashCode(). Verwenden Sie stattdessen einen bekannten Algorithmus.
Stephen Ostermiller
7
Der Algorithmus für String::hashCodewird im JDK angegeben, ist also genauso portabel wie die Existenz der Klasse java.lang.String.
Yshavit
12

GuavasHashFunction ( Javadoc ) bietet anständiges, nicht kryptostarkes Hashing.

Mike Samuel
quelle
1
Es ist noch in der Beta ab diesem Kommentar
ThomasRS
1
Und jetzt würde 404ich.
Shawn
8

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.

private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

public static String byteArray2Hex(byte[] bytes) {
    StringBuffer sb = new StringBuffer(bytes.length * 2);
    for(final byte b : bytes) {
        sb.append(hex[(b & 0xF0) >> 4]);
        sb.append(hex[b & 0x0F]);
    }
    return sb.toString();
}

public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
    messageDigest.update(stringToEncrypt.getBytes());
    return byteArray2Hex(messageDigest.digest());
}

Vielleicht kann das jemandem helfen

Festus Tamakloe
quelle
Sie können das Byte-Array einfach an messageDigest.update () übergeben.
Szgal
byteArray2Hex () - genau das habe ich gesucht! Vielen Dank :)
Krzysiek
5
// djb2 hash function
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Quelle Logik hinter djb2 Hash - Funktion - SO

Pratik Deoghare
quelle
1
Ich denke, es ist nur eine Primzahl, um anzufangen, damit wir weniger Kollisionen haben.
CornSmith
5

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- charWerte 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.

Thomas Pornin
quelle
Diese Hash-Funktion ist so viel besser als die, die mit Java geliefert wird.
Clankill3r
3

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."

Dean J.
quelle
1

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.

Yefei
quelle
1

sdbm: Dieser Algorithmus wurde für die Datenbankbibliothek sdbm (eine gemeinfreie Neuimplementierung von ndbm) erstellt

static unsigned long sdbm(unsigned char *str)
{   
    unsigned long hash = 0;
    int c;
    while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}
Anchal
quelle
0
         public String hashString(String s) throws NoSuchAlgorithmException {
    byte[] hash = null;
    try {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        hash = md.digest(s.getBytes());

    } catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < hash.length; ++i) {
        String hex = Integer.toHexString(hash[i]);
        if (hex.length() == 1) {
            sb.append(0);
            sb.append(hex.charAt(hex.length() - 1));
        } else {
            sb.append(hex.substring(hex.length() - 2));
        }
    }
    return sb.toString();
}
Charaf JRA
quelle
-1

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".

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += 7*n%31;
    }
    return u%139;
}

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.

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += i*n%31;
    }
    return u%139;
}
kanthonye
quelle
-1

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.

int generatehashkey(const char *name)
{
        int x = tolower(name[0])- 97;
        if (x < 0 || x > 25)
           x = 26;
        return x;
}

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

Geben Sie den folgenden Text als Eingabe ein: Atticus sagte eines Tages zu Jem: „Ich würde lieber auf Blechdosen im Hinterhof schießen, aber ich weiß, dass Sie nach Vögeln suchen werden. Erschieße alle Blauhäher, die du willst, wenn du sie schlagen kannst, aber denk daran, dass es eine Sünde ist, einen Spottdrossel zu töten. “ Dies war das einzige Mal, dass ich Atticus sagen hörte, es sei eine Sünde, etwas zu tun, und ich fragte Miss Maudie danach. "Dein Vater hat Recht", sagte sie. „Spottdrosseln machen nichts anderes, als Musik zu machen, die wir genießen können. Sie fressen nicht die Gärten der Menschen auf, nisten nicht in Maiskrippen, sie tun nichts, sondern singen ihr Herz für uns aus. Deshalb ist es eine Sünde, einen Spottdrossel zu töten.

Dies wäre die Ausgabe:

0 --> a a about asked and a Atticus a a all after at Atticus
1 --> but but blue birds. but backyard
2 --> cribs corn can cans
3 --> do dont dont dont do dont do day
4 --> eat enjoy. except ever
5 --> for for fathers
6 --> gardens go
7 --> hearts heard hit
8 --> its in it. I it I its if I in
9 --> jays Jem
10 --> kill kill know
11 --> 
12 --> mockingbird. music make Maudie Miss mockingbird.”
13 --> nest
14 --> out one one only one
15 --> peoples
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to Thats their thing they They to thing to time the That to the the tin to
20 --> us. up us
21 --> 
22 --> why was was want
23 --> 
24 --> you you youll you
25 --> 
26 --> Mockingbirds  Your em Id
user2311285
quelle
2
Eine gute Hash-Funktion verteilt die Werte gleichmäßig auf die Buckets.
Jonathan Peterson
-1

Dies vermeidet jede Kollision und ist schnell, bis wir die Verschiebung in den Berechnungen verwenden.

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }
Kamal El-Deen Shair
quelle