¿Por qué deberían las funciones hash usar un módulo de número primo?

Hace mucho tiempo, compré un libro de estructuras de datos de la mesa de gangas por $ 1.25. En él, la explicación de una función hashing decía que finalmente debería modificar por 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 sobre la naturaleza de las matemáticas, y todavía no puedo entenderlo.

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

Por lo general, una simple función hash funciona tomando las “partes componentes” de la entrada (caracteres en el caso de una cadena), y multiplicándolas por las potencias de alguna constante, y sujetándolas juntas en algún tipo entero. Entonces, 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) + ... 

Entonces, si se alimenta un grupo de cadenas que tienen todas la misma primera char, entonces los resultados serán todos del mismo módulo k, al menos hasta que el tipo entero se desborde.

[Como ejemplo, el hashCode de la cadena de Java es inquietantemente similar a este: hace el orden inverso de los caracteres, con k = 31. Así que obtienes relaciones llamativas módulo 31 entre cadenas que terminan de la misma manera, y relaciones llamativas módulo 2 ^ 32 entre cadenas que son iguales excepto cerca del final. Esto no estropea seriamente el comportamiento de hashtable.]

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 casos probables, ya que las colisiones reducen la eficacia de la tabla hash.

Ahora, supongamos que alguien pone un montón de valores en una tabla hash que tienen 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 se produzcan demasiadas colisiones.

Resulta que “debido a la naturaleza de las matemáticas”, si la constante utilizada en el hash y el número de cubetas 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 de módulo al factor común, lo que significa que todos caerán en la 1 / n th de las cubetas que tienen ese valor módulo el factor común. Obtienen n veces más colisiones, donde n es el factor común. Como n es al menos 2, diría que no es aceptable que un caso de uso bastante simple genere al menos el doble de colisiones que las normales. Si algún usuario va a dividir nuestra distribución en cubos, queremos que sea un accidente extraño, no un simple uso predecible.

Ahora, las implementaciones de tablas hash obviamente no tienen control sobre los elementos puestos en ellas. No pueden evitar que se relacionen. Entonces, lo que hay que hacer es asegurarse de que la constante y el recuento de cubos sean coprimos. De esta forma, no depende únicamente del “último” componente para determinar el módulo del cubo con respecto a algún pequeño factor común. Por lo que yo sé, no tienen que ser primos para lograr esto, solo en primicia.

Pero si la función hash y la tabla hash se escriben de forma independiente, 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 no ser lineal. Si el hash es lo suficientemente bueno, entonces cualquier recuento de cubos está bien. Pero una tabla hash paranoica no puede asumir una buena función hash, por lo que debe usar un número primo de cubetas. De manera similar, una función hash paranoide debe usar una constante principal más grande, para reducir la posibilidad de que alguien use una cantidad de cubos que tiene un factor común con la constante.

En la práctica, creo que es bastante normal usar una potencia de 2 como número de cubos. Esto es conveniente y ahorra tener que buscar o preseleccionar un número primo de la magnitud correcta. Así que confía en la función hash para no usar multiplicadores, lo que generalmente es una suposición segura. Pero todavía puede obtener ocasionales comportamientos hash incorrectos basados ​​en funciones hash como la anterior, y el recuento máximo de cubetas podría ayudar aún más.

Poner el principio de que “todo tiene que ser primordial” es, hasta donde yo sé, una condición suficiente, pero no necesaria, para una buena distribución sobre los hashtables. Permite que todos puedan interoperar sin la necesidad de suponer que los demás han seguido la misma regla.

[Editar: hay otra razón más especializada para usar un número primo de cubos, que es si manejas las colisiones con sondeos lineales. Luego se calcula un paso adelante desde el código hash, y si esa zancada es un factor del recuento de cubos, entonces solo se pueden hacer sondas (bucket_count / stride) antes de volver al punto de partida. El caso que más quieres evitar es zancada = 0, por supuesto, que debe tener una envoltura especial, pero para evitar también la división de compartimiento especial / zancada igual a un número entero pequeño, puedes hacer que el primer depósito sea primo y no importa qué zancada se proporciona, no es 0.]

Lo primero que debe hacer cuando inserta / recupera desde la tabla hash es calcular el hashCode para la clave dada y luego encontrar el depósito correcto recortando hashCode al tamaño de hashTable haciendo hashCode% table_length. Aquí hay 2 ‘declaraciones’ que probablemente haya leído en algún lado

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

Y aquí está la prueba.

Si supone que su función hashCode da como resultado los siguientes hashCodes entre otros {x, 2x, 3x, 4x, 5x, 6x …}, todos estos se agruparán en solo m número de segmentos, donde m = table_length / GreatestCommonFactor (tabla_length, x). (Es trivial verificar / derivar esto). Ahora puede hacer una de las siguientes acciones para evitar clustering

Asegúrese 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 su 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 – http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

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

Una explicación bastante clara, con imágenes también.

Editar: como resumen, se utilizan primos porque tiene la mejor posibilidad de obtener un valor único al multiplicar los valores por el número primo elegido y sumrlos todos. Por ejemplo, si se le da una cadena, al multiplicar el valor de cada letra con el número primo y luego agregar todo eso, obtendrá su valor hash.

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

tl; dr

index[hash(input)%2] daría lugar a 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 asegura que el número no puede ser mayor que la tabla.

Se utilizan primos porque tiene buenas posibilidades de obtener un valor único para una función hash típica que utiliza módulos de polinomios P. Digamos que utiliza esa función hash para cadenas de longitud < = N y tiene una colisión. Eso significa que 2 polinomios diferentes producen el mismo módulo de valor P. La diferencia de esos polinomios es nuevamente un polinomio del mismo grado N (o menos). No tiene más de N raíces (aquí se muestra la naturaleza de las matemáticas, ya que esta afirmación solo es cierta para un polinomio sobre un campo => número primo). Entonces, si N es mucho menor que P, es probable que no tengas una colisión. Después de eso, el experimento probablemente demuestre que 37 es lo suficientemente grande como para evitar colisiones para una tabla hash de cadenas que tienen una longitud de 5 a 10, y es lo suficientemente pequeña como para usarla 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 significa que debe usar la mayor cantidad de cubos posible en lugar de redondear a un número primo de cubos. Parece una posibilidad razonable. Intuitivamente, ciertamente puedo ver cómo sería mejor un gran número de cubos, pero no puedo hacer un argumento matemático de esto.

Primes son números únicos. Son únicos en eso, el producto de un primo con cualquier otro número tiene la mejor posibilidad de ser único (no tan único como el propio primo del curso) debido al hecho de que se usa un primo para componerlo. Esta propiedad se usa en funciones hash.

Dada una cadena “Samuel”, puedes generar un hash único multiplicando cada uno de los dígitos o letras constituyentes con un número primo y sumrlos. Es por eso que se usan primos.

Sin embargo, usar primos es una técnica antigua. La clave aquí es comprender que, siempre que pueda generar una clave suficientemente única, también podrá pasar a otras técnicas de hash. 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/

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

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

No quiere 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 al variar el elemento de datos no se distribuyan los datos en toda la tabla. Si elige un primo para el tamaño de la tabla, un factor tan común es muy poco probable.

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

Supongamos que el tamaño de su tabla (o el número de 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 se distribuirá solo en las posiciones C. Tenga en cuenta que C aquí es (T / HCF (table-size, hash)).

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

Otra cosa interesante es cuando T es 2 ^ N. Estos darán salida exactamente igual que todos los N bits más bajos de entrada-hash. Como cada número puede representar potencias de 2, cuando tomemos el módulo de cualquier número con T, restaremos todas las potencias de 2 números de forma, que son> = N, por lo tanto siempre emitiendo 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 binarios).

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

Me gustaría agregar algo para la respuesta de Steve Jessop (no puedo comentar sobre eso porque no tengo suficiente reputación). Pero encontré un material útil. Su respuesta es de gran ayuda, pero cometió un error: el tamaño del cubo no debería ser una potencia de 2. Haré una cita del libro “Introducción al algoritmo” de Thomas Cormen, Charles Leisersen, et al en la página 263:

Cuando usamos 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 simplemente el p de bits de orden más bajo de k. A menos que sepamos que todos los patrones de p bits de orden inferior 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 lo muestre, elegir m = 2 ^ p-1 cuando k es una cadena de caracteres interpretada en radix 2 ^ p puede ser una elección deficiente, porque permutando los caracteres de k no cambia su valor hash.

Espero eso ayude.

Copia 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 en la base 2. Solo piense en cómo funciona lo mismo para la base 10:

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

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

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

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

Supongamos que tiene una ecuación: (x + y*z) % key = x con la (x + y*z) % key = x 0 y la 0 0 . Si key es un primenumber n * y = la clave es verdadera para cada n en N y falsa para cualquier otro número.

Un ejemplo donde la clave no es un buen ejemplo: x = 1, z = 2 y clave = 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 primo.

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

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 simple observación que hice.

Puede encontrar todos los detalles en el artículo aquí , pero suponga que lo siguiente es verdadero:

  • Usar 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 primordial. Básicamente, primo 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:

llave = “llave”

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

mapas a una identificación única

Ahora queremos una ubicación única para nuestro valor, así que

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

Sé que esto se simplifica, pero espero tener una idea general.