Java Map :: HashCode () Collision - ¿Por qué?

Question

El siguiente código da como resultado que se genere el mismo código hash para los dos mapas, ¿alguna idea?

import java.util.HashMap;
import java.util.Map;

public class Foo
{
    @SuppressWarnings("unchecked")
    public static void main (String[] args)
    {
        Map map;

        map = new HashMap();

        map.put("campaignId", 4770L);
        map.put("location", "MINI_PROFILE");
        map.put("active", "true");
        map.put("lazy", true);

        System.out.println(map.hashCode());

        map = new HashMap();

        map.put("campaignId", 4936L);
        map.put("location", "MINI_PROFILE");
        map.put("active", "true");
        map.put("lazy", false);

        System.out.println(map.hashCode());


    }
}

El resultado es:

-1376467648
-1376467648

Simplemente cambiar los nombres clave es suficiente para que el código genere dos códigos hash diferentes.

Answer 1

Simplemente coincidencia, sospecho que ... hay vinculado Para ser colisiones, y en este caso parece que los diferentes bits relevantes en el primer valor se están perdiendo, de manera efectiva.

Sin embargo, no debería hacer ninguna diferencia: nada usando códigos hash deber hacer frente a las colisiones.

Editar: es la forma en que se calculan los hashes. Este código muestra lo que está pasando:

import java.util.*;

public class Test
{
    @SuppressWarnings("unchecked")
    public static void main (String[] args)
    {
        AbstractMap.SimpleEntry[] entries = {
            new AbstractMap.SimpleEntry("campaignId", 4770L),
            new AbstractMap.SimpleEntry("campaignId", 4936L),
            new AbstractMap.SimpleEntry("lazy", true),
            new AbstractMap.SimpleEntry("lazy", false)
        };
        for (AbstractMap.SimpleEntry entry : entries) {
            System.out.println(entry + ": " + entry.hashCode());
        }
    }
}

Resultados:

campaignId=4770: -1318251287
campaignId=4936: -1318251261
lazy=true: 3315643
lazy=false: 3315617

Entonces, en un par, el primer mapa tiene un hash 26 menos que el segundo mapa, y en otro par, el primer mapa tiene un hash 26 más que el segundo mapa.

AbstractMap Solo resume los valores de hash (una forma de asegurarse de que el pedido sea irrelevante), por lo que los dos terminan con el mismo código hash.

Realmente se debe a Boolean.hashCode() que se ve así:

return value ? 1231 : 1237;

... y Long.hashCode() que se ve así:

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

Dados los valores que eligieron Boolean.hashCode(), si tu long Los valores son solo 26 aparte (o 26 * 2^32 aparte), luego se encontrará con lo mismo.

Answer 2

Creo que esto es solo una coincidencia. Desde el javadoc para abstractMap#hashcode ():

El código hash de un mapa se define como la suma de los códigos hash de cada entrada en la vista Entrada () del mapa.

Y para la entrada#hashcode ():

Devuelve el valor del código hash para esta entrada de mapa. El código hash de una entrada de mapa se define como:

 (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
 (e.getValue()==null ? 0 : e.getValue().hashCode())

Por lo tanto, los códigos hash para mapas se basan tanto en las claves como en los valores contenidos en el mapa. Solo estás experimentando una situación extraña en la que dos mapas tienen el mismo código hash, sin razón aparente.

Answer 3

Collisions happen. In fact, you could override hashCode() to always return 0 for every HashMap and it would be correct (altough it would make a lot of structures slow).

Answer 4

It is not a coincident.

String objects are same in both. Same object will give same hashcode.