Nicht kollidierende Hash-Algorithmus für Strings bis zu 255 Zeichen

Question

Ich bin für einen Hash-Algorithmus zu erstellen, wie nah an einen eindeutigen Hash einer Zeichenfolge (max len = 255) wie möglich, die eine lange Ganzzahl erzeugt (DWORD).

Ich weiß, dass 26 ^ 255 >> 2 ^ 32, sondern auch wissen, dass die Anzahl der Worte in der englischen Sprache ist weit weniger als 2 ^ 32.

Die Saiten, die ich zu ‚Hash‘ brauchen würde meist einzelne Wörter oder einige einfache Konstrukt unter Verwendung von zwei oder drei Wörtern.

---

Die Antwort :

Einer der FNV Varianten Ihren Anforderungen entsprechen sollte. Sie sind schnell und produzieren ziemlich gleichmäßig verteilt Ausgänge. (Beantwortet von Arachnidus )

---

Answer 1

Siehe hier für eine vorherige Iteration dieser Frage (und Antwort).

Answer 2

Eine Technik ist es, einen bekannter Hash-Algorithmus zu verwenden (beispielsweise MD5 oder SHA-1) und nur die ersten 32 Bits des Ergebnisses verwenden.

Bitte beachten Sie, dass das Risiko von Hash-Kollisionen erhöht schneller als man erwarten könnte. Für Informationen zu diesem Thema lesen Sie über die Geburtstag Paradox .

Answer 3

Ronny Pfannschmidt habe einen Test mit gemeinsamen gestern Englisch Wörter und gestoßen keine Kollisionen für die 10000 Worte, die er in der Python-String-Hash-Funktion getestet. Ich habe es selbst nicht getestet, aber das Algorithmus ist sehr einfach und schnell, und scheint für gemeinsame Worte optimiert werden.

Hier ist die Umsetzung:

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}

Answer 4

H (Schlüssel) = [GetHash (key) + 1 + (((GetHash (key) >> 5) + 1)% (hashsize - 1))]% hashsize

MSDN-Artikel auf Hashcodes

Answer 5

Java String.hash () leicht hier eingesehen werden , sein Algorithmus ist

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]