Como Construir um Hashmap

Esta semana, vamos mergulhar em uma das estruturas de dados mais poderosas e fundamentais da programação: o Hash Map, também chamado de Hash Table ou Dicionário. Hash maps são essenciais em praticamente toda linguagem para armazenar e recuperar dados rapidamente como pares chave-valor.

O que é, de fato, um Hash Map?

Um Hash Map é uma estrutura baseada em array que dá acesso quase instantâneo a um valor armazenado. Ele alcança essa velocidade usando uma função hash especial, que converte a chave (por exemplo, o nome de uma pessoa) em um índice (um número) do array interno.

Pense em um guarda-volumes:

A chave é o número único do tíquete que você recebe.

A função hash é o atendente que sabe na hora em qual gancho (o índice) está seu casaco.

O valor é o próprio casaco.

Neste exemplo simples, vamos usar um array de tamanho fixo com 10 posições. Importante: para manter o código simples, esta implementação não trata colisões, ou seja, o caso em que duas chaves diferentes geram o mesmo índice.

O Hash Map nativo do Python: o dict

Antes de construir o nosso, vamos ver a implementação nativa e altamente otimizada do Python: o dict. Python

Crie um dicionário vazio

user_profile = {}

Armazene pares chave-valor

user_profile["username"] = "coder_x"
user_profile["status"] = "online"

Recupere um valor na hora usando a chave

print(user_profile["username"]) # Output: coder_x

A estrutura final

print(user_profile) # Output: {'username': 'coder_x', 'status': 'online'}

Construindo uma classe HashMap própria

Agora, vamos implementar a lógica principal nós mesmos. Nosso HashMap vai mostrar claramente como as chaves são convertidas em índices do array para armazenar e recuperar valores:

class HashMap:
    def __init__(self, size):
        self.size = size
        # Initialize the map: a list of 'None' values
        self.map = [None] * self.size

    def _hash(self, key):
        return hash(key) % self.size

    def set(self, key, value):
        index = self._hash(key)
        self.map[index] = value

    def get(self, key):
        index = self._hash(key)
        return self.map[index]

    def __str__(self):
        return str(self.map)

Exemplo prático e indexação

Vamos ver nosso HashMap em ação e observar os índices que ele gera: Python

1. Inicialize o hash map com 10 posições

contact_list = HashMap(10)

2. Armazene entradas (o índice hash é calculado internamente)

Chave: “Alice” -> índice hash: 3

contact_list.set("Alice", "555-0101")

Chave: “Bob” -> índice hash: 6

contact_list.set("Bob", "555-0202")

Chave: “Charlie” -> índice hash: 7

contact_list.set("Charlie", "555-0303")

3. Recupere os valores usando as chaves originais

print(f"Alice's Number: {contact_list.get('Alice')}")    # Output: 555-0101
print(f"Bob's Number: {contact_list.get('Bob')}")      # Output: 555-0202

4. Veja o array interno depois das inserções

print("\n--- Map Array State ---")
print(str(contact_list))

Saída (índices 0-9):

[None, None, None, '555-0101', None, None, '555-0202', '555-0303', None, None]

Este modelo simplificado demonstra o princípio central: usar uma função hash para conseguir buscas rápidas em O(1) (tempo constante), pulando direto para a posição certa do array. Hash maps do mundo real adicionam complexidade para lidar com crescimento e colisões, mas o conceito fundamental continua sendo essa estratégia eficiente de indexação!

Espero que este passo a passo tenha dado a você uma boa compreensão de como um Hash Map funciona por dentro! Embora nosso exemplo seja simples, ele demonstra o hashing e a indexação eficientes que tornam essa estrutura de dados tão poderosa. Ficou com alguma dúvida ou quer saber mais sobre colisões ou redimensionamento? Não hesite em perguntar nos comentários abaixo! Bons códigos!