En la multiplicación de enteros, desbordamiento y pérdida de información

Question

Estoy leyendo a través de Chapter 3 de de Joshua Bloch Effective Java. En Tema 8: Siempre anular hashCode cuando se sobrescribe equals, el autor utiliza el paso siguiente que combina en su función hash:

result = 37 * result + c; 

A continuación, explica por qué 37 se eligió (el subrayado es nuestro):

Se eligió el multiplicador 37 porque es un primo impar. Si fue par y la multiplicación se desbordó, la información se perdería porque la multiplicación por dos es equivalente a cambiar. Las ventajas de usar un número primo son menos claras que , pero es tradicional usar primos para este propósito.

Mi pregunta es ¿por qué es importante que el factor de combinación (37) es extraña? ¿El desbordamiento de la multiplicación no resultaría en una pérdida de información independientemente de si el factor era impar o par?

Answer 1

Considere lo que sucede cuando un valor positivo se multiplica repetidamente por dos en una representación de base 2: todos los bits establecidos eventualmente marchan hacia el final, dejándolo con cero.

Un multiplicador par resultaría en códigos hash con menos diversidad.

Los números impares, por otro lado, pueden provocar un desbordamiento, pero sin pérdida de diversidad.

Answer 2

El propósito de un hashCode es tener bits aleatorios en base a la entrada (especialmente los bits inferiores como éstos se utilizan a menudo más)

Cuando múltiple por 2 el bit más bajo sólo puede ser 0, que carece de aleatoriedad . Si multiplicas por un número impar, el bit más bajo puede ser impar o par.

---

Una pregunta similar es lo que se puede conseguir aquí

public static void main(String... args) { 
    System.out.println(factorial(66)); 
} 

public static long factorial(int n) { 
    long product = 1; 
    for (; n > 1; n--) 
     product *= n; 
    return product; 
} 

impresiones

0 

Cada segundo número es un uniforme y cada luz un múltiplo de 4, etc.

Answer 3

La solución está en Number Theory y el Lowest common denominator de su multiplicador y su número de módulo.

Un ejemplo puede ayudar. Digamos que en lugar de 32 bits solo tienes 2 bits para representar un número. Entonces tienes 4 números (clases). 0, 1, 2 y 3

un desbordamiento en la CPU es lo mismo que una operación de módulo

Class - x2 - mod 4 - x2 - mod 4 

0  0  0  0  0 

1  2  2  4  0 

2  4  0  0  0 

3  6  2  4  0 

Después de 2 operaciones que solo recibió 1 número posible (clase) izquierda. Entonces has 'perdido' la información.

Class - x3 - mod 4 - x3 - mod 4 ... 

0  0  0  0  0 

1  3  3  9  1 

2  6  2  6  2 

3  9  1  3  3 

Esto puede durar para siempre y usted todavía tiene las 4 clases. Entonces no pierdes información.

La clave es que la pantalla LCD de su muliplier y su clase de módulo es 1. Eso es cierto para todos los números impares porque su número de módulo es actualmente siempre una potencia de 2. No tienen que ser primos y no tienen ser 37 específicamente. Pero la pérdida de información es sólo una razón por criterios 37 se recoge otros criterios de distribución de los valores son etc.

Answer 4

no matemáticas versión simple de por qué ... se utilizan

Los números primos de hash para mantener la diversidad.

Quizás la diversidad es más importante debido a las implementaciones de Conjunto y Mapa. Estas implementaciones usan los últimos bits de números hash de objetos para indexar matrices internas de entradas.

Por ejemplo, en un HashMap con tabla interna (matriz) para entradas con tamaño 8, utilizará los últimos 3 bits de números hash para ingresar a la tabla.

 

    static int indexFor(int h, int length) { 
     return h & (length-1); 
    } 

De hecho no lo es, pero si el objeto entero tendría

 

    hash = 4 * number; 

la mayoría de elementos de la tabla estará vacía, pero algunos contendrá demasiadas entradas. Esto llevaría a iteraciones adicionales y operaciones de comparación al buscar una entrada particular.

Creo que la principal preocupación de Joshua Bloch fue distribuir los números hash todo lo posible para optimizar el rendimiento de las colecciones mediante la distribución uniforme de objetos en Maps and Sets. Los números primos intuitivamente son un buen factor de distribución.

Answer 5

Los números primos no son estrictamente necesarios para garantizar la diversidad; lo que es necesario es que el factor sea relativamente primordial para el módulo.

Dado que el módulo para la aritmética binaria es siempre una potencia de dos, cualquier número impar es relativamente primo, y sería suficiente. Sin embargo, si tomara un módulo distinto al desbordamiento, un número primo continuaría asegurando la diversidad (suponiendo que no eligió el mismo primo ...).