El enfoque estándar para calcular un código hash es multiplicar por 31.
Bloch afirma:
Se eligió el valor 31 porque es un primo impar. Si fuera par y la multiplicación se desbordara, se perdería información, ya que multiplicar por 2 es lo mismo que desplazar
No estoy seguro de entender esto. Si la multiplicación se desborda, el valor se pierde independientemente de si es par/impar, ¿verdad?
En el siguiente ejemplo, no estoy seguro de cuál es la diferencia:
int number = 2000000000; System.out.println(Integer.toBinaryString(number)); number*=2; System.out.println(Integer.toBinaryString(number)); 1110111001101011001010000000000 11101110011010110010100000000000y
int number = 2000000000; System.out.println(Integer.toBinaryString(number)); number*=3; System.out.println(Integer.toBinaryString(number)); 1110111001101011001010000000000 1100101101000001011110000000000Los números pares siempre olvidan al menos el bit más significativo. El msb solo afecta el resultado si el multiplicador es impar, porque solo cuando se desplaza a la izquierda en 0 pasos, no desaparece inmediatamente. Eso es también lo que se quiso decir con "se perdería información, ya que multiplicar por 2 es lo mismo que cambiar". En su ejemplo, no tiene muchos problemas visibles porque el resultado no se desborda, 2000000000 = 0x77359400 claramente no tiene el bit superior establecido (se ajusta a negativo como un entero con signo, pero eso es irrelevante, el bit de signo es un bit normal que lleva un poco de información, cambiar algo no destruye la información), trabajar hacia atrás es ambiguo si era 0x77359400 antes del cambio o 0xF7359400. Espero que esto sea suficiente "justificación intuitiva".
La verdadera prueba de que sólo los multiplicadores impares conservan toda la información es que son precisamente los números impares los que tienen inversos multiplicativos módulo una potencia de dos. x tiene un módulo inverso multiplicativo m iff mcd(x, m) == 1, dado que m es 2 k esa condición se cumple solo para números impares: no se puede cumplir para números pares porque tendrían un factor de 2 en común, y dado que un número impar no tiene factores de 2 pero 2k solo tiene factores de 2, nunca comparten ningún factor.
El hecho de que haya un inv(x) inverso significa que puedes escribir number * x * inv(x) = number para que no se pierda información en la primera multiplicación.
Como ejemplo concreto, inv(3) = 0xaaaaaaab entonces:
2000000000 * 3 = 0x65a0bc00 0x65a0bc00 * 0xaaaaaaab = 2000000000