java - name - ¿Por qué el método get de HashMap tiene un bucle FOR?

map string object get value

Question

Estoy viendo el código fuente de HashMap en Java 7, y veo que el método put comprueba si alguna entrada ya está presente y si está presente, entonces reemplazará el valor antiguo con el nuevo valor.

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

Entonces, básicamente, significa que siempre habrá una sola entrada para la clave dada, también lo he visto mediante la depuración, pero si estoy equivocado, corríjame.

Ahora, ya que solo hay una entrada para una clave dada, ¿por qué el método get tiene un bucle FOR, ya que simplemente podría haber devuelto el valor directamente?

    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }

Siento que el bucle anterior es innecesario. Por favor ayúdame a entender si estoy equivocado.

Answer 1

Creo que @Eran ya ha respondido bien a su consulta y @Prashant también ha hecho un buen intento junto con otras personas que han respondido, así que permítame explicarlo con un ejemplo para que el concepto sea muy claro .

Conceptos

Básicamente, lo que @Eran está tratando de decir que en un grupo dado (básicamente en un índice dado de la matriz) es posible que haya más de una entrada (nada más que un objeto de Entry ) y esto es posible cuando 2 o más teclas dan un hash diferente pero da la misma ubicación índice / cubo.

Ahora, para colocar la entrada en el mapa hash, esto es lo que sucede a un nivel alto (léalo detenidamente porque he ido más allá para explicar algunas cosas buenas que de otra manera no son parte de su pregunta ):

• Obtenga el hash: lo que sucede aquí es que el primer hash se calcula para una clave dada (observe que esto no es un hashCode , un hash se calcula utilizando el hashCode y se hace como para mitigar el riesgo de una función hash mal escrita).
• Obtenga el índice: este es básicamente el índice de la matriz o, en otras palabras, de un grupo. Ahora, el motivo por el que se calcula este índice en lugar de utilizar directamente el hash como índice es porque para mitigar el riesgo de que el hash pueda ser mayor que el tamaño del hashmap, este paso del cálculo del índice garantiza que el índice siempre será menor que el tamaño del hashmap. hashmap.

Y cuando ocurre una situación cuando 2 teclas dan un hash diferente pero el mismo índice, entonces ambas irán en el mismo grupo, y esa es la razón por la que el ciclo FOR es importante.

Ejemplo

A continuación se muestra un ejemplo simple que he creado para mostrarle el concepto:

public class Person {
    private int id;

    Person(int _id){
        id = _id;
    }

    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return id;
    }
}

Clase de prueba

import java.util.Map;

public class HashMapHashingTest {
    public static void main(String[] args) {
        Person p1 = new Person(129);
        Person p2 = new Person(133);

        Map<Person, String> hashMap = new MyHashMap<>(2);
        hashMap.put(p1, "p1");
        hashMap.put(p2, "p2");
        System.out.println(hashMap);
    }
}

Captura de pantalla de depuración (haga clic y amplíe porque se ve pequeño):

Tenga en cuenta que en el ejemplo anterior, ambos objetos Person dan un valor de hash diferente (136 y 140 respectivamente) pero dan el mismo índice de 0, por lo que ambos objetos van en el mismo grupo. En la captura de pantalla, puede ver que ambos objetos están en el índice 0 y allí también se ha completado un next que básicamente apunta al segundo objeto.

Actualización: otra forma más fácil de ver que más de una clave está ingresando en el mismo grupo es creando una clase y anulando el método hashCode para devolver siempre el mismo valor int. Ahora, lo que sucedería es que todos los objetos de esa clase darían la misma ubicación de índice / grupo, pero como no ha anulado el método de equals , no se considerarán iguales y, por lo tanto, formarán una lista en esa ubicación de índice / grupo.

Otro giro en esto supondría que también anula el método igual y compara todos los objetos iguales, entonces solo habrá un objeto presente en la ubicación del índice / cubo porque todos los objetos son iguales.

Answer 2

Las tablas de hash tienen cubos porque los hashes de objetos no tienen que ser únicos. Si hashes de objetos son iguales, significa, objetos, probablemente, son iguales. Si los hashes de los objetos son diferentes, entonces los objetos son exactamente diferentes. Por lo tanto, los objetos con los mismos hashes se agrupan en cubos. El bucle for se utiliza para iterar los objetos contenidos en dicho grupo.

De hecho, esto significa que la complejidad algorítmica de encontrar un objeto en una tabla hash de este tipo no es constante (aunque está muy cerca), sino algo entre logarítmico y lineal.

Answer 3

Me gustaría ponerlo en palabras simples. el método put tiene un bucle FOR para iterar sobre la lista de claves que cae bajo el mismo cubo de código hash.

¿Qué sucede cuando put el par key-value en el hashmap:

1. Entonces, por cada key que pase al HashMap , calculará el código hash para ello.
2. Tantas keys pueden caer en el mismo cubo de hashCode . Ahora HashMap comprobará si la misma key ya está presente o no en el mismo cubo.
3. En Java 7, HashMap mantiene todas las claves del mismo grupo en una lista. Entonces, antes de insertar la clave, se desplazará por la lista para verificar si la misma clave está presente o no. Es por eso que hay un bucle FOR.

Entonces, en el caso promedio su complejidad de tiempo: O(1) y en el peor de los casos su complejidad de tiempo es O(N) .

Answer 4

Mientras que las otras respuestas explican lo que está sucediendo, los comentarios de OP sobre esas respuestas me llevan a pensar que se requiere un ángulo diferente de explicación.

Ejemplo simplificado

Digamos que vas a tirar 10 cuerdas en un mapa hash: "A", "B", "C", "Hola", "Bye", "Yo", "Yo-yo", "Z", "1 "," 2 "

Está utilizando HashMap como su mapa hash en lugar de hacer su propio mapa hash (buena elección). Algunas de las cosas a continuación no utilizarán la implementación de HashMap directamente, sino que la abordarán desde un punto de vista más teórico y abstracto.

HashMap no sabe mágicamente que vas a agregarle 10 cadenas, ni tampoco sabe qué cadenas pondrás en él más adelante. Tiene que proporcionar lugares para poner lo que puedas darle ... por lo que sabe, vas a poner 100,000 cuerdas, tal vez cada palabra en el diccionario.

Digamos que, debido al argumento de constructor que eligió al crear su new HashMap(n) su mapa hash tiene 20 depósitos . Los llamaremos bucket[0] través de bucket[19] .

1. map.put("A", value); Digamos que el valor de hash para "A" es 5. El mapa de hash ahora puede hacer bucket[5] = new Entry("A", value);

2. map.put("B", value); Supongamos que hash ("B") = 3. Entonces, bucket[3] = new Entry("B", value);

3. map.put("C"), value); - hash ("C") = 19 - bucket[19] = new Entry("C", value);

4. map.put("Hi", value); Ahora aquí es donde se pone interesante. Digamos que su función hash es tal que hash ("Hola") = 3. Así que ahora el mapa hash quiere hacer bucket[3] = new Entry("Hi", value); ¡Tenemos un problema! bucket[3] es donde colocamos la clave "B", y "Hola" es definitivamente una clave diferente a "B" ... pero tienen el mismo valor de hash . ¡Tenemos una colisión !

Debido a esta posibilidad, el HashMap no se implementa de esta manera. Un mapa hash debe tener cubos que puedan contener más de 1 entrada. NOTA: No dije más de 1 entrada con la misma clave , ya que no podemos tener eso , pero debe tener grupos que puedan contener más de 1 entrada de claves diferentes . Necesitamos un cubo que pueda contener tanto "B" como "Hola".

Así que no hagamos bucket[n] = new Entry(key, value); , pero en vez de eso, hagamos que el bucket sea ​​del tipo Bucket[] lugar de Entry[] . Así que ahora hacemos bucket[n].add( new Entry(key, value) );

Así que vamos a cambiar a ...

bucket[3].add("B", value);

y

bucket[3].add("Hi", value);

Como puede ver, ahora tenemos las entradas para "B" y "Hola" en el mismo grupo . Ahora, cuando queremos volver a sacarlos, necesitamos recorrer todo lo que hay en el cubo, por ejemplo, con un bucle for .

Así que el bucle está presente debido a las colisiones . No colisiones de key , sino colisiones de hash(key) .

¿Por qué usamos una estructura de datos tan loca?

Es posible que se esté preguntando en este punto, "¡Espere, ¿QUÉ? ¿Por qué haríamos una cosa tan extraña como esa? ¿Por qué estamos utilizando una estructura de datos tan artificial y complicada?" La respuesta a esa pregunta sería ...

Un mapa hash funciona así debido a las propiedades que nos brinda una configuración tan peculiar debido a la forma en que funcionan las matemáticas. Si usa una buena función de hash que minimiza los conflictos, y si dimensiona su HashMap para tener más depósitos que el número de entradas que cree que tendrá, entonces tiene un mapa de hash optimizado que será la estructura de datos más rápida para las inserciones. y consultas de datos complejos.

Tu HashMap puede ser demasiado pequeño

Ya que dice que a menudo ve que este bucle for se repite con múltiples elementos en su depuración, eso significa que su HashMap puede ser demasiado pequeño. Si tiene una idea razonable de cuántas cosas podría poner en él, intente establecer el tamaño para que sea más grande que eso. Observe en mi ejemplo anterior que estaba insertando 10 cadenas, pero tenía un mapa hash con 20 cubos. Con una buena función hash, esto producirá muy pocas colisiones.

Nota:

Nota: el ejemplo anterior es una simplificación del asunto y requiere algunos atajos para abreviar. Una explicación completa es incluso un poco más complicada, pero aquí encontrará todo lo que necesita saber para responder la pregunta.

Answer 5

Para el registro, en java-8, esto también está presente (más o menos, ya que también hay TreeNode s):

if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }

Básicamente (en el caso de que el contenedor no sea un Tree ), repita la iteración completa hasta que encuentre la entrada que estamos buscando.

Al observar esta implementación, es posible que comprenda por qué es bueno proporcionar un buen hash, de modo que no todas las entradas terminan en el mismo grupo, por lo que es un momento más importante para buscarlo.

Answer 6

Si ves el funcionamiento interno del método get de HashMap.

public V get(Object key)  {
        if (key == null)
           return getForNullKey();
         int hash = hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
         {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                 return e.value;
         }
             return null;
}

• Primero, obtiene el código hash del objeto clave, que se pasa, y encuentra la ubicación del depósito.
• Si se encuentra el grupo correcto, devuelve el valor (valor e)
• Si no se encuentra ninguna coincidencia, devuelve nulo.

Algunas veces puede haber posibilidades de colisión con Hashcode y para resolver esta colisión, Hashmap usa equals () y luego almacena ese elemento en LinkedList en el mismo grupo.

Tomemos ejemplo:

Obtenga los datos para la clave vaibahv: map.get (nueva clave ("vaibhav"));

Pasos:

1. Calcule el código hash de la Clave {"vaibhav"}. Se generará como 118.

2. Calcular el índice utilizando el método de índice será 6.

3. Vaya al índice 6 de la matriz y compare la clave del primer elemento con la clave dada. Si ambos son iguales, devuelva el valor; de lo contrario, compruebe el elemento siguiente si existe.

4. En nuestro caso, no se encuentra como primer elemento y el siguiente objeto de nodo no es nulo.

5. Si next of node es nulo, devuelve nulo.

6. Si next of node no está nulo a través del segundo elemento y repita el proceso 3 hasta que no se encuentre la clave o la siguiente no sea null.

Para este proceso de recuperación se utilizará el bucle. Para mas referencia puedes consultar this

Answer 7

table[indexFor(hash, table.length)] es el grupo de HashMap que puede contener la clave que estamos buscando (si está presente en el Map ).

Sin embargo, cada grupo puede contener varias entradas (ya sea claves diferentes que tienen el mismo hashCode() , o teclas diferentes con hashCode() diferente hashCode() que aún se asignaron al mismo grupo), por lo que debe recorrer estas entradas hasta que encuentre la clave estan buscando.

Dado que el número esperado de entradas en cada grupo debería ser muy pequeño, este bucle todavía se ejecuta en el tiempo O(1) esperado.