Sumário
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
Top comments (1)
Muito interessante o jeito que é tratado em caso de colisão! Parabéns pelo artigo 👏