Desliza para mostrar el menú

Ahora, analicemos más de cerca la clase que implementa la interfaz Map — HashMap.

Esta clase es comúnmente utilizada cuando hablamos de mapas. Ya has tenido la oportunidad de trabajar con esta clase y estudiar sus métodos. Pero descubramos cómo funciona realmente esta clase.

Primero, es necesario comprender qué es un código hash, ya que se utiliza internamente en un HashMap.

Código Hash

Cada objeto tiene su propio código hash, que se puede obtener utilizando el método Object de la clase hashCode(). Veamos un ejemplo:

Main.java


              123456789
            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Como se puede observar, el objeto String con el dato "Hello World!" tiene un código hash de "-969099747". El método que determina exactamente qué código hash se sobrescribirá en la clase String es el siguiente:

Main.java


              1234567
            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

El objeto String se descompone en un arreglo de bytes utilizando el método getBytes(), tras lo cual cada byte es procesado y añadido al código hash. De este modo, el código hash se vuelve máximamente único, lo que ayuda al programa a identificar este objeto.

Para objetos de clases personalizadas, también se puede sobrescribir el código hash definiendo una forma única para que los objetos obtengan este número. Vamos a crear una clase de prueba User y sobrescribir el método de código hash para ella.

Main.java


              12345678910111213141516171819202122232425262728293031
            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

En la clase User, hay 2 atributos que utilicé en el método hashCode(). Elegí operaciones aleatorias en el método hashCode() para obtener un número lo más aleatorio posible, haciéndolo único para cada objeto User.

Esto es precisamente el código hash. Ahora, veamos cómo se utiliza en un HashMap.

HashMap

Un HashMap en sí puede visualizarse como un arreglo de cubetas. Una cubeta es una lista donde se almacena un elemento. Inicialmente, el HashMap tiene 16 cubetas, que es el DEFAULT_INITIAL_CAPACITY.

Cuando se inserta un elemento en el HashMap utilizando el método put(), el HashMap necesita determinar en qué cubeta específica colocar este elemento. Lo hace utilizando una fórmula simple: keyValue.hashCode() & (n - 1), donde n es el tamaño del arreglo de cubetas en el HashMap. '&' es una operación bit a bit AND, que también es programación de bajo nivel, por lo que no profundizaremos en los detalles.

Es importante comprender que el HashMap utiliza el código hash del valor de la clave para encontrar la cubeta apropiada para ella. Por lo tanto, es fundamental crear un código hash lo más único posible para evitar colisiones.

Colisión

No importa cuán único sea un código hash, aún puede darse la situación en la que el HashMap calcule la misma cubeta para dos elementos. En tales casos, ocurre una colisión. En términos simples, una colisión es una situación en la que dos o más elementos terminan en la misma cubeta. Se almacenan allí como un SinglyLinkedList, que implementaste anteriormente.

Veamos una ilustración:

La colisión no es favorable ya que afecta la optimización. Si observas esta tabla, verás que en el mejor de los casos, el HashMap tiene complejidad algorítmica constante, mientras que en el peor de los casos, es lineal. Esta complejidad algorítmica lineal surge de colisiones significativas. Por lo tanto, se recomienda utilizar claves con códigos hash lo más únicos posible para evitar colisiones.

¿Cómo maneja HashMap las colisiones?

HashMap también resuelve las colisiones mediante el redimensionamiento constante del arreglo de buckets. Cuando el número de elementos alcanza el 75% del tamaño del arreglo de buckets, HashMap inicia un redimensionamiento duplicando el tamaño del arreglo de buckets. Posteriormente, redistribuye los elementos entre los nuevos buckets utilizando el nuevo valor de n en la fórmula.

Por lo tanto, HashMap es una estructura de datos altamente optimizada y suele utilizarse como la implementación principal de la interfaz Map.

1. ¿Cuál de las siguientes implementaciones utiliza una tabla hash para almacenar pares clave-valor?

2. En un `HashMap`, ¿qué sucede si dos claves tienen el mismo código hash?

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 1. Capítulo 14

Pregunte a AI

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Sección 1. Capítulo 14

Trabajando con HashMap en Java

Código Hash

HashMap

Colisión

¿Cómo maneja HashMap las colisiones?

1. ¿Cuál de las siguientes implementaciones utiliza una tabla hash para almacenar pares clave-valor?

2. En un HashMap, ¿qué sucede si dos claves tienen el mismo código hash?

2. En un `HashMap`, ¿qué sucede si dos claves tienen el mismo código hash?