¿Qué es un número primo sensata para el cálculo código hash?

Question

Eclipse 3.5 tiene una característica muy agradable para generar funciones hashcode (). Se generaría por ejemplo (ligeramente abreviada:)

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(Si tiene más atributos de la clase, result = prime * result + attribute.hashCode(); se repite para cada atributo adicional. Para enteros .hashCode () puede ser omitido.)

Esto parece bien, pero para la elección 31 para el primer. Es probable que se toma de la aplicación código hash de Java cadena, que fue utilizado por razones de rendimiento que se han ido mucho después de la introducción de multiplicadores de hardware. Aquí tienen muchas colisiones hashcode para pequeños valores de i y j: por ejemplo (0,0) y (-1,31) tienen el mismo valor. Creo que es una mala cosa (TM), ya que los valores pequeños producen a menudo. Para String.hashCode también encontrará muchas cadenas cortas con el mismo código hash, por ejemplo "Ca" y "DB". Si se toma un primo grande, este problema desaparece si se elige el primer derecho.

Así que mi pregunta: ¿qué es un buen primer elegir? ¿Qué criterios se aplican para encontrarlo?

Esto se entiende como una cuestión general - por lo que no quieren dar un rango de i y j. Pero supongo que en la mayoría de las aplicaciones relativamente pequeños valores se producen con más frecuencia que los valores grandes. (Si usted tiene grandes valores de la elección del primer probablemente es poco importante.) Puede que no hace mucha diferencia, pero una mejor opción es una manera fácil y obvio para mejorar esto - ¿por qué no lo hace? Commons Lang HashCodeBuilder también sugiere valores curiosamente pequeños.

( Aclaración : esto es no un duplicado de ¿por qué código hash de Java () en la cadena utilizan 31 como un multiplicador? ya que mi pregunta no tiene que ver con la historia de los 31 en el JDK, sino en lo que sería un mejor valor en el nuevo código usando la misma plantilla básica. Ninguna de las respuestas allí tratar de responder a eso.)

Answer 1

Le recomiendo usar 92821 . He aquí por qué.

Para dar una respuesta significativa a esto usted tiene que saber algo acerca de los posibles valores de i y j. Lo único que puedo pensar es en general, que en muchos casos los pequeños valores serán más comunes que los valores grandes. (Las probabilidades de que 15 aparecen como un valor en su programa son mucho mejores que, por ejemplo, 438281923.) por lo que parece una buena idea para hacer la colisión código hash más pequeño lo más grande posible mediante la elección de un primo adecuado. Para el 31 de este mal lugar - ya para i=-1 y j=31 que tiene el mismo valor hash como para i=0 y j=0

.

Dado que esto es interesante, he escrito un pequeño programa que buscó toda la gama int para el mejor privilegiada en este sentido. Es decir, para cada primo Busqué el valor mínimo de Math.abs(i) + Math.abs(j) todos los valores de i,j que tengan el mismo código hash como 0,0, y luego tomó el primer donde este valor mínimo es de lo más grande posible.

Drumroll : la mejor ubicación en este sentido es 486 187 739 (con el más pequeño de colisión siendo i=-25486, j=67194). Casi tan bueno y mucho más fácil de recordar es 92821 con la más pequeña colisión siendo i=-46272 and j=46016.

Si le das a "pequeña" otro sentido y quiere ser el mínimo de Math.sqrt(i*i+j*j) de la colisión lo más grande posible, los resultados son un poco diferentes: lo mejor sería 1322837333 con i=-6815 and j=70091, pero mi favorita 92821 (el más pequeño -46272,46016 colisión ) es de nuevo casi tan bueno como el mejor valor.

Yo reconozco que es bastante discutible si estos cálculos tiene mucho sentido en la práctica. Pero yo creo que la toma de 92821 como primer hace mucho más sentido que el 31, a menos que tenga buenas razones para no hacerlo.

Answer 2

En realidad, si se toma un número primo tan grande que se acerca a INT_MAX, que tienen el mismo problema debido a la aritmética de módulo. Si esperas para discutir su mayoría cadenas de longitud 2, tal vez una privilegiada, cerca de la raíz cuadrada de INT_MAX sería mejor, si las cadenas hash que son más largas que no importa tanto y las colisiones son inevitables de todos modos ...

Answer 3

Las colisiones pueden no ser un problema tan grande ... El objetivo principal del hash es evitar el uso iguales para 1: 1 comparaciones. Si usted tiene una aplicación donde es igual a "generalmente" muy barato para los objetos que han colisionado hashs, entonces esto no es un problema (en absoluto).

Al final, ¿cuál es la mejor manera de hash depende de lo que está comparando. En el caso de un par int (como en su ejemplo), utilizando operadores de bits básicos podría ser suficiente (como el uso de y o ^).

Answer 4

Es necesario definir el rango de i y j. Se puede usar un número primo para ambos.

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

Answer 5

elegiría 7243. Lo suficientemente grande como para evitar colisiones con los números pequeños. No se desborde a un número reducido rápidamente.

Answer 6

Sólo quiero señalar que código hash no tiene nada que ver con la primera. En la implementación JDK

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

He encontrado si reemplaza 31 27 , el resultado son muy similares.