FNV-1, Murmur2 e DJB2 sono esempi di funzioni di hashing non crittografiche utilizzate nelle applicazioni reali (vedere Quale algoritmo di hashing è il migliore per unicità e velocità? ). Questi sono tutti simili in quanto hanno un loop interno che calcola il risultato usando semplici operazioni come XOR o bit shifting.
Forse questi algoritmi sono veramente i migliori disponibili; Non lo so. Ma Pearson Hashing, in particolare, sembra essere raramente considerato. Eppure è l'algoritmo che sembra essere il migliore, dato nessun dominio informazioni sulle chiavi, perché è stato progettato per distribuire (randomizzare) la gamma bene per qualsiasi dominio.
Questo significa (per le stringhe di caratteri) che se le chiavi sono singole lettere (un piccolo dominio) o stringhe di lunghezza 128 (un dominio molto più grande), il risultato (il valore hash) è garantito per essere distribuito bene ( distribuito casualmente sull'intervallo della funzione). La ragione per cui una tale buona distribuzione casuale è desiderata è che ci si aspetta che tale distribuzione riduca il numero di collisioni per selezioni casuali di chiavi (anche in questo caso, assumendo non ci sono particolari caratteristiche della distribuzione della chiave (dominio).
L'hashing Pearson realizza ciò usando una matrice a 256 voci che contiene una permutazione casuale con un singolo ciclo. Per chiarire cosa intendo, ecco un array di quattro voci che specifica una tale permutazione della lista valori [0, 1, 2, 3]:
0: 2
1: 3
2: 1
3: 0
L'hashing di Pearson analizza la stringa chiave. Per ogni byte (va bene che un personaggio si estenda su più byte), XORs il byte in una somma di esecuzione hash , quindi cerca hash up nella sua matrice di permutazione a 256 byte . Questo risultato della ricerca è la somma successiva. Poiché la matrice contiene 256 voci, gestirà qualsiasi byte. Per scalare fino a un intervallo più ampio, ad esempio un intervallo di 16 o 32 bit, il ciclo interno viene eseguito più volte. Poiché l'algoritmo utilizza uno XOR e una semplice ricerca di array per ogni byte dell'intervallo, è probabilmente l'algoritmo più veloce possibile, in particolare se implementato in linguaggio assembly. E la dimensione della funzione di hashing di Pearson dovrebbe essere piccola, non molto di più dei 256 byte usati dal suo array. Tranne che in applicazioni embedded minuscole, non posso immaginare che 256 byte di memoria siano un'obiezione all'utilizzo dell'hash di Pearson.
Alcuni esempi di implementazioni delle funzioni di Pearson sono forniti al link .
Sarei molto interessato a vedere un'analisi dell'hash di Pearson rispetto ad altri algoritmi più comunemente usati, come i tre elencati sopra, con set di input come un dizionario inglese. Mi aspetto che faccia molto bene.