java - para - dos objetos desiguales con el mismo hashcode

override hashcode java

Question

El concepto Hashcode () y equals () es

1) Si dos Objetos son iguales de acuerdo con igual (), entonces llamar al método de código de hash en cada uno de esos dos objetos debería producir el mismo código de hash.

y otro es

2) No es necesario que si dos objetos son desiguales de acuerdo con el igual (), llamar al método de código hash en cada uno de los dos objetos debe producir valores distintos.

Intenté y entendí primero y este es el código para el primer punto.

public class Test {
    public static void main(String[] args) {

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(1, 11);
        map.put(4, 11);
        System.out.println(map.hashCode());
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        map1.put(1, 11);
        map1.put(4, 11);
        System.out.println(map1.hashCode());
        if (map.equals(map1)) {
            System.out.println("equal ");
        }
    }
}

el programa anterior proporciona el mismo código hash para dos objetos diferentes.

¿Puede alguien explicarme con un ejemplo, cómo dos objetos diferentes que son desiguales de acuerdo con los iguales () tienen el mismo código hash?

Answer 1

2) No es necesario que si dos objetos son desiguales de acuerdo con el igual (), llamar al método de código hash en cada uno de los dos objetos debe producir valores distintos.

Dependiendo de la función hash, 2 objetos diferentes pueden tener el mismo código hash. Sin embargo, 2 objetos que son iguales deben producir el mismo resultado cuando se usan hash (a menos que alguien implemente una función hash con números aleatorios, en cuyo caso es inútil)

Por ejemplo, si estoy mezclando números enteros y mi función de hash es simplemente (n % 10) entonces el número 17 y el número 27 producirán el mismo resultado. Esto no significa que esos números sean iguales.

Answer 2

Es bastante simple en realidad,

Primero tenemos que saber qué es un código hash.

En Java, un código hash es simple un entero de 32 bits con signo que de alguna manera se deriva de los datos en cuestión. Los tipos enteros generalmente son solo (Datos Int) Mod (algún número primo grande razonable).

Hagamos un hash simple en enteros.
Definir:

public int hash(int num){ return num % 19 ; } 

En este caso, tanto 19 como 38 devolverán el valor hash de 0.

Para los tipos de cadena, el hash se deriva de los caracteres individuales y la posición de cada uno en la cadena, dividida por un número razonablemente grande. (O, en el caso de Java, ignorar el desbordamiento en una suma de 32 bits).

Dado que hay arbitrariamente muchas cadenas posibles, y hay una cantidad limitada de códigos hash (2 ^ 32) para una cadena, el principio del casillero establece que hay al menos dos cadenas diferentes que dan como resultado el mismo código hash.

Answer 3

Mi entendimiento es que hashCode es una representación numérica de la dirección de memoria, pero no es la dirección real. Se puede cambiar, sin afectar la dirección real. Por lo tanto, debería ser posible establecer todos los objetos en el mismo código hash, incluso si son todos elementos completamente diferentes. Piensa en todos los integrantes de un solo bloque que repentinamente tienen la misma dirección. Son personas realmente diferentes, pero ahora todos comparten la misma dirección. Su casa no se movió, un adolescente travieso acaba de etiquetar a todos como "100 N. Main".

Soy bastante nuevo en Java, así que toma mi respuesta con un poco de precaución.

Answer 4

hashCode () tiene valores posibles de 32 bits. Tus objetos pueden tener mucho más que esto, así que tendrás algunos objetos con el mismo hashCode, es decir, no puedes asegurar que sean únicos.

Esto empeora en una colección hash de tamaño limitado. La capacidad máxima de HashMap es 1 << 30 o aproximadamente mil millones. Esto significa que solo se usan realmente 30 bits y si su colección no usa 16+ GB y solo dice mil cubos (o 1 << 10 técnicamente), entonces realmente solo tiene 1000 cubos posibles.

Nota: en HotSpot JVM, el Object.hashCode () predeterminado nunca es negativo, es decir, solo de 31 bits, aunque no estoy seguro de por qué.

Si desea generar muchos objetos con el mismo hashCode, mire Long.

// from Long
public int hashCode() {
    return (int)(value ^ (value >>> 32));
}

for(long i = Integer.MIN_VALUE; i < Integer.MAX_VALUE;i++) {
    Long l = (i << 32) + i;
    System.out.print(l.hashCode()+" ");
    if (i % 100 == 0)
        System.out.println();
}

Esto generará 4 billones de Long. Todo con un hashCode de 0.

Answer 5

El objetivo de hashCode es habilitar el siguiente axioma y corolario:

• Si uno conoce los códigos hash de dos objetos, y esos códigos hash no coinciden, uno no necesita molestarse en examinar los objetos para saber que los objetos no coincidirán. Incluso si dos objetos no coincidentes elegidos arbitrariamente tuvieran un 10% de probabilidades de tener códigos hash coincidentes, la prueba de códigos hash permitiría eliminar el 90% de las comparaciones que uno necesitaría. No es una victoria tan grande como eliminar el 99.99%, pero definitivamente vale la pena.

• El conocimiento de que ninguno de los objetos en un grupo tiene un código hash particular implica que ninguno de los objetos en ese grupo coincidirá con un objeto con ese código hash. Si uno dividía una colección de objetos en aquellos cuyo código hash era un número par y aquellos cuyo hash era impar, y uno quería saber si uno tenía un elemento determinado cuyo código hash era par, no habría necesidad de examinar nada. en la colección de elementos de hash impar. Del mismo modo, no habría necesidad de buscar un elemento de hash extraño en la colección de hash par. Incluso un hash de dos valores podría acelerar las búsquedas en casi la mitad. Si uno divide una colección en particiones más pequeñas, uno puede acelerar aún más las cosas.

Tenga en cuenta que hashCode() ofrecerá el mayor beneficio si cada elemento diferente devuelve un hash diferente, pero puede ofrecer un beneficio sustancial incluso cuando muchos artículos tienen el mismo valor hash. La diferencia entre un ahorro del 90% y un ahorro del 99,99% es a menudo mucho mayor de lo que sugieren los números, y por lo tanto uno, si uno puede mejorar razonablemente fácilmente las cosas al 99%, 99,9% o mejor, debería hacerlo, pero la diferencia entre tener cero coincidencias falsas y tener algunas coincidencias falsas en una colección es bastante leve.

Answer 6

Es bastante simple de entender si sabes cómo se implementa un HashMap y su propósito. Un Hashmap toma un gran conjunto de valores y los divide en conjuntos mucho más pequeños (cubos) para una recuperación mucho más rápida de los elementos. Básicamente, solo necesita buscar un cubo en lugar de la lista completa de su elemento. Los cubos están en una matriz donde el índice es el código hash. Cada segmento contiene una lista vinculada de elementos con el mismo código hash, pero no son iguales (). Creo que en Java 8 cambiaron a usar un mapa de árbol cuando el tamaño del cubo se vuelve grande.

Answer 7

Actullay, este enlace explica qué pasa si hashcode es más claro.

http://www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html

Answer 8

Ejemplo con cadenas (todas las cadenas a continuación tienen un código de hash de 0):

public static void main(String[] args) {
    List<String> list = Arrays.asList("pollinating sandboxes",
                                      "amusement & hemophilias",
                                      "schoolworks = perversive",
                                      "electrolysissweeteners.net",
                                      "constitutionalunstableness.net",
                                      "grinnerslaphappier.org",
                                      "BLEACHINGFEMININELY.NET",
                                      "WWW.BUMRACEGOERS.ORG",
                                      "WWW.RACCOONPRUDENTIALS.NET",
                                      "Microcomputers: the unredeemed lollipop...",
                                      "Incentively, my dear, I don''t tessellate a derangement.",
                                      "A person who never yodelled an apology, never preened vocalizing transsexuals.");
    for (String s : list) {
        System.out.println(s.hashCode());
    }
}

(robado de esta publicación ).