Internals de Funções Hash e Tratamento de Colisões
Entenda como o Python calcula o hash de objetos, como endereçamento aberto e encadeamento resolvem colisões e por que O(1) no caso médio pode degradar para O(n).
Internals de Funções Hash e Tratamento de Colisões é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
O que é um mapa hash?
Um mapa hash (dicionário em Python) associa chaves a valores usando uma função de hash que converte qualquer chave em um índice inteiro de um vetor subjacente. Uma função de hash ideal distribui as chaves uniformemente pelo vetor, permitindo busca, inserção e remoção em O(1) no caso médio. O vetor subjacente é chamado de tabela hash ou vetor de compartimentos.
Em Python, dict é um mapa hash altamente otimizado. Entender seus componentes internos ajuda você a analisar o comportamento no pior caso e a escolher chaves adequadas.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Funções de hash e o método __hash__
O Python chama __hash__(key) para calcular um inteiro a partir da chave e, em seguida, calcula o resto desse inteiro pelo tamanho da tabela para encontrar o índice do compartimento. Tipos integrados como int, str e tuple têm implementações integradas de hash rápidas. list e dict não aceitam hash (são mutáveis, e modificá-los invalidaria qualquer hash armazenado).
Uma boa função de hash distribui as chaves uniformemente, é determinística e é rápida de calcular. O hash de strings do Python é aleatorizado entre execuções (um recurso de segurança) — use PYTHONHASHSEED=0 para desativá-lo e obter reprodutibilidade nos testes.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Colisões: quando duas chaves geram o mesmo compartimento
Uma colisão ocorre quando duas chaves distintas produzem o mesmo índice de compartimento. As colisões são inevitáveis (princípio da casa dos pombos: infinitas chaves, um número finito de compartimentos). Duas estratégias padrão de resolução são o encadeamento e o endereçamento aberto. O Python usa uma variante de endereçamento aberto com sondagem pseudoaleatória.
O encadeamento armazena uma lista encadeada (ou vetor dinâmico) em cada compartimento; todas as chaves que colidem nesse compartimento formam uma cadeia. O endereçamento aberto procura o próximo compartimento vazio de acordo com uma sequência de sondagem.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneEndereçamento aberto: sondagem linear
Na sondagem linear, quando ocorre uma colisão no índice i, o mapa verifica i+1, i+2, ... (dando a volta ao chegar ao fim) até encontrar uma posição vazia. A busca deve sondar a mesma sequência para encontrar a chave. As remoções exigem um marcador de exclusão em vez de limpar a posição, para evitar romper a cadeia de sondagem.
O agrupamento é a principal desvantagem: quando se forma um agrupamento de posições ocupadas, as inserções futuras nessa área aumentam o agrupamento, degradando o desempenho até O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Fator de carga e redimensionamento
O fator de carga é a razão entre as entradas armazenadas e a capacidade total: α = n/m. À medida que α aumenta, a probabilidade de colisão cresce e o desempenho piora. O dict do Python redimensiona a tabela (dobra a capacidade) quando o fator de carga ultrapassa aproximadamente 2/3. O redimensionamento recalcula o hash de todas as entradas existentes na nova tabela maior — uma operação O(n) que ocorre com pouca frequência, mantendo o custo amortizado de inserção em O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeO(1) médio vs. O(n) no pior caso
Com uma boa função de hash, as colisões são raras e o comprimento esperado da cadeia é constante, independentemente de n. Portanto, a busca, a inserção e a remoção no caso médio são O(1). No entanto, um cenário de pior caso — por exemplo, uma entrada deliberadamente adversarial que mapeia todas as chaves para o mesmo compartimento — reduz todas as operações a O(n). A semente de hash aleatorizada do Python reduz o impacto desse ataque, mas não elimina teoricamente o pior caso.
Para a análise em entrevistas, diga: "O(1) no caso médio, O(n) no pior caso devido a colisões".
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyMapa hash do Python em comparação com mapa de valores padrão e contador
O Python oferece três variantes de mapas hash que vale a pena conhecer. dict é o mapa de uso geral; acessar uma chave ausente gera KeyError. defaultdict(factory) devolve um valor padrão ao acessar uma chave ausente (útil para reunir listas ou fazer contagens). Counter é uma subclasse especializada para contar objetos que aceitam hash; também aceita operações aritméticas entre contadores.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionMapa hash vs. conjunto hash
Um conjunto hash armazena apenas chaves (sem valores associados), oferecendo verificação de pertencimento, inserção e remoção em O(1). O set do Python é um conjunto hash. Use um conjunto quando precisar apenas responder à pergunta "este elemento existe?", sem armazenar dados associados. Use um dicionário quando precisar associar valores (contagens, resultados etc.) a chaves.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Implementando um mapa hash do zero (versão para entrevistas)
Às vezes, entrevistadores pedem que você implemente um mapa hash básico. Os componentes principais são: um vetor de compartimentos de tamanho fixo (use 16 ou 1024), cada compartimento sendo uma lista de pares (chave, valor) para encadeamento, uma função de hash (use o hash integrado do Python % capacidade) e redimensionamento quando o fator de carga exceder 0,7. Mencionar proativamente o redimensionamento e o fator de carga demonstra profundidade de conhecimento.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedQuando os mapas hash falham: chaves que não aceitam hash
Somente objetos que aceitam hash podem ser chaves de dicionário. No Python, um objeto aceita hash se tiver um método __hash__ e um método __eq__, e se seu valor de hash não mudar durante seu ciclo de vida. Listas, conjuntos e dicionários são mutáveis e, portanto, não aceitam hash. Tuplas e conjuntos imutáveis são alternativas que aceitam hash para listas e conjuntos quando usados como chaves.
Uma armadilha comum em entrevistas: agrupar anagramas exige usar uma tupla ordenada (não uma lista ordenada) como chave do dicionário.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Resumo: complexidade dos mapas hash
Os mapas hash oferecem O(1) no caso médio para inserção, remoção e busca — a base de muitas soluções ideais de entrevistas. As principais suposições são: uma boa função de hash distribui as chaves uniformemente, o fator de carga permanece limitado (o redimensionamento mantém essa condição) e os objetos usados como chaves são imutáveis e aceitam hash. Quando essas suposições são válidas, os mapas hash transformam varreduras lineares O(n) em buscas O(1), permitindo soluções como soma de dois em O(n), em vez de O(n²).
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de dados e algoritmos — preparação para entrevistas de programação abordados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu: um mapa hash associa chaves a índices de compartimentos usando uma função de hash e realiza operações O(1) no caso médio, as colisões são resolvidas por encadeamento (uma lista encadeada por compartimento) ou endereçamento aberto (sondagem em busca do próximo compartimento vazio) e somente objetos imutáveis que aceitam hash podem ser chaves de dicionário — use tuplas em vez de listas quando precisar de uma chave de sequência. Em seguida, resolveremos soma de dois e suas muitas variantes de entrevista.
Perguntas Frequentes
A aula “Internals de Funções Hash e Tratamento de Colisões” é grátis?
Sim — o texto completo de “Internals de Funções Hash e Tratamento de Colisões” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Internals de Funções Hash e Tratamento de Colisões”?
Entenda como o Python calcula o hash de objetos, como endereçamento aberto e encadeamento resolvem colisões e por que O(1) no caso médio pode degradar para O(n). Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Internals de Funções Hash e Tratamento de Colisões”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Internals de Funções Hash e Tratamento de Colisões
- Two-Sum e Suas Muitas Variantes
- Contagem e Agrupamento por Frequência
- Maior Sequência Consecutiva e Cache LRU