Deslize para mostrar o menu

Agora, vamos analisar mais de perto a classe que implementa a interface Map — HashMap.

Esta classe é comumente utilizada quando falamos sobre mapas. Você já teve a oportunidade de trabalhar com esta classe e estudar seus métodos. Mas vamos descobrir como esta classe realmente funciona.

Primeiro, é necessário entender o que é um hash code, pois ele é utilizado internamente em um HashMap.

Hash Code

Todo objeto possui seu próprio hash code, que pode ser obtido utilizando o método Object da classe hashCode(). Veja um exemplo:

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 pode ser observado, o objeto String com o dado "Hello World!" possui um hash code de "-969099747". O método que determina exatamente qual hash code será sobrescrito na classe String é o seguinte:

Main.java


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

O objeto String é dividido em um array de bytes usando o método getBytes(), após o qual cada byte é processado e adicionado ao hash code. Dessa forma, o hash code torna-se maximamente único, auxiliando o programa a identificar esse objeto.

Para objetos de classes personalizadas, também é possível sobrescrever o hash code definindo uma maneira única para os objetos obterem esse número. Vamos criar uma classe de teste User e sobrescrever o método hash code para ela.

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());
    }
}

Na classe User, existem 2 atributos que utilizei no método hashCode(). Escolhi operações aleatórias no método hashCode() para obter um número maximamente aleatório, tornando-o único para cada objeto User.

Este é precisamente o hash code. Agora, vamos descobrir como ele é utilizado em um HashMap.

HashMap

Um HashMap pode ser visualizado como um array de buckets. Um bucket é uma lista onde um elemento é armazenado. Inicialmente, o HashMap possui 16 buckets, que é o DEFAULT_INITIAL_CAPACITY.

Quando um elemento é inserido no HashMap utilizando o método put(), o HashMap precisa determinar em qual bucket específico esse elemento será colocado. Isso é feito utilizando a seguinte fórmula: keyValue.hashCode() & (n - 1), onde n é o tamanho do array de buckets no HashMap. '&' é uma operação bitwise AND, que é uma operação de baixo nível, portanto não entraremos em detalhes.

É importante compreender que o HashMap utiliza o hash code do valor da chave para encontrar o bucket apropriado para ela. Por isso, é fundamental criar um hash code o mais único possível para evitar colisões.

Colisão

Não importa o quão único seja um hash code, ainda pode ocorrer uma situação em que o HashMap calcula o mesmo bucket para dois elementos. Nesses casos, ocorre uma colisão. De forma simples, uma colisão é uma situação em que dois ou mais elementos acabam no mesmo bucket. Eles são armazenados ali como um SinglyLinkedList, que você implementou anteriormente.

Veja a ilustração a seguir:

Colisão não é desejável, pois afeta a otimização. Se você observar esta tabela, verá que, no melhor caso, o HashMap possui complexidade algorítmica constante, enquanto no pior caso, ela é linear. Essa complexidade algorítmica linear ocorre devido a colisões significativas. Por isso, recomenda-se utilizar chaves com hash codes o mais únicos possível para evitar colisões.

Como o HashMap Lida com Colisões?

O HashMap também trata colisões por meio do redimensionamento constante do array de buckets. Quando o número de elementos atinge 75% do tamanho do array de buckets, o HashMap dispara um redimensionamento ao dobrar o tamanho do array de buckets. Em seguida, ele redistribui os elementos entre os novos buckets utilizando o novo valor de n na fórmula.

Assim, o HashMap é uma estrutura de dados altamente otimizada e frequentemente utilizada como a principal implementação da interface Map.

1. Qual das seguintes implementações utiliza uma tabela hash para armazenar pares chave-valor?

2. Em um `HashMap`, o que acontece se duas chaves tiverem o mesmo código hash?

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 1. Capítulo 14

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Seção 1. Capítulo 14

Trabalhando com HashMap em Java

Hash Code

HashMap

Colisão

Como o HashMap Lida com Colisões?

1. Qual das seguintes implementações utiliza uma tabela hash para armazenar pares chave-valor?

2. Em um HashMap, o que acontece se duas chaves tiverem o mesmo código hash?

2. Em um `HashMap`, o que acontece se duas chaves tiverem o mesmo código hash?