language agnostic - example - ¿Por qué las funciones hash usan un módulo de número primo?

hash table python (13)

Copiando de mi otra respuesta https://stackoverflow.com/a/43126969/917428 . Véalo para más detalles y ejemplos.

Creo que solo tiene que ver con el hecho de que las computadoras funcionan con la base 2. Solo piense cómo funciona lo mismo para la base 10:

8% 10 = 8
18% 10 = 8
87865378% 10 = 8

No importa cuál es el número: mientras termine con 8, su módulo 10 será 8.

Escoger un número suficientemente grande, sin poder de dos, asegurará que la función hash sea realmente una función de todos los bits de entrada, en lugar de un subconjunto de ellos.

Hace mucho tiempo, compré un libro de estructuras de datos de la mesa de negociación por $ 1.25. En él, la explicación de una función de hash decía que, en última instancia, debería modificarse con un número primo debido a "la naturaleza de las matemáticas".

¿Qué esperas de un libro de $ 1.25?

De todos modos, he tenido años para pensar en la naturaleza de las matemáticas, y todavía no puedo entenderlo.

¿Es la distribución de números realmente más incluso cuando hay un número primo de cubetas? ¿O es este un viejo cuento de programador que todos aceptan porque todos los demás lo aceptan?

Primes son números únicos. Son únicos en eso, el producto de un número primo con cualquier otro número tiene la mejor oportunidad de ser único (no tan único como el primer elemento del curso) debido al hecho de que se utiliza un número primo para componerlo. Esta propiedad se utiliza en funciones hash.
Dada una cadena "Samuel", puede generar un hash único multiplicando cada uno de los dígitos o letras constituyentes con un número primo y sumándolos. Es por esto que se utilizan primos.
Sin embargo, el uso de números primos es una técnica antigua. La clave aquí es entender que siempre que pueda generar una clave suficientemente única, también puede pasar a otras técnicas de hashing. Vaya aquí para obtener más información sobre este tema sobre http://www.azillionmonkeys.com/qed/hash.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

tl; dr

index[hash(input)%2] resultaría en una colisión para la mitad de todos los hashes posibles y un rango de valores. index[hash(input)%prime] da como resultado una colisión de <2 de todos los hashes posibles. La fijación del divisor al tamaño de la tabla también garantiza que el número no puede ser mayor que la tabla.

Depende de la elección de la función hash.

Muchas funciones de hash combinan los diversos elementos en los datos al multiplicarlos con algunos factores, la potencia de dos correspondientes al tamaño de palabra de la máquina (ese módulo es libre simplemente dejando que el cálculo se desborde).

No desea ningún factor común entre un multiplicador para un elemento de datos y el tamaño de la tabla hash, porque entonces podría suceder que la variación del elemento de datos no distribuya los datos en toda la tabla. Si elige un primo para el tamaño de la tabla, es muy poco probable que un factor tan común.

Por otro lado, esos factores generalmente se componen de primos impares, por lo que también debería estar seguro usando potencias de dos para su tabla hash (por ejemplo, Eclipse usa 31 cuando genera el método Java hashCode ()).

He leído el popular sitio web de wordpress vinculado en algunas de las respuestas populares anteriores en la parte superior. Por lo que he entendido, me gustaría compartir una observación simple que hice.

Puede encontrar todos los detalles en el artículo http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/ , pero supongamos que lo siguiente es cierto:

El uso de un número primo nos da la "mejor oportunidad" de un valor único

Una implementación general de hashmap quiere que 2 cosas sean únicas.

Código hash único para la clave.
Índice único para almacenar el valor real .

¿Cómo obtenemos el índice único? Al hacer que el tamaño inicial del contenedor interno también sea primo. Básicamente, Prime está involucrado porque posee este rasgo único de producir números únicos que terminamos usando para identificar objetos y encontrar índices dentro del contenedor interno.

Ejemplo:

clave = "clave"

value = "value" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

mapas para identificación única

Ahora queremos una ubicación única para nuestro valor, por lo que

uniqueId % internalContainerSize == uniqueLocationForValue , asumiendo que internalContainerSize también es primo.

Sé que esto está simplificado, pero espero poder hacer llegar la idea general.

Lo primero que debe hacer al insertar / recuperar de la tabla hash es calcular el hashCode para la clave dada y luego encontrar el grupo correcto recortando el hashCode al tamaño de hashTable haciendo hashCode% table_length. Aquí hay 2 ''declaraciones'' que probablemente haya leído en algún lugar

Si usa una potencia de 2 para table_length, encontrar (hashCode (key)% 2 ^ n) es tan simple y rápido como (hashCode (key) & (2 ^ n -1)). Pero si su función para calcular el código hash para una clave dada no es buena, definitivamente sufrirá la agrupación de muchas claves en unos pocos hash buckets.
Pero si usa números primos para table_length, los hashCodes calculados podrían asignarse a los diferentes hash buckets, incluso si tiene una función hashCode ligeramente estúpida.

Y aquí está la prueba.

Si supongamos que su función hashCode da como resultado los siguientes hashCodes entre {x, 2x, 3x, 4x, 5x, 6x ...}, entonces todos estos se agruparán en m número 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

Asegúrese de no generar demasiados códigos hash que sean múltiplos de otro código hash como en {x, 2x, 3x, 4x, 5x, 6x ...}. Pero esto puede ser difícil si se supone que su tabla hash tiene Millones de entradas. 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.

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

Me gustaría agregar algo a la respuesta de Steve Jessop (no puedo comentarlo porque no tengo suficiente reputación). Pero encontré algún material útil. Su respuesta es de mucha ayuda, pero cometió un error: el tamaño del cubo no debe ser una potencia de 2. Citaré el libro "Introducción al algoritmo" de Thomas Cormen, Charles Leisersen, y otros en la página 263:

Cuando se usa el método de división, usualmente evitamos ciertos valores de m. Por ejemplo, m no debería ser una potencia de 2, ya que si m = 2 ^ p, entonces h (k) es solo los p bits de orden más bajo de k. A menos que sepamos que todos los patrones de p-bit de orden bajo son igualmente probables, es mejor que diseñemos la función hash para que dependa de todos los bits de la clave. Como el Ejercicio 11.3-3 le pide que muestre, elegir m = 2 ^ p-1 cuando k es una cadena de caracteres interpretada en la raíz 2 ^ p puede ser una mala elección, porque permutar los caracteres de k no cambia su valor hash.

Espero eso ayude.

Para una función hash, no solo es importante minimizar las colisiones en general, sino hacer que sea imposible mantener el mismo hash mientras se cambian algunos bytes.

Digamos que tienes una ecuación: (x + y*z) % key = x con 0<x<key y 0<z<key . Si la clave es un número primo, n * y = la clave es verdadera para cada n en N y falsa para cada otro número.

Un ejemplo donde key no es un ejemplo principal: x = 1, z = 2 y key = 8 Debido a que key / z = 4 sigue siendo un número natural, 4 se convierte en una solución para nuestra ecuación y en este caso (n / 2) * y = la clave es verdadera para cada n en N. La cantidad de soluciones para la ecuación prácticamente se ha duplicado porque 8 no es un número primo.

Si nuestro atacante ya sabe que 8 es una posible solución para la ecuación, puede cambiar el archivo de 8 a 4 y aún así obtener el mismo hash.

Por lo general, una función hash simple funciona al tomar las "partes componentes" de la entrada (caracteres en el caso de una cadena) y multiplicarlas por las potencias de alguna constante, y sumarlas en algún tipo de entero. Así, por ejemplo, un hash típico (aunque no especialmente bueno) de una cadena podría ser:

(first char) + k * (second char) + k^2 * (third char) + ...

Luego, si se introducen un montón de cadenas que tienen el mismo primer carácter, los resultados serán todos el mismo módulo k, al menos hasta que se desborde el tipo entero.

[Como ejemplo, el código de hash de la cadena de Java es inquietantemente similar a este: hace que los caracteres se inviertan en orden, con k = 31. De este modo, se obtienen relaciones sorprendentes en el módulo 31 entre cadenas que terminan de la misma manera, y relaciones sorprendentes en el módulo 2 ^ 32 entre cadenas que son iguales, excepto cerca del final. Esto no desordena seriamente el comportamiento de la tabla hash.]

Una tabla hash funciona tomando el módulo del hash sobre el número de cubos.

Es importante en una tabla hash no producir colisiones para los casos probables, ya que las colisiones reducen la eficiencia de la tabla hash.

Ahora, supongamos que alguien pone un montón de valores en una tabla hash que tenga alguna relación entre los elementos, como que todos tengan el mismo primer carácter. Este es un patrón de uso bastante predecible, diría, por lo que no queremos que produzca demasiadas colisiones.

Resulta que "debido a la naturaleza de las matemáticas", si la constante utilizada en el hash y el número de cubos son coprime , las colisiones se minimizan en algunos casos comunes. Si no son coprime , entonces hay algunas relaciones bastante simples entre las entradas para las cuales las colisiones no se minimizan. Todos los hashes salen igual al módulo del factor común, lo que significa que todos caerán en la 1 / n ª de los grupos que tienen ese valor de módulo el factor común. Obtienes n veces más colisiones, donde n es el factor común. Como n es al menos 2, diría que es inaceptable que un caso de uso bastante simple genere al menos el doble de colisiones que lo normal. Si algún usuario va a dividir nuestra distribución en grupos, queremos que sea un accidente extraño, no un uso predecible simple.

Ahora, las implementaciones de tabla hash obviamente no tienen control sobre los elementos que se ponen en ellas. No pueden evitar que estén relacionados. Entonces, lo que hay que hacer es asegurarse de que la constante y los recuentos de depósitos sean coprime. De esa manera, no está confiando solo en el "último" componente para determinar el módulo del grupo con respecto a algún factor común pequeño. Por lo que sé, no tienen que ser los mejores para lograr esto, solo coprime.

Pero si la función hash y la tabla hash se escriben de forma independiente, entonces la tabla hash no sabe cómo funciona la función hash. Podría estar usando una constante con pequeños factores. Si tienes suerte, podría funcionar de manera completamente diferente y ser no lineal. Si el hash es lo suficientemente bueno, entonces cualquier cantidad de cubos está bien. Pero una tabla hash paranoica no puede asumir una buena función hash, por lo que debería usar un número primo de cubos. De manera similar, una función hash paranoica debería usar una constante primordial más grande, para reducir la posibilidad de que alguien use una cantidad de cubos que tienen un factor común con la constante.

En la práctica, creo que es bastante normal usar una potencia de 2 como el número de cubos. Esto es conveniente y evita tener que buscar alrededor o preseleccionar un número primo de la magnitud correcta. Por lo tanto, depende de la función hash para no usar multiplicadores pares, lo que generalmente es una suposición segura. Pero aún puede obtener malos comportamientos de hashing ocasionales basados en funciones de hash como la que se muestra arriba, y el recuento de grupos principales podría ayudar más.

Poner sobre el principio de que "todo tiene que ser primordial" es, por lo que sé, una condición suficiente pero no necesaria para una buena distribución sobre las tablas hash. Permite a todos interoperar sin necesidad de asumir que los demás han seguido la misma regla.

[Edición: hay otra razón más especializada para usar un número primo de cubos, que es si maneja las colisiones con el sondeo lineal. Luego, calcula una zancada a partir del código hash, y si esa zancada se convierte en un factor del conteo de cubetas, solo puedes hacer sondeos (bucket_count / stride) antes de que vuelvas a donde empezaste. El caso que más desea evitar es stride = 0, por supuesto, que debe tener una caja especial, pero para evitar que la caja especial bucket_count / stride sea igual a un entero pequeño, puede hacer que bucket_count prime y no importarle lo que se proporciona zancada no es 0.]

Se usan primes porque tiene buenas posibilidades de obtener un valor único para una función hash típica que usa polinomios módulo P. Supongamos que usa dicha función hash para cadenas de longitud <= N, y tiene una colisión. Eso significa que 2 polinomios diferentes producen el mismo valor módulo P. La diferencia de esos polinomios es nuevamente un polinomio del mismo grado N (o menos). No tiene más de N raíces (esta es la naturaleza de la matemática que se muestra a sí misma, ya que esta afirmación solo es válida para un polinomio sobre un campo => número primo). Entonces, si N es mucho menor que P, es probable que no tenga una colisión. Después de eso, el experimento probablemente puede mostrar que 37 es lo suficientemente grande como para evitar colisiones para una tabla hash de cadenas que tienen una longitud de 5-10, y es lo suficientemente pequeña como para usar en los cálculos.

Solo para proporcionar un punto de vista alternativo hay este sitio:

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

Lo que afirma que debería usar el mayor número posible de cubos en lugar de redondear a un número primo de cubos. Parece una posibilidad razonable. Intuitivamente, ciertamente puedo ver cómo un número mayor de cubos sería mejor, pero no puedo hacer un argumento matemático de esto.

Supongamos que su tamaño de tabla (o el número para el módulo) es T = (B * C). Ahora bien, si el hash para su entrada es como (N * A * B) donde N puede ser cualquier número entero, entonces su salida no estará bien distribuida. Porque cada vez que n se convierte en C, 2C, 3C, etc., su salida comenzará a repetirse. Es decir, su salida será distribuida solo en las posiciones C. Tenga en cuenta que C aquí es (T / HCF (tamaño de tabla, hash)).

Este problema se puede eliminar haciendo que el HCF 1. Los números primos son muy buenos para eso.

Otra cosa interesante es cuando T es 2 ^ N. Estos darán una salida exactamente igual a todos los N bits más bajos de hash de entrada. Como cada número se puede representar con potencias de 2, cuando tomaremos el módulo de cualquier número con T, restaremos todas las potencias de 2 números de forma, que son> = N, por lo que siempre emitiremos un número de patrón específico, dependiendo de la entrada . Esta es también una mala elección.

De manera similar, T como 10 ^ N también es malo debido a razones similares (patrón en notación decimal de números en lugar de binario).

Por lo tanto, los números primos tienden a dar mejores resultados distribuidos, por lo que son una buena opción para el tamaño de la tabla.

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Explicación bastante clara, con fotos también.

Edición: como resumen, se utilizan números primos porque tiene la mejor oportunidad de obtener un valor único al multiplicar los valores por el número primo elegido y sumarlos a todos. Por ejemplo, dada una cadena, multiplicar cada valor de letra con el número primo y luego sumarlos a todos le dará su valor hash.

Una mejor pregunta sería, ¿por qué exactamente el número 31?