Algoritmo di hash per l'implementazione della tabella hash

Sto cercando una funzione di hashing ad alta velocità con una buona distribuzione (cioè quasi uniforme) da utilizzare in un'implementazione della tabella hash.Algoritmo di hash per l'implementazione della tabella hash

La tabella hash verrà utilizzata esclusivamente per la memorizzazione di valori con un numero intero.

Posso usare solo i bit più bassi del numero intero come hash?

ad es. Int chiave = n & 15; e creare un array con 16 slot per memorizzarli.

Qualche consiglio?

fonte

2012-05-29 Anonymous

+12

Non esiste una funzione di cancellatura perfetta. Tuttavia, se vuoi alcuni algoritmi con il corrispondente codice sorgente, vedi qui: http://partow.net/programming/hashfunctions/index.html –

Prendere i bit più bassi è probabilmente la cosa peggiore da fare. (ma: tutto dipende dall'intervallo di valori che ci si aspetta dalla chiave int) Prova a mischiare anche i bit superiori, o moltiplica con un numero abbastanza grande (dispari, primo). Sapere cosa aspettarsi e misurarlo. – wildplasser

Posta il tuo commento come risposta e lo accetterò. –

Si può vedere qui xxhash

La vostra funzione di hash citato è molto veloce, ma è molto male anche. Se si desidera una funzione di hash "stupida", si può considerare il modulo.

Esempio:

int key = item % size_of_hash_table

fonte

2012-10-30 16:35:18

Perché "it" è cattivo? –

Beh, ieri sera ho fatto un test di hash versatile (in C), che copre diversi hashers top-gun e 38 chiavi diverse.

Voi tutti sono invitati a punto di riferimento all'indirizzo: http://www.overclock.net/t/1319572/benchmarking-the-fastest-hash-function/0_20#post_18495990

Sarei contento per rivelando come Intel vs AMD e Intel 12.1 compilatore vs Microsoft 16 (VS2010) combinazioni di compilatore si comportano con il tuo aiuto.

fonte

2012-10-31 15:47:05 Georgi

Algoritmo di hash per l'implementazione della tabella hash

risposta

Problemi correlati