¿Por qué es mejor usar un número primo como mod en una función hash?

Si tengo una lista de valores clave del 1 al 100 y quiero organizarlos en una matriz de 11 cubos, me han enseñado a formar una función mod

Ahora todos los valores se colocarán uno tras otro en 9 filas. Por ejemplo, en el primer depósito habrá $0, 11, 22 \dots$ . En el segundo, habrá $1, 12, 23 \dots$ etc.

Digamos que decidí ser un chico malo y usar un no primo como mi función de hashing: toma 12. Uso de la función Hashing

daría como resultado una tabla hash con valores $0, 12, 24 \dots$ en el primer depósito, $1, 13, 25 \dots$ etc. en el segundo y así sucesivamente.

Esencialmente son lo mismo. No reduje las colisiones y no extendí las cosas mejor usando el código hash del número primo y no puedo ver cómo es beneficioso.

Considere el conjunto de claves y una tabla hash donde el número de cubos es . Dado que es un factor de , las claves que son múltiplos de se dividirán en cubos que son múltiplos de :$K=\{0,1,...,100\}$$m=12$$3$$12$$3$$3$

• Las teclas se cifrarán en el depósito .$\{0,12,24,36,...\}$$0$
• Las teclas se encapsularán al cubo .$\{3,15,27,39,...\}$$3$
• Las teclas se encapsularán al cubo .$\{6,18,30,42,...\}$$6$
• Las teclas se encapsularán al cubo .$\{9,21,33,45,...\}$$9$

Si está distribuido uniformemente (es decir, cada clave en es igualmente probable que ocurra), entonces la elección de no es tan crítica. Pero, ¿qué sucede si no está distribuido uniformemente? Imagine que las claves que tienen más probabilidades de ocurrir son los múltiplos de . En este caso, todos los cubos que no son múltiplos de estarán vacíos con alta probabilidad (lo cual es realmente malo en términos de rendimiento de la tabla hash).$K$$K$$m$$K$$3$$3$

Esta situación es más común de lo que parece. Imagine, por ejemplo, que realiza un seguimiento de los objetos en función de dónde están almacenados en la memoria. Si el tamaño de palabra de su computadora es de cuatro bytes, entonces tendrá claves hash que son múltiplos de . No hace falta decir que elegir como múltiplo de sería una elección terrible: tendría cubos completamente vacíos y todas sus llaves colisionarían en los cubos restantes .$4$$m$$4$$3m/4$$m/4$

En general:

Cada clave en que comparte un factor común con el número de cubos se convertirá en un cubo que es un múltiplo de este factor.$K$$m$

Por lo tanto, para reducir al mínimo las colisiones, es importante para reducir el número de factores comunes entre y los elementos de . ¿Cómo se puede lograr esto? Al elegir como un número que tiene muy pocos factores: un número primo .$m$$K$$m$

Si una colisión es menos probable usando primos depende de la distribución de sus claves.

Si muchas de sus teclas tienen la forma y su función hash es , entonces estas teclas van a un pequeño subconjunto de los cubos si f divide . Por lo tanto, debe minimizar el número de tales , que puede lograrse eligiendo un primo.$a+k\cdot b$$H(n)=n \bmod m$$b$$n$$b$

Si, por otro lado, desea tener de a cubos y sabe que las diferencias que son múltiplos de son más probables que las diferencias que son múltiplos de y , puede elegir para su aplicación muy especial.$11$$12$$11$$2$$3$$12$

Si esto tiene un impacto (también) depende de cómo trate las colisiones. Cuando se usan algunas variantes de hashing abierto , el uso de primos garantiza que se encuentren ranuras vacías siempre que la tabla esté suficientemente vacía.

Intente mostrar lo siguiente, por ejemplo:

Supongamos que queremos insertar un elemento que los hashes para hacer frente a y las colisiones a resolver por las posiciones que tratan , posteriormente, para .$a$$a + i^2$$i=1,2,\dots$

Muestre que este procedimiento siempre produce una posición vacía si la tabla hash es del tamaño , un primo mayor que , y al menos la mitad de todas las posiciones están libres.$p$$p$$3$

Sugerencia: Utilice el hecho de que el módulo de anillo de clase de residuo es un campo si es primo y, por lo tanto, tiene como máximo soluciones.$p$$p$$i^2=c$$2$

Si su función hash es de la forma donde es primo y se elige al azar, entonces la probabilidad de que 2 claves distintas de hash para el mismo segmento sea . Entonces, para , que es muy pequeño.$h(k)=a\times k \mod m$$m$$a$$1\over m$$m=1009$$Pr\{h(x)=h(y), x\neq y\}=0.00099108027$

Este esquema se conoce como: Hashing Universal.