wake-up-neo.net

Gute Hash-Funktion für Strings

Ich versuche mir eine gute Hash-Funktion für Strings zu überlegen. Ich dachte, es wäre eine gute Idee, die Unicode-Werte für die ersten fünf Zeichen in der Zeichenfolge zusammenzufassen (vorausgesetzt, es enthält fünf, andernfalls hört es auf, wo es endet). Wäre das eine gute Idee oder eine schlechte Idee?

Ich mache das in Java, aber ich könnte mir nicht vorstellen, dass das einen großen Unterschied machen würde.

132
Leif Andersen

Normalerweise würden Hashes keine Summen machen, andernfalls haben stop und pots den gleichen Hash.

und Sie würden es nicht auf die ersten n Zeichen beschränken, da andernfalls Haus und Häuser denselben Hash haben würden.

Im Allgemeinen nehmen Hashwerte Werte ein und multiplizieren sie mit einer Primzahl (wodurch es wahrscheinlicher ist, eindeutige Hashwerte zu generieren).

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}
135
jonathanasdf

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());
127
Nick

Sie sollten wahrscheinlich String.hashCode () verwenden.

Wenn Sie hashCode wirklich selbst implementieren wollen:

Seien Sie nicht versucht, .__ auszuschließen. wesentliche Teile eines Objekts aus die Hash-Code-Berechnung zur Verbesserung von Leistung - Joshua Bloch, Effektives Java

Wenn Sie nur die ersten fünf Zeichen verwenden, handelt es sich um eine bad Idee. Denken Sie an hierarchische Namen wie URLs: Sie haben alle denselben Hash-Code (da sie alle mit "http: //" beginnen, was bedeutet, dass sie in derselben Hash-Tabelle in einer Hash-Map gespeichert sind und eine schreckliche Leistung zeigen.

Hier ist eine Kriegsgeschichte, die im String hashCode von " Effective Java " paraphrasiert ist:

Die String-Hash-Funktion wurde implementiert in allen Releases vor 1.2 geprüft höchstens sechzehn Zeichen gleichmäßig in der gesamten Zeichenfolge angeordnet, beginnend mit mit dem ersten Zeichen. Für große Sammlungen von hierarchischen Namen, Diese Hash-Funktion .__ wie URLs schreckliches Verhalten gezeigt.

34
Frederik

Wenn Sie dies in Java tun, warum machen Sie es dann? Rufen Sie einfach .hashCode() für die Zeichenfolge auf

17
Pyrolistical

Guavas HashFunction ( javadoc ) liefert anständiges Nicht-Krypto-starkes Hashing.

12
Mike Samuel

Diese von Nick bereitgestellte Funktion ist gut. Wenn Sie jedoch die neue Zeichenfolge (Byte [] Bytes) verwenden, um die Umwandlung in eine Zeichenfolge vorzunehmen, schlug die Funktion fehl. Sie können diese Funktion dazu verwenden.

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

7
Festus Tamakloe
// 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;
}

sourceLogik hinter der djb2-Hashfunktion - SO

5
Pratik Deoghare

FNV-1 soll eine gute Hash-Funktion für Strings sein.

Bei langen Zeichenfolgen (länger als etwa 200 Zeichen) können Sie mit der Funktion MD4 Hash eine gute Leistung erzielen. Als kryptographische Funktion wurde es vor etwa 15 Jahren zerstört, aber für nicht kryptographische Zwecke ist es immer noch sehr gut und überraschend schnell. Im Java-Kontext müssten Sie die 16-Bit-Variablen char in 32-Bit-Wörter konvertieren, z. durch Gruppieren solcher Werte in Paaren. Eine schnelle Implementierung von MD4 in Java finden Sie in sphlib . Wahrscheinlich übertrieben im Rahmen eines Klassenzimmers, aber ansonsten einen Versuch wert.

4
Thomas Pornin

Wenn Sie die Industriestandard-Implementierungen sehen möchten, würde ich unter Java.security.MessageDigest nachsehen.

"Message Digests sind sichere Einweg-Hashfunktionen, die Daten beliebiger Größe annehmen und einen Hashwert mit fester Länge ausgeben."

3
Dean J

sdbm: Dieser Algorithmus wurde für die Datenbankbibliothek sdbm (eine Neuimplementierung der öffentlichen Domänen 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;
}
2
Anchal

hier ist ein Link das viele verschiedene Hash-Funktionen erklärt, denn jetzt bevorzuge ich die ELF-Hash-Funktion für Ihr spezielles Problem. Als Eingabe wird eine beliebige Zeichenfolge benötigt. 

1
Yefei
         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();
}
0
Charaf JRA

Dies vermeidet jegliche Kollision und es wird schnell sein, bis wir die Verschiebung in Berechnungen verwenden.

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