Estos dos números son números primos suficientemente grandes. Lea el artículo sobre Hash Table en Wikipedia para obtener más información.
Boris Pavlović
Respuestas:
140
1231 y 1237 son solo dos números primos arbitrarios (suficientemente grandes) . Cualquier otro dos números primos grandes estaría bien.
¿Por qué primos?
Supongamos por un segundo que seleccionamos números compuestos (no primos), digamos 1000 y 2000. Al insertar valores booleanos en una tabla hash, verdadero y falso irían al cubo 1000 % Nresp 2000 % N(donde Nestá el número de cubos).
Ahora nota que
1000 % 8 mismo cubo que 2000 % 8
1000 % 10 mismo cubo que 2000 % 10
1000 % 20 mismo cubo que 2000 % 20
....
en otras palabras, provocaría muchas colisiones .
Esto se debe a que la factorización de 1000 (2 3 , 5 3 ) y la factorización de 2000 (2 4 , 5 3 ) tienen muchos factores comunes. Por tanto, se eligen los números primos, ya que es poco probable que tengan factores comunes con el tamaño del cubo.
Por qué grandes números primos. ¿No servirían 2 y 3?
Al calcular códigos hash para objetos compuestos, es común agregar los códigos hash para los componentes. Si se utilizan valores demasiado pequeños en un conjunto hash con una gran cantidad de depósitos, existe el riesgo de terminar con una distribución desigual de objetos.
¿Importan las colisiones? ¿Los booleanos solo tienen dos valores diferentes de todos modos?
Los mapas pueden contener valores booleanos junto con otros objetos. Además, como señaló Drunix, una forma común de crear funciones hash de objetos compuestos es reutilizar las implementaciones del código hash de los subcomponentes, en cuyo caso es bueno devolver números primos grandes.
Supongo que son lo suficientemente grandes. Para obtener un gcd mayor que 1, necesitaría al menos 2*1231 = 2462cubos. ¿Son las colisiones un problema en tal situación?
aioobe
2
Sin embargo, es interesante que no sean realmente "bastante grandes" considerando lo que puede caber en un int. Supongo que son lo suficientemente grandes para funcionar bien con JDK Hashtable, pero aún lo suficientemente pequeños como para minimizar los costos de cálculo.
Thilo
2
Sí, se me ocurrió también que no son que grande. ¿Pero cree que hay un costo más alto con primos más grandes?
aioobe
3
@Thilo que había necesidad de un múltiplo de 1231 * 1237 = 1,522,747 cubos antes de que chocarían, que es un montón lo suficientemente grande
monstruo de trinquete
2
Yo diría que llevar a colisiones con el conteo de cubos no es realmente un problema con boolean, sino más bien la construcción común sobre cómo obtenemos el código hascode de un objeto compuesto, es decir, multiplicando los códigos hash de los componentes con algunas constantes y sumándolos.
Drunix
2
Además de todo lo dicho anteriormente, también puede ser un pequeño huevo de Pascua de los desarrolladores:
verdadero: 1231 => 1 + 2 + 3 + 1 = 7
7 - es un número de la suerte en las tradiciones europeas;
falso: 1237 => 1 + 2 + 3 + 7 = 13
13 (también conocido como la docena del diablo) - número de la mala suerte.
Respuestas:
1231 y 1237 son solo dos números primos arbitrarios (suficientemente grandes) . Cualquier otro dos números primos grandes estaría bien.
¿Por qué primos?
Supongamos por un segundo que seleccionamos números compuestos (no primos), digamos 1000 y 2000. Al insertar valores booleanos en una tabla hash, verdadero y falso irían al cubo
1000 % Nresp2000 % N(dondeNestá el número de cubos).Ahora nota que
1000 % 8mismo cubo que2000 % 81000 % 10mismo cubo que2000 % 101000 % 20mismo cubo que2000 % 20en otras palabras, provocaría muchas colisiones .
Esto se debe a que la factorización de 1000 (2 3 , 5 3 ) y la factorización de 2000 (2 4 , 5 3 ) tienen muchos factores comunes. Por tanto, se eligen los números primos, ya que es poco probable que tengan factores comunes con el tamaño del cubo.
Por qué grandes números primos. ¿No servirían 2 y 3?
Al calcular códigos hash para objetos compuestos, es común agregar los códigos hash para los componentes. Si se utilizan valores demasiado pequeños en un conjunto hash con una gran cantidad de depósitos, existe el riesgo de terminar con una distribución desigual de objetos.
¿Importan las colisiones? ¿Los booleanos solo tienen dos valores diferentes de todos modos?
Los mapas pueden contener valores booleanos junto con otros objetos. Además, como señaló Drunix, una forma común de crear funciones hash de objetos compuestos es reutilizar las implementaciones del código hash de los subcomponentes, en cuyo caso es bueno devolver números primos grandes.
Preguntas relacionadas:
fuente
2*1231 = 2462cubos. ¿Son las colisiones un problema en tal situación?Además de todo lo dicho anteriormente, también puede ser un pequeño huevo de Pascua de los desarrolladores:
7 - es un número de la suerte en las tradiciones europeas;
13 (también conocido como la docena del diablo) - número de la mala suerte.
fuente