DEV Community

Cover image for Uma breve introdução à HashMap
Patrícia Clares
Patrícia Clares

Posted on

2 2

Uma breve introdução à HashMap

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:

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

Open addressing

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

Separate chaining


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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (1)

Collapse
 
gabriel_vacari_f7c311ddbe profile image
Gabriel Vacari

Muito interessante o jeito que é tratado em caso de colisão! Parabéns pelo artigo 👏

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up