Uma breve introdução à HashMap

Sumário HashMap Hash Function Load Factor Collisions Relacionando tudo e aprendendo sobre Open addressing e Separate chaining HashMap Um HashMap é uma estrutura de dados que faz parte da biblioteca de coleções em muitas linguagens de programação. Ele é utilizado para armazenar pares de chave-valor. Hash Function Função responsável por transformar um input em um índice do array, o retorno de um Hash Function é chamado de Hash Value ou simplesmente Hash. Um Hash Function é implementado usando criptografia como SHA-256, MD5 para ser consistente e minimizar duplicações de índices como veremos mais a frente. Load Factor Load Factor representa a quantidade que o array esta preenchido, por exemplo, um array que armazena 10 itens e nele ja existem 2 itens armazenados, significa que temos 20%(0.2%) do array preenchido. Collisions Quando uma Hash Function produz um hash que já existe como posição, é causado uma collision pois estamos tentando armazenar um valor em uma posição que já tem outro valor armazenado. Relacionando tudo e aprendendo sobre Open addressing e Separate chaining Quando o Load Factor atinge 0.7% ou 0.8% (ou seja, quando nosso array está 70% ou 80% preenchido), o HashMap aciona uma função para dobrar o tamanho do array para reduzir a probabilidade de colisão, e recalcular as posições dos elementos. No entanto, isso é muito custoso mas acontece algumas vezes. Ao tentar realizar uma inserção em um HashMap e acontecer uma colisão, existem duas abordagens de implementação: Open addressing: busca-se a próxima posição disponível, o que torna a inserção O(n). Separate chaining -> os elementos são armazenados em uma estrutura encadeada, geralmente uma lista ligada ou, em algumas implementações uma árvore balanceada, tornando a inserção O(1). A intenção é que essa lista seja pequena, devido à baixa probabilidade de colisão quando a função hash é bem implementada. O artigo foi baseado no curso "Estruturas de Dados e Algoritmos" do Augusto Galego, se curtiu o artigo e gostaria de aprender mais sobre o tema do curso utilize o meu link, irá ajudar bastante! https://pay.hub.la/L8wi9vio7WPnWbmF8ZIO?ref=soIMpTHnaaX7oPqRCHak

Feb 2, 2025 - 21:22

Sumário

HashMap
- Hash Function
- Load Factor
- Collisions
- Relacionando tudo e aprendendo sobre Open addressing e Separate chaining

HashMap

Um HashMap é uma estrutura de dados que faz parte da biblioteca de coleções em muitas linguagens de programação.
Ele é utilizado para armazenar pares de chave-valor.

Hash Function

Função responsável por transformar um input em um índice do array, o retorno de um Hash Function é chamado de Hash Value ou simplesmente Hash.
Um Hash Function é implementado usando criptografia como SHA-256, MD5 para ser consistente e minimizar duplicações de índices como veremos mais a frente.

Load Factor

Load Factor representa a quantidade que o array esta preenchido, por exemplo, um array que armazena 10 itens e nele ja existem 2 itens armazenados, significa que temos 20%(0.2%) do array preenchido.

Collisions

Quando uma Hash Function produz um hash que já existe como posição, é causado uma collision pois estamos tentando armazenar um valor em uma posição que já tem outro valor armazenado.

Relacionando tudo e aprendendo sobre Open addressing e Separate chaining

Quando o Load Factor atinge 0.7% ou 0.8% (ou seja, quando nosso array está 70% ou 80% preenchido), o HashMap aciona uma função para dobrar o tamanho do array para reduzir a probabilidade de colisão, e recalcular as posições dos elementos. No entanto, isso é muito custoso mas acontece algumas vezes.

Ao tentar realizar uma inserção em um HashMap e acontecer uma colisão, existem duas abordagens de implementação:

Open addressing: busca-se a próxima posição disponível, o que torna a inserção O(n).

Separate chaining -> os elementos são armazenados em uma estrutura encadeada, geralmente uma lista ligada ou, em algumas implementações uma árvore balanceada, tornando a inserção O(1). A intenção é que essa lista seja pequena, devido à baixa probabilidade de colisão quando a função hash é bem implementada.

O artigo foi baseado no curso "Estruturas de Dados e Algoritmos" do Augusto Galego, se curtiu o artigo e gostaria de aprender mais sobre o tema do curso utilize o meu link, irá ajudar bastante!
https://pay.hub.la/L8wi9vio7WPnWbmF8ZIO?ref=soIMpTHnaaX7oPqRCHak