Perché un tasso di collisione così elevato con la mia implementazione hash ELF

Question

Attualmente sto lavorando sulla scelta di un paio di funzioni di hashing per uso generico da utilizzare nelle sostituzioni Object.GetHashCode(). Inizialmente, su raccomandazione di this site ho iniziato con ELF. La mia implementazione C# è qui sotto:

public int Generate(byte[] key) { 
    const uint c = 0xf0000000; 

    uint h = 0, 
     g = 0; 

    unchecked { 
     for (int i = 0, len = key.Length; i < len; i++) { 
      h = (h << 4) + key[i]; 

      if ((g = h & c) != 0) 
       h ^= g >> 24; 

      h &= ~g; 
     } 
    } 

    return (int)h; 
} 

Il mio banco di prova è costituito da 524.288 valori unici divisi in (256-2048) stringhe brevi (1-64) e lunghe (set di caratteri ASCII limitata) e dati binari arbitrari (131,072 ciascuna) per testare ogni algoritmo in una varietà di circostanze.

Comprendo anche i limiti di questo scenario di test. Un algoritmo di hashing può funzionare eccezionalmente bene con l'hashing, ad esempio gli URL, ma essere pessimi con hashing JPG o qualcosa del genere. Stringhe casuali/binari mi sembrano il miglior punto di partenza per scegliere una funzione generica. Sono felice di sentire i motivi per cui questo non è il caso.

Ho eseguito 3 esecuzioni di test separate (generando un nuovo set di stringhe/byte casuali ogni volta) e una media dei risultati.

L'algoritmo ELF prodotto un certo numero di collisioni orribile in confronto agli altri algoritmi sono test:

• stringhe brevi: 817 collisioni (~ 0.5% non riesce rate).
• Short binary: 550 collisioni (~ 0,4% tasso fallito)
• Lunghe stringhe/binario: 34 collisioni (~ 0,025% percentuale di errore).

Per posizionare questo contesto, gli altri 3 algoritmi che ho testato hanno prodotto in media tra 3-10 collisioni in media per gli stessi test. E 'anche tra i più lenti dei 4, quindi a questo punto sembra essere del tutto inutile.

risultati completi:

 
      Strings  Binary 
Algorithm short:long short:long 
ELF  817:40  550:28 
FNV  1.6:2  0.6:2.6 
OAT  9:9.6  14:5 
Jenkins* 2:1.3  12:3.6 

* A close approximation of the lookup3 hash function. 

Così, per gli stessi campioni casuali che ELF sta lottando su (ho generato 3 set separati), tutti gli altri algoritmi testati stanno producendo modo modo meno collisioni.

Ho cercato varianti dell'algoritmo ELF, ma i pochi esempi che ho trovato sembrano coerenti con ciò che ho implementato. L'unica variazione che ho visto era su questa domanda SO: Using ELF to produce a tweaked hashmap. Questa variazione include h &= g >> 24 all'interno del blocco if e taglia il risultato a 31 bit. Ho provato quella variazione e ha prodotto gli stessi risultati terribili.

Ho fatto qualcosa di sottilmente ma orribilmente sbagliato? Non riesco a capire perché si stia comportando così male visto che è presumibilmente ampiamente usato in Unix.

Answer 1

Il actual ELF implementation restituisce unsigned long e l'origine utilizza unsigned long internamente. Non posso dirlo con certezza, ma la mia intuizione è che la tua implementazione sta semplicemente buttando via troppe cose interessanti trattando in int.

Answer 2

È non un hash crittografico, è un hash tabella hash.

Questa è una prestazione perfettamente ragionevole per una funzione di hash destinata all'uso in una tabella hash.In genere si archiviano tra centinaia e centinaia di migliaia di oggetti e si desidera memorizzare e recuperare rapidamente gli oggetti.

Si fa dividendo in bucket, ciascuno contenente un elenco collegato (o forse un array). Quindi calcoli l'hash e, prendendo il resto quando si divide per il numero di bucket, si individua il bucket. Quindi si cammina l'elenco collegato confrontando ciascun oggetto per trovare quello desiderato.

Se il bucket è vuoto, l'oggetto non viene trovato. È quindi possibile crearne uno o adottare l'altra azione appropriata in base all'applicazione.

L'hash deve essere dimensionato in modo da avere circa lo stesso numero di bucket del numero previsto di elementi da memorizzare (o pochi), quindi la maggior parte delle ricerche troverà un bucket con zero, una o due voci.

Per le prestazioni, si desidera bilanciare le spese di calcolo dell'hash contro le spese di attraversamento di una lista concatenata molto breve in caso di collisione. È con questo in mente che sono state progettate le implementazioni di ELF e funzioni di hash simili.

In breve:

• In una tabella hash, lo scontro occasionale è un prezzo da pagare per un hash più veloce.
• In un hash crittografico, un hash lento è un prezzo che vale la pena pagare per evitare le collisioni.

Se le collisioni rappresentano un problema nell'applicazione, utilizzare SHA1 o SHA256 o qualcosa progettato con questo in mente.

Nota: Per l'utilizzo come un'implementazione di object.GetHashCode() il codice hash è destinato esclusivamente per accelerare il confronto ("fail fast") e per l'utilizzo in tabelle hash. Non è necessario che sia completamente resistente alla collisione poiché si andrà a confrontare completamente la parità. È necessario prestazione equilibrata. Suggerisco di eseguire l'hashing dei campi più importanti (utilizzando il proprio codice GetHashCode()) e XOR dei valori.

Modifica: Vedi anche questi hash qui:

• http://www.burtleburtle.net/bob/hash/doobs.html

Answer 3

Il numero atteso di collisioni a 524000 campioni casuali su un 32 bit di hash è 34.

You' ottenendo 34 collisioni con stringhe lunghe, quindi per stringhe lunghe, questo algoritmo sta eseguendo più o meno come previsto.

Le collisioni di hash sono molto, molto più probabili su stringhe corte poiché c'è così molta meno entropia nei dati, quindi non mi sorprende affatto che stai ottenendo ordini di grandezza peggiori delle prestazioni su stringhe piccole.

E è sorprendente che si ottengano solo dieci collisioni con altri algoritmi di hash. Mi sarei aspettato molto di più.

In tema di prestazioni della velocità non elaborata: si potrebbe fare meglio a smettere di essere così intelligenti.Il jitter può riconoscere e ottimizzare il modello estremamente comune:

for(int i = 0; i < array.Length; ++i) 
    do something with array[i] 

modo da evitare il ricalcolo della lunghezza ed evitare il controllo dell'intervallo sull'accesso matrice. Cercando di essere intelligente ed evitare il ricalcolo di Length, si potrebbe essere ingannare il jitter per non più ottimizzare il controllo del range.

Se si desidera evitare sempre il controllo intervallo, è sempre possibile passare al codice non sicuro; Correggi l'array, ottieni un puntatore e poi incrementa il puntatore, come se scrivessi il programma in C. Assumi la responsabilità di garantire la sicurezza della memoria in quel punto, ma le probabilità sono buone, sarà più veloce.

Ovviamente, l'analisi delle prestazioni "poltrona" vale esattamente quello che hai pagato; per ottenere una vera analisi, provalo e guarda cosa succede.