data structures - hashing - Hash table: ¿por qué el tamaño debe ser primo?

hash tables

Question

Posible duplicado:
¿Por qué las funciones hash usan un módulo de número primo?

¿Por qué es necesario que el tamaño de una tabla hash (la estructura de datos) sea primo?

Por lo que entiendo, asegura una distribución más equitativa, pero ¿hay alguna otra razón?

Answer 1

La única razón es evitar la agrupación de valores en un pequeño número de grupos (sí, distribución). Una tabla hash más distribuida se realizará de manera más consistente.

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

Si supongamos que su función hashCode da como resultado los siguientes códigos hash entre {x, 2x, 3x, 4x, 5x, 6x ...}, entonces todos estos se agruparán en un número m de grupos, donde m = table_length / GreatestCommonFactor (table_length, x). (Es trivial verificar / derivar esto). Ahora puede hacer una de las siguientes acciones para evitar la agrupación en clústeres.

1. Asegúrate de no generar demasiados hashCodes que sean múltiplos de otro hashCode como en {x, 2x, 3x, 4x, 5x, 6x ...}. Pero esto puede ser un poco difícil si se supone que tu hashTable tiene Millones de entradas.

2. O simplemente haga que m sea igual a table_length haciendo que GreatestCommonFactor (table_length, x) sea igual a 1, es decir, haciendo que table_length coprime con x. Y si x puede ser casi cualquier número, entonces asegúrese de que table_length sea un número primo.

Answer 2

Cualquiera que sea la función que uses, obtienes un número entero. Para asignar eso a la tabla hash, generalmente se mod el número entero con el tamaño de la tabla hash para hacer ese valor más pequeño que el tamaño de la tabla para asignarlo.

return hashVal% tableSize

Estoy un poco perdido desde este punto en adelante, pero IIRC si tableSize es parejo, todas las entradas serán parciales. La mitad de tu tabla hash nunca será poblada.