Algoritmo hash non in collisione per stringhe fino a 255 caratteri

Question

Sto cercando un algoritmo hash, per creare il più vicino possibile a un hash univoco di una stringa (max len = 255), che produce un intero lungo (DWORD).

Mi rendo conto che 26 ^ 255 > > 2 ^ 32, ma sappi anche che il numero di parole in lingua inglese è molto inferiore a 2 ^ 32.

Le stringhe di cui ho bisogno per 'hash' sarebbero principalmente parole singole o un semplice costrutto che usa due o tre parole.

---

La risposta :

Una delle varianti FNV dovrebbe soddisfare i tuoi requisiti. Sono veloci e producono output distribuiti in modo abbastanza uniforme. (Risposta di Arachnid )

---

Answer 1

Vedi qui per una precedente iterazione di questa domanda (e la risposta).

Answer 2

Una tecnica consiste nell'utilizzare un noto algoritmo hash (ad esempio, MD5 o SHA-1) e utilizzare solo i primi 32 bit del risultato.

Tieni presente che il rischio di collisioni con hash aumenta più rapidamente di quanto ti aspetti. Per informazioni al riguardo, leggi Birthday Paradox .

Answer 3

Ronny Pfannschmidt ha fatto un test con parole inglesi comuni ieri e non ha riscontrato alcuna collisione per le 10000 parole che ha testato nella funzione hash della stringa Python. Non l'ho testato da solo, ma quell'algoritmo è molto semplice e veloce e sembra essere ottimizzato per le parole comuni.

Qui l'implementazione:

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 (chiave) = [GetHash (chiave) + 1 + (((GetHash (chiave) > > 5) + 1)% (hashsize & # 8211; 1))]% hashsize

Articolo MSDN su HashCodes

Answer 5

String.hash () di Java può essere facilmente visualizzato qui , il suo algoritmo è

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