Duplicar posible:
Why should hash functions use a prime number modulus?Tabla hash: ¿por qué el tamaño debe ser primordial?
¿Por qué es necesario que (la estructura de datos) de una tabla hash tamaño para ser un número primo?
Por lo que entiendo, asegura una distribución más uniforme, pero ¿hay alguna otra razón?
La única razón es evitar la agrupación de valores en un pequeño número de segmentos (sí, distribución). Una tabla hash distribuida más uniforme tendrá un rendimiento más consistente.
de http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html
Si supongamos que sus resultados de la función hashCode en los siguientes hashcodes entre otros {x, 2x, 3x, 4x, 5x, 6x ...}, entonces todo lo que estos van a ser agrupadas en solo en número de cubetas, donde m = table_length/GreatestCommonFactor (table_length, x). (Es trivial verificar/derivar esto). Ahora se puede realizar una de las acciones siguientes para evitar el agrupamiento
Asegúrese de que no generan demasiados hashcodes que son múltiplos de otra 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.
O simplemente haga que m sea igual a la longitud_de_tabla haciendo que GreatestCommonFactor (table_length, x) sea igual a 1, es decir, haciendo table_length coprime con x. Y si x puede ser casi cualquier número, asegúrese de que table_length es un número primo.
De lo que supongo que entendí bien: Evite agrupar <=> Obtenga una mejor distribución. ¿Derecha? Gracias por la referencia. –
@Olivier Lalonde, si esto responde a su pregunta, por favor márquelo como la respuesta. –
Cualquiera que sea hashfunction utiliza se obtiene un entero. Para asignarlo a la tabla hash generalmente se mod el entero con el tamaño de la tabla hash para hacer que ese valor sea más pequeño que el tamaño de la tabla para mapearlo.
retorno hashVal% tableSize
estoy un poco perdido desde este punto en adelante, pero IIRC si tableSize es par, todas las entradas será aún. La mitad de tu hashtable nunca se completará.
Ese es otro buen punto. Y creo que la razón para un primo es que reduce el riesgo de patrones (por ejemplo, 10,20,30,40, que darán 0 si tableSize = 10) en el hashVal, lo que puede dar como resultado una distribución desigual como la mencionada por @Sam . –
347% 20 es 7, que no es par. –
Este es un duplicado de [¿Por qué las funciones hash usan un módulo de número primo?] (Http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus) - el primer enlace en la sección "Relacionada" de la barra lateral - y creo que la [respuesta aceptada] (http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime- number-modulus/1147232 # 1147232) es muy bueno. –
Deberías aceptar una respuesta. – gwg