¿Cómo debo mapear long to int en hashCode()?

Question

Tengo un rango de objetos que tienen un campo long cuyo valor identifica de manera única un objeto en particular en todo mi sistema, al igual que un GUID. He reemplazado Object.equals() para usar esta identificación para comparar, porque quiero que funcione con copias del objeto. Ahora también quiero sobrescribir Object.hashCode(), lo que básicamente significa mapear long a un valor de retorno de int.

Si entendí correctamente el propósito de hashCode, se usa principalmente en tablas hash, por lo que sería deseable una distribución uniforme. Esto significaría que simplemente devolver id % 2^32 sería suficiente. ¿Eso es todo, o debería estar al tanto de otra cosa?

Answer 1

Desde Java 8 se puede utilizar

Long.hashCode(guid); 

Para versiones anteriores de Java que puede utilizar el siguiente:

Long.valueOf(guid).hashCode(); 

Tenga en cuenta que esta solución crea un nuevo objeto de la pila, mientras que la primera no (aunque es probable que Java optimice la creación del objeto) ..

Mirando los documentos, en ambos sentidos simplemente use el siguiente algoritmo:

(int)(this.longValue()^(this.longValue()>>>32)) 

Estas son soluciones decentes, ya que hacen uso de la biblioteca Java, siempre es mejor aprovecharse de algo que ya se ha probado.

Answer 2

Ha entendido correctamente el propósito de hashCode. Sí, es deseable una distribución uniforme (aunque no es un requisito real).

Sugeriría ((id >> 32)^id).

La expresión anterior:

• Usos todos los bits del valor original, no se descarta ninguna información por adelantado. Por ejemplo, dependiendo de cómo esté generando los ID, los bits superiores podrían cambiar más frecuentemente (o lo contrario).
• No introduce ningún sesgo hacia valores con más unos (ceros), como sería el caso si las dos mitades se combinaron con una operación OR (Y).

Answer 3

int result = (int)((longVal >> 32)^longVal); 

será más bien distribuido, porque módulo no volverá valor diferente si sólo bits superiores del valor de su tiempo ha cambiado.

Answer 4

que es un poco de una cosa menor si no estás usando Guava ya, pero la guayaba puede do this for you muy bien:

public int hashCode() { 
    return Longs.hashCode(id); 
} 

que le da el equivalente de Long.valueOf(id).hashCode():

return (int) (value^(value >>> 32)); 

Además, si tuviera otros valores u objetos que formaban parte del código hash, podría escribir

return Objects.hashCode(longValue, somethingElse, ...); 

El long sería autoboxed en un Long, por lo que obtendría el hashcode correcto como parte del hashcode general.

Answer 5

(l >> 32)^l es un buen hashcode en la mayoría de los casos; particularmente cuando el largo tiene una distribución uniforme.

Dado que fue la respuesta aceptada, publicaré esto para aclarar algunos de mis comentarios sobre cuándo NO es un buen hashcode por mucho tiempo.

El ejemplo que dio fue una clase Point como esto:

public class Point { 
    private final long coords; //x in high-bits, y in low 
    public int getX() { 
     return (int)(coords >> 32); 
    } 
    public int getY() { 
     return (int)coords; 
    } 
    public int hashCode() { 
     return (int)((coords >> 32)^(coords)); 
    } 
} 

Puede parecer artificial, pero de vez en cuando tener múltiples "campos" empaquetados en un largo.

Así que el campo coords representa 32 bits de xy 32 bits de y. ¿Por qué es esto un problema? Bueno, no es si cada uno de xey están distribuidos uniformemente sobre sus respectivos 32 bits. Pero eso es poco probable en la práctica. Lo que es más probable es que X e Y estén delimitados por un número. Digamos 1024 ya que son 2^10. Esto significa que como máximo se establecen las inferiores 10 bits de cada X e Y:

00000000 00000000 000000XX XXXXXXXX 00000000 00000000 000000YY YYYYYYYY 

hay 2^20 (1024 * 1024) combinaciones posibles. ¿Pero cuál es la operación que hashCode está haciendo?

00000000 00000000 000000XX XXXXXXXX 
^ 00000000 00000000 000000YY YYYYYYYY 
------------------------------------- 
= 00000000 00000000 000000?? ???????? 

Hay como máximo 2^10 (1024) posibles valores hashCode ya que sólo los bajos 10 bits nunca pueden ser distinto de cero. La relación de valores hash a valores reales es 1024:(1024*1024) o 1:1024. Así que desde el principio hay una probabilidad de 1/1024 de que dos números tengan el mismo hash.

Ahora calculemos la probabilidad de una colisión aplicando matemática del birthday problem. Sea p (n) la probabilidad de que con n valores habrá al menos una colisión. Sabemos que p (1025+) = 1 ya que solo hay 1024 valores.

p(n) = 1 - (n! * (1024 choose n))/1024^n 

Esto se resuelve a lo siguiente:

n: p(n) 
1: 0.00000 
2: 0.00098 
3: 0.00293 
4: 0.00585 
5: 0.00973 
6: 0.01457 
... 
38: 0.50096 
... 
79: 0.95444 
... 
148: 0.99999 

Con tan sólo 38 artículos, es probable que una colisión. Con 148 artículos, hay un 99.999% de posibilidades de (al menos una) colisión. Con 148 artículos, cada artículo tiene un 7% de probabilidad de colisionar con otro artículo. Con una función de hash adecuada, tomando conocimiento del dominio, estos números podrían bajar fácilmente a 0.

En otras palabras, conocer su dominio y cómo suceden las cosas en la práctica son la clave para hacer un hash de ejecución.Las funciones de la biblioteca intentan hacer el mejor trabajo posible sin saber nada sobre su dominio y, para ser eficaces, suelen confiar en una distribución de datos que no se realizará en la práctica.

Answer 6

Java 8 agrega Long.hashCode(long) al JDK.

El siguiente código podría producir un mayor rendimiento. Este código reduce el cálculo a 32 bits int en lugar de calcular con 64-bit long. Esto puede hacer una diferencia en arquitecturas de 32 bits y más pequeñas. Los procesos de 32 bits en máquinas x86 podrían optimizar esto en una única instrucción que simplemente registra XORs 2.

return (int)(value^(value >>> 32));

Como se ha señalado en otras respuestas, esto hace no tienen una buenaavalanche effect y por lo tanto podría dar lugar a colisiones. Uno podría ir con funciones hash criptográficas para garantizar un efecto de avalancha alto. Sin embargo, hay otros algoritmos como Murmur Hash (más information) que tienen un efecto de avalancha muy bueno pero no consumen tanto tiempo de CPU.