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 hash dice que, en última instancia, debería modificarse 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 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 cubos? ¿O se trata de una vieja historia de programador que todos aceptan porque todos los demás la aceptan?

Por lo general, una función hash simple 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 sumá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) + ...

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

[Como ejemplo, el string hashCode de Java es inquietantemente similar a esto: hace el orden inverso de los caracteres, con k = 31. Entonces obtienes relaciones sorprendentes módulo 31 entre cadenas que terminan de la misma manera, y relaciones sorprendentes módulo 2 ^ 32 entre cadenas que son iguales excepto cerca del final. Esto no estropea seriamente el comportamiento de 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 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 tiene alguna relación entre los elementos, como que todos tienen 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 coprimos , las colisiones se minimizan en algunos casos comunes. Si no son coprimos, entonces hay algunas relaciones bastante simples entre las entradas para las cuales no se minimizan las colisiones. Todos los hashes salen igual al módulo del factor común, lo que significa que todos caerán en la 1ª parte de los cubos que tienen ese valor del módulo del 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 de lo normal. 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 tabla hash obviamente no tienen control sobre los elementos puestos en ellas. No pueden evitar que estén relacionados. Entonces, lo que hay que hacer es asegurarse de que la cuenta constante y el conteo sean coprimos. De esa manera, no dependerá únicamente del "último" componente para determinar el módulo de la cubeta con respecto a algún factor común pequeño. Por lo que sé, no tienen que ser primos 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 no ser lineal. Si el hash es lo suficientemente bueno, entonces cualquier conteo 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 cubos. Del mismo modo, una función hash paranoica debería usar una constante principal grande, para reducir la posibilidad de que alguien use varios 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 número de cubos. Esto es conveniente y ahorra tener que buscar o preseleccionar un número primo de la magnitud correcta. Por lo tanto, confía en la función hash para no usar incluso multiplicadores, lo que generalmente es una suposición segura. Pero aún puede obtener comportamientos de hash malos ocasionales basados ​​en funciones hash como la anterior, y el recuento de cubos principales podría ayudar aún más.

Poner sobre el principio de que "todo tiene que ser primo" es, hasta donde yo sé, una condición suficiente pero no necesaria para una buena distribución sobre tablas hash. Permite a todos interactuar sin necesidad de asumir 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 colisiones con sondeo lineal. Luego calcula un paso a partir del código hash, y si ese paso resulta ser un factor del conteo de cubos, entonces solo puede hacer sondas (bucket_count / stride) antes de volver a donde comenzó. El caso que más desea evitar es stride = 0, por supuesto, que debe estar en mayúsculas especiales, pero para evitar también una mayúscula especial bucket_count / stride igual a un número entero pequeño, puede hacer que bucket_count sea primo y no le importe lo que se proporciona zancada no es 0.]

Lo primero que debe hacer al insertar / volver a recibir de la tabla hash es calcular el hashCode para la clave dada y luego encontrar el depósito correcto recortando el hashCode al tamaño de la tabla hash haciendo el código hash% table_length. Aquí hay 2 'declaraciones' que probablemente hayas leído en alguna parte

1. 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 determinada no es buena, definitivamente sufrirá la agrupación de muchas claves en unos pocos cubos hash.
2. Pero si usa números primos para table_length, los códigos hash calculados podrían mapearse en los diferentes cubos hash incluso si tiene una función hashCode ligeramente estúpida.

Y aquí está la prueba.

Si se supone que su función hashCode da como resultado los siguientes hashCodes entre otros {x, 2x, 3x, 4x, 5x, 6x ...}, entonces todos estos se agruparán en solo m número de cubos, donde m = table_length / GreatestCommonFactor (longitud_tabla, 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 un poco difícil si se supone que su tabla hash tiene millones de entradas. O simplemente haga que m sea igual a table_length haciendo GreatestCommonFactor (table_length, x) 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 sea 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/

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

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

Una mejor pregunta 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. Fijar el divisor en el tamaño de la tabla también asegura que el número no pueda ser mayor que la tabla.

Los primos se utilizan porque tiene buenas posibilidades de obtener un valor único para una función hash típica que utiliza polinomios módulo P. Digamos 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 del módulo P. La diferencia de esos polinomios es nuevamente un polinomio del mismo grado N (o menos). No tiene más que N raíces (aquí es donde 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 tenga una colisión. Después de eso, el experimento probablemente puede demostrar 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 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 afirma que debe usar el mayor número de cubos posible en lugar de redondear a un número primo de cubos. Parece una posibilidad razonable. Intuitivamente, ciertamente puedo ver cómo un mayor número de cubos sería mejor, pero no puedo hacer un argumento matemático sobre esto.

Los primos son números únicos. Son únicos en eso, el producto de un primo con cualquier otro número tiene la mejor oportunidad de ser único (no tan único como el primo en sí mismo, por supuesto) debido al hecho de que se utiliza un primo para componerlo. Esta propiedad se usa en funciones hash.

Dada una cadena "Samuel", puede generar un hash único al multiplicar cada uno de los dígitos o letras constituyentes con un número primo y sumarlos. 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 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/

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

Muchas funciones hash combinan los diversos elementos en los datos multiplicándolos con algunos factores que modulan 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 podría ocurrir que al variar el elemento de datos no se extiendan los datos en toda la tabla. Si elige una prima 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 números primos impares, por lo que también debe estar seguro usando potencias de dos para su tabla hash (por ejemplo, Eclipse usa 31 cuando genera el método Java hashCode ()).

Suponga que el tamaño de su tabla (o el número de módulo) es T = (B * C). Ahora, 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 posiciones C. Tenga en cuenta que C aquí es (T / HCF (tamaño de tabla, 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 inferiores de hash de entrada. Como cada número puede representarse 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 tanto, siempre emiten un número de patrón específico, dependiendo de la entrada . Esta también es una mala elección.

Del mismo modo, 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).

Entonces, 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.

Copiando desde 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.

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

Me gustaría agregar algo para la respuesta de Steve Jessop (no puedo comentarlo ya que no tengo suficiente reputación). Pero encontré material útil. Su respuesta es de gran 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, et al en la página 263:

Cuando usamos el método de división, generalmente 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 bits p 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 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 permanecer con el mismo hash mientras se cambian algunos bytes.

Digamos que tienes una ecuación: (x + y*z) % key = xcon 0<x<keyy 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 cualquier otro número.

Un ejemplo donde la clave no es un ejemplo principal: x = 1, z = 2 y clave = 8 Debido a que clave / 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 primo.

Si nuestro atacante ya sabe que 8 es una solución posible para la ecuación, puede cambiar el archivo de producir 8 a 4 y aún así 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 cierto:

• 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:

clave = "clave"

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

asigna a una identificación única

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

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

Sé que esto se simplifica, pero espero hacer realidad la idea general.

"La naturaleza de las matemáticas" con respecto a los módulos de potencia primaria es que son un componente básico de un campo finito . Los otros dos bloques de construcción son una operación de suma y multiplicación. La propiedad especial de los módulos primos es que forman un campo finito con las operaciones de suma y multiplicación "regulares", simplemente llevadas al módulo. Esto significa que cada multiplicación se asigna a un módulo entero diferente al primo, al igual que cada suma.

Los módulos principales son ventajosos porque:

• Dan la mayor libertad al elegir el multiplicador secundario en el hashing secundario, todos los multiplicadores excepto 0 terminarán visitando todos los elementos exactamente una vez
• Si todos los valores hash son menores que el módulo, no habrá colisiones
• Los primos aleatorios se mezclan mejor que la potencia de dos módulos y comprimen la información de todos los bits, no solo un subconjunto

Sin embargo, tienen un gran inconveniente, requieren una división entera, que toma muchos (~ 15-40) ciclos, incluso en una CPU moderna. Con aproximadamente la mitad del cálculo, uno puede asegurarse de que el hash se mezcle muy bien. Dos operaciones de multiplicación y xorshift se mezclarán mejor que un moudulus principal. Entonces podemos usar cualquier tamaño de tabla hash y la reducción de hash es más rápida, dando 7 operaciones en total para una potencia de 2 tamaños de tabla y alrededor de 9 operaciones para tamaños arbitrarios.

Recientemente examiné muchas de las implementaciones de tablas hash más rápidas y la mayoría de ellas no usan módulos principales.

Esta pregunta se fusionó con la pregunta más apropiada, por qué las tablas hash deberían usar matrices de primer tamaño, y no potencia de 2. Para las funciones hash en sí, hay muchas buenas respuestas aquí, pero para la pregunta relacionada, por qué algunas tablas hash críticas para la seguridad , como glibc, use matrices de primer tamaño, todavía no hay ninguna.

Generalmente la potencia de 2 mesas es mucho más rápida. Ahí está el costoso h % n => h & bitmask, donde se puede calcular la máscara de bits mediante clz("contar ceros iniciales") del tamaño n. Una función de módulo necesita hacer una división entera que es aproximadamente 50 veces más lenta que una lógica and. Hay algunos trucos para evitar un módulo, como usar https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ de Lemire , pero en general las tablas hash rápidas usan potencia de 2, y las tablas hash seguras usan primos.

¿Porque?

La seguridad en este caso se define por los ataques a la estrategia de resolución de colisiones, que es con la mayoría de las tablas hash solo búsqueda lineal en una lista vinculada de colisiones. O con la búsqueda lineal de tablas de direccionamiento abierto más rápida en la tabla directamente. Entonces, con la potencia de 2 tablas y un cierto conocimiento interno de la tabla, por ejemplo, el tamaño o el orden de la lista de claves proporcionadas por alguna interfaz JSON, obtiene el número de bits correctos utilizados. El número de unos en la máscara de bits. Esto suele ser inferior a 10 bits. Y para 5-10 bits es trivial para colisiones de fuerza bruta incluso con las funciones hash más fuertes y lentas. Ya no obtienes la seguridad total de tus funciones hash de 32 bits o 64 bits. Y el objetivo es utilizar funciones de hash pequeñas y rápidas, no monstruos como murmullos o incluso siphash.

Por lo tanto, si proporciona una interfaz externa a su tabla hash, como un solucionador de DNS, un lenguaje de programación, ... desea preocuparse por las personas que abusan y a las que les gustan los servicios de DOS. Normalmente es más fácil para esas personas cerrar su servicio público con métodos mucho más fáciles, pero sucedió. Entonces a la gente le importaba.

Entonces, las mejores opciones para prevenir tales ataques de colisión son

1) usar tablas prime, porque entonces

• los 32 o 64 bits son relevantes para encontrar el depósito, no solo unos pocos.
• la función de cambio de tamaño de la tabla hash es más natural que solo el doble. La mejor función de crecimiento es la secuencia de Fibonacci y los primos se acercan más a eso que duplicarse.

2) usa mejores medidas contra el ataque real, junto con un poder rápido de 2 tamaños.

• cuente las colisiones y cancele o duerma en los ataques detectados, que son números de colisión con una probabilidad de <1%. Como 100 con tablas hash de 32 bits. Esto es lo que, por ejemplo, hace djb's dns resolver.
• Convierta la lista vinculada de colisiones en árboles con O (log n) buscar no O (n) cuando se detecta un ataque de colisión. Esto es lo que, por ejemplo, hace Java.

Existe un mito generalizado de que las funciones hash más seguras ayudan a prevenir tales ataques, lo cual es incorrecto como lo expliqué. No hay seguridad solo con bits bajos. Esto solo funcionaría con tablas de primer tamaño, pero usaría una combinación de los dos métodos más lentos, hash lento más módulo de primo lento.

Las funciones de hash para las tablas de hash deben ser principalmente pequeñas (para que estén disponibles) y rápidas. La seguridad solo puede venir evitando la búsqueda lineal en las colisiones. Y no usar funciones hash trivialmente malas, como las insensibles a algunos valores (como \ 0 cuando se usa la multiplicación).

El uso de semillas aleatorias también es una buena opción, las personas comenzaron con eso primero, pero con suficiente información de la tabla, incluso una semilla aleatoria no ayuda mucho, y los lenguajes dinámicos generalmente hacen que sea trivial obtener la semilla a través de otros métodos, ya que se almacena en ubicaciones de memoria conocidas.

function eratosthenes(n) {

    function getPrime(x) {
        var middle = (x-(x%2))/2;
        var arr_rest = [];
        for(var j=2 ; j<=middle;j++){
            arr_rest.push(x%j);
        }

        if(arr_rest.indexOf(0) == -1) {
            return true
        }else {
            return false
        }

    }
    if(n<2)  {
        return []
    }else if(n==2){
        return [2]
    }else {
        var arr = [2]
        for(var i=3;i<n;i++) {
            if(getPrime(i)){
                arr.push(i)
            }
        }
    }

    return arr;
}