Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Aprende Trabajando con HashMap en Java | Dominando Map en Java
Learn
Cursos
Learning Tracks
Popular Topics
Practice
Projects
Quizzes & Challenges
Quizzes
Challenges
/
Estructuras de Datos en Java

bookTrabajando con HashMap en Java

Ahora, examinemos más de cerca la clase que implementa la interfaz Map: HashMap.

Esta clase es utilizada comúnmente 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

Main.java

copy

              
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 será sobrescrito en la clase String es el siguiente:

Main.java

Main.java

copy

              
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(), después de lo cual cada byte es procesado y añadido al código hash. De esta manera, el código hash se vuelve máximamente único, ayudando 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 hash code para ella.

Main.java

Main.java

copy

              
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 usando 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 de AND a nivel de bits, que también es programación de bajo nivel, por lo que no profundizaremos en los detalles.

Es importante entender que el HashMap utiliza el código hash del valor de la clave para encontrar la cubeta adecuada 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.

¿Por qué es importante conocer esto?

Esto es teoría de programación de bajo nivel que resulta relevante porque, al trabajar con grandes volúmenes de datos, las estructuras de datos pueden impactar significativamente en el rendimiento de la aplicación. Esto ocurre cuando estas estructuras de datos se utilizan incorrectamente.

El mal uso de las estructuras de datos sucede porque los programadores no comprenden cómo funcionan estas estructuras. Después de todo, ¿quieres convertirte en un buen programador, verdad?

Además, las preguntas sobre estructuras de datos son frecuentes en entrevistas.

Si te interesa profundizar en cómo funciona HashMap internamente, puedes consultar la documentación de Java en IntelliJ IDEA.

En IntelliJ IDEA, mantén presionada la tecla Ctrl (Windows/Linux) o Command (macOS) y haz clic en el nombre de la clase para navegar a su definición y ver todos los métodos disponibles.

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?

question mark

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

Select the correct answer

question mark

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

Select the correct answer

¿Todo estuvo claro?

¿Cómo podemos mejorarlo?

¡Gracias por tus comentarios!

Sección 3. Capítulo 2

Pregunte a AI

expand

Pregunte a AI

ChatGPT

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

bookTrabajando con HashMap en Java

Desliza para mostrar el menú

Ahora, examinemos más de cerca la clase que implementa la interfaz Map: HashMap.

Esta clase es utilizada comúnmente 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

Main.java

copy

              
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 será sobrescrito en la clase String es el siguiente:

Main.java

Main.java

copy

              
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(), después de lo cual cada byte es procesado y añadido al código hash. De esta manera, el código hash se vuelve máximamente único, ayudando 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 hash code para ella.

Main.java

Main.java

copy

              
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 usando 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 de AND a nivel de bits, que también es programación de bajo nivel, por lo que no profundizaremos en los detalles.

Es importante entender que el HashMap utiliza el código hash del valor de la clave para encontrar la cubeta adecuada 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.

¿Por qué es importante conocer esto?

Esto es teoría de programación de bajo nivel que resulta relevante porque, al trabajar con grandes volúmenes de datos, las estructuras de datos pueden impactar significativamente en el rendimiento de la aplicación. Esto ocurre cuando estas estructuras de datos se utilizan incorrectamente.

El mal uso de las estructuras de datos sucede porque los programadores no comprenden cómo funcionan estas estructuras. Después de todo, ¿quieres convertirte en un buen programador, verdad?

Además, las preguntas sobre estructuras de datos son frecuentes en entrevistas.

Si te interesa profundizar en cómo funciona HashMap internamente, puedes consultar la documentación de Java en IntelliJ IDEA.

En IntelliJ IDEA, mantén presionada la tecla Ctrl (Windows/Linux) o Command (macOS) y haz clic en el nombre de la clase para navegar a su definición y ver todos los métodos disponibles.

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?

question mark

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

Select the correct answer

question mark

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

Select the correct answer

¿Todo estuvo claro?

¿Cómo podemos mejorarlo?

¡Gracias por tus comentarios!

Sección 3. Capítulo 2
some-alt