È possibile implementare una tabella hash ben distribuita senza utilizzare l'operatore%?

Question

È possibile implementare una tabella hash ben distribuita senza utilizzare l'operatore%?

#1 da (9 voti)
#2 da (3 voti)
#3 da (1 voti)

11

Sto cercando di implementare una tabella hash veloce e ben distribuita in C #. Ho difficoltà a scegliere la mia funzione di hash-constraing che accetta un codice hash arbitrario e lo "vincola" in modo che possa essere utilizzato per indicizzare i bucket. Ci sono due opzioni che vedo finora:

Da un lato, puoi assicurarti che i tuoi bucket abbiano sempre un numero primo di elementi, e per limitare l'hash devi semplicemente farlo in base al numero di bucket. Questo è, in effetti, cosa fa il dizionario di .NET . Il problema con questo approccio è che l'utilizzo di% è estremamente lento rispetto ad altre operazioni; se si guarda Le tabelle di istruzioni Agner Fog , idiv (che è il codice assembly generato per%) ha una latenza di istruzioni di ~ 25 cicli per i processori Intel più recenti. Confronta questo con circa 3 per mul , o 1 per operazioni bit a bit come and , or o xor .
D'altra parte, puoi avere il numero di bucket sempre di potenza 2. Dovrai comunque calcolare il modulo dell'hash in modo da non tentare di indicizzare all'esterno dell'array, ma questo tempo sarà meno costoso. Poiché per le potenze del 2% di% N è appena & (N - 1) , la limitazione viene ridotta a un'operazione di mascheramento che richiede solo 1-2 cicli. Questa operazione viene eseguita da sparsehash di Google . Il lato negativo di questo è che contiamo sugli utenti per fornire buoni hash; il mascheramento dell'hash esclude essenzialmente parte dell'hash, quindi non prendiamo in considerazione tutti i bit dell'hash. Se l'hash dell'utente è distribuito in modo non uniforme, ad esempio solo i bit più alti sono compilati oi bit inferiori sono sempre gli stessi, allora questo approccio ha un tasso di collisioni molto più alto.

Sto cercando un algoritmo che posso usare che ha il meglio di entrambi i mondi: prende in considerazione tutti i bit dell'hash ed è anche più veloce dell'utilizzo di%. Non ha necessariamente per essere un modulo, solo qualcosa che è garantito essere nell'intervallo 0..N-1 (dove N è la lunghezza dei bucket) e ha una distribuzione uniforme per tutti gli slot. Esiste un tale algoritmo?

Grazie per l'aiuto.

language-agnostic c# algorithms hashing

posta James Ko 06.09.2016 - 18:20

fonte

3 risposte

Leggi altre domande sui tag language-agnostic c# algorithms hashing

Come funziona la GPL nei confronti di linguaggi come Dart che compilano in altre lingue? Bug che possono essere evitati con gli standard di codifica [chiuso]

score 9 · Answer 1

Le moderne implementazioni della tabella hash non utilizzano la funzione modulo. Spesso usano la potenza di due tabelle di dimensioni e tagliano i bit non necessari. Una funzione di hash ideale consentirebbe questo. L'uso del modulo combinato con le dimensioni delle tabelle dei numeri primi è sorto nei giorni in cui le funzioni di hash erano generalmente scarse, poiché spesso si trovano nello sviluppo .net. Consiglio di leggere su SipHash , una moderna funzione di hash, quindi di leggere alcune altre funzioni moderne, come xxHash .

Dovrei spiegare perché. Le funzioni di hash net sono spesso scarse. In .net, i programmatori sono spesso costretti a implementare le funzioni hash ignorando GetHashcode. Ma .net non fornisce gli strumenti necessari per garantire che le funzioni create dal programmatore siano di alta qualità, ovvero:

incapsulamento dello stato dell'hash in una struttura o classe
hash "aggiungi" funzioni, che aggiungono nuovi dati allo stato di hash (aggiungi un array di byte o un doppio, ad esempio)
una funzione hash "finalizza", per produrre la valanga
incapsulamento del risultato dell'hash - in .net si ottiene una scelta, un intero con segno a 32 bit.

Per ulteriori informazioni sull'utilizzo di un risultato di funzione hash come indice di tabella hash, vedere le definizioni di forme universali di hashing in questo documento: Più veloce Hash universale a 64 bit utilizzando le moltiplicazioni di tipo carry-less

score 3 · Answer 2

Per usare AND mentre stai ancora mantenendo tutti i bit, usa anche XOR.

Per un esempio, temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8); .

Per questo esempio, non esiste un modulo e tutti i 32 bit di hash influiscono sul index a 8 bit. Tuttavia, indipendentemente dal fatto che sia più veloce del DIV è qualcosa che dipende da troppi fattori e può essere facilmente più lento del DIV in alcuni casi (ad esempio hash di grandi dimensioni e indice minuscolo).

score 1 · Answer 3

Puoi trarre vantaggio dal fatto che molti numeri primi hanno un inverso moltiplicativo modulare. Vedi questo articolo . Hai soddisfatto uno dei vincoli rendendo il primo indice del bucket e il modulo 2 ^ n, che sono intrinsecamente relativamente primi.

L'articolo descrive l'algoritmo per trovare un numero tale che moltiplicando per quel numero e ignorando l'overflow, produrrà lo stesso risultato come se fosse stato diviso per la dimensione dell'indice del bucket.