In che modo Pearson si confronta con altri algoritmi di hashing non crittografici?

0

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.

    
posta David Spector 11.06.2016 - 15:50
fonte

1 risposta

1

Non ho un confronto pratico tra l'hashing di Pearson e gli altri suggerimenti comuni, ma posso evidenziare alcune ipotesi che stai facendo che non sono necessariamente vere e che potrebbero spiegare perché non è così popolare come sembri aspettarsi:

  • Si afferma che avere una buona distribuzione di piccole chiavi nell'intero intervallo è tanto importante quanto una buona distribuzione di chiavi più grandi, ma questo non è necessariamente vero. Nelle applicazioni pratiche, i tasti piccoli sono rari e non possono verificarsi con una frequenza non banale in grandi serie di dati semplicemente perché c'è solo un piccolo numero di possibili piccole chiavi. Ci interessano solo le prestazioni opzionali per i set di dati di grandi dimensioni, in quanto piccoli set di dati possono essere elaborati abbastanza rapidamente in ogni caso.

  • Asserisci che le prestazioni saranno buone a causa della semplicità dell'algoritmo, ma a me non sembra così semplice. Per un hash a 32 bit (che è il più piccolo che sia davvero utile) richiede 8 operazioni per byte. Confronta questo con le 6 operazioni di Murmur per parola da 4 byte, e chiaramente non sarà competitivo. Anche un singolo byte in uscita a 2 operazioni per byte è improbabile che sia veloce quanto Murmur.

risposta data 12.06.2016 - 08:59
fonte

Leggi altre domande sui tag