Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Aprenda Trabalhando com HashMap em Java | Dominando Map em Java
Learn
Cursos
Learning Tracks
Popular Topics
Practice
Projects
Quizzes & Challenges
Quizzes
Challenges
/
Estruturas de Dados em Java

bookTrabalhando com HashMap em Java

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

Esta classe é amplamente 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 compreender 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

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 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

Main.java

copy

              
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

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

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.

Ao inserir um elemento no HashMap usando o método put(), o HashMap precisa determinar em qual bucket específico colocar esse elemento. Ele faz isso utilizando uma fórmula simples: keyValue.hashCode() & (n - 1), onde n é o tamanho do array de buckets no HashMap. '&' é uma operação de AND bit a bit, que é uma técnica de programaçã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. Portanto, é 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. Em termos 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 surge devido a colisões significativas. Portanto, 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.

Por Que Você Precisa Saber Tudo Isso?

Esta é uma teoria de programação de baixo nível que é importante porque, ao trabalhar com grandes volumes de dados, as estruturas de dados podem impactar significativamente o desempenho da aplicação. Isso ocorre quando essas estruturas de dados são mal utilizadas.

O uso inadequado das estruturas de dados acontece porque programadores não entendem como essas estruturas funcionam. Afinal, você quer se tornar um bom programador, certo?

Além disso, perguntas sobre estruturas de dados são frequentemente feitas em entrevistas.

Se tiver interesse em se aprofundar em como o HashMap funciona internamente, consulte a documentação Java no IntelliJ IDEA.

No IntelliJ IDEA, mantenha pressionado Ctrl (Windows/Linux) ou Command (macOS) e clique no nome da classe para navegar até sua definição e ver todos os métodos disponíveis.

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?

question mark

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

Select the correct answer

question mark

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

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 2

Pergunte à IA

expand

Pergunte à IA

ChatGPT

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

bookTrabalhando com HashMap em Java

Deslize para mostrar o menu

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

Esta classe é amplamente 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 compreender 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

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 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

Main.java

copy

              
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

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

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.

Ao inserir um elemento no HashMap usando o método put(), o HashMap precisa determinar em qual bucket específico colocar esse elemento. Ele faz isso utilizando uma fórmula simples: keyValue.hashCode() & (n - 1), onde n é o tamanho do array de buckets no HashMap. '&' é uma operação de AND bit a bit, que é uma técnica de programaçã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. Portanto, é 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. Em termos 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 surge devido a colisões significativas. Portanto, 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.

Por Que Você Precisa Saber Tudo Isso?

Esta é uma teoria de programação de baixo nível que é importante porque, ao trabalhar com grandes volumes de dados, as estruturas de dados podem impactar significativamente o desempenho da aplicação. Isso ocorre quando essas estruturas de dados são mal utilizadas.

O uso inadequado das estruturas de dados acontece porque programadores não entendem como essas estruturas funcionam. Afinal, você quer se tornar um bom programador, certo?

Além disso, perguntas sobre estruturas de dados são frequentemente feitas em entrevistas.

Se tiver interesse em se aprofundar em como o HashMap funciona internamente, consulte a documentação Java no IntelliJ IDEA.

No IntelliJ IDEA, mantenha pressionado Ctrl (Windows/Linux) ou Command (macOS) e clique no nome da classe para navegar até sua definição e ver todos os métodos disponíveis.

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?

question mark

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

Select the correct answer

question mark

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

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 2
some-alt