Tabella hash: perché la dimensione dovrebbe essere in primo piano?

Question

Eventuali duplicati:
Why should hash functions use a prime number modulus?

Perché è necessario per (la struttura di dati) di una tabella hash dimensioni per essere un numero primo?

Da quello che ho capito, assicura una distribuzione più uniforme ma c'è qualche altra ragione?

Answer 1

L'unico motivo è evitare il raggruppamento di valori in un piccolo numero di bucket (sì, distribuzione). Un hashtable distribuito più uniforme funzionerà in modo più coerente.

da http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

Se supponiamo che i risultati di funzione hashCode nei seguenti codici hash tra gli altri {x, 2x, 3x, 4x, 5x, 6x ...}, allora tutti questi stanno per essere raggruppati in solo m numero di bucket, dove m = table_length/GreatestCommonFactor (table_length, x). (È banale verificarlo/derivarlo). Ora è possibile eseguire una delle seguenti operazioni per evitare il clustering

1. Assicurarsi di non generare troppi codici hash che sono multipli di un altro hashCode come in {x, 2x, 3x, 4x, 5x, 6x. ..}. Ma questo può essere un po 'difficile se si suppone che il tuo hashTable abbia milioni di voci.

2. O semplicemente rendere m uguale al table_length rendendo GreatestCommonFactor (table_length, x) uguale a 1, cioè rendendo table_length coprime con x. E se x può essere praticamente un numero qualsiasi, assicurati che table_length sia un numero primo.

Answer 2

Qualunque sia hashfunction si utilizza si ottiene un numero intero. Per mappare l'hashtable in genere devi inserire il numero intero mod con la dimensione della tabella hash per renderlo più piccolo della dimensione della tabella per poterlo mappare.

ritorno hashVal% tableSize

io sono un po 'perso da questo punto in poi, ma IIRC se tableSize è ancora, tutte le voci sarà ancora. Metà del tuo hashtable non verrà mai popolata.