7.1 Definição de colisões em tabela hash
Colisão em uma tabela hash acontece quando duas chaves diferentes são hashadas para o mesmo índice de array. Isso resulta em mais de um elemento tentando ocupar a mesma célula na tabela hash.
Exemplo de colisão:
Suponha que a gente tenha uma função de hash simples que retorna o resto da divisão da chave pelo tamanho da tabela. Para as chaves 5 e 15 com tamanho de tabela 10, ambas as chaves darão o mesmo índice: 5 % 10 = 5 e 15 % 10 = 5. Isso é uma colisão.
Outro exemplo:
Imagina que você está criando um dicionário de nomes, e você tem uma função de hash simples que retorna a primeira letra do nome. Mas descobre-se que 80% dos nomes começam com a letra "A". Não é só uma colisão, é um problemão.
7.2 Métodos de resolução de colisões – Encadeamento
Existem vários métodos para resolver colisões em tabelas hash. Os dois métodos mais comuns são encadeamento (chaining) e endereçamento aberto (open addressing).
Encadeamento (Chaining)
Vantagens:
- Simplicidade na implementação.
- Eficiente quando há poucas colisões.
- Menor dependência da densidade de preenchimento da tabela hash.
Desvantagens:
- Requer memória adicional para ponteiros na lista encadeada.
- O desempenho pode cair com um grande número de colisões devido a cadeias longas.
Exemplo de implementação do método de encadeamento:
Você pode apenas estudar como a função insert trabalha, mas eu decidi mostrar o código completo para facilitar.
class HashTableChaining:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# Exemplo de uso:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Saída: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Saída: None
7.3 Método número dois – endereçamento aberto
O método de endereçamento aberto envolve a busca da próxima célula disponível no array quando ocorre uma colisão. Existem diferentes estratégias para encontrar uma nova célula: sondagem linear, sondagem quadrática e duplo hash.
Vantagens:
- Não requer memória adicional para armazenar ponteiros.
- Representação de dados mais compacta.
Desvantagens:
- O desempenho pode cair significativamente com alta densidade de preenchimento da tabela.
- Requer mais recursos computacionais para resolver colisões.
Exemplos de estratégias de endereçamento aberto
Sondagem linear (Linear Probing):
- Sondagem com passo 1:
index = (index + 1) % size. - Simples, mas pode levar à "clusterização".
Sondagem quadrática (Quadratic Probing):
- Sondagem com passo aumentando ao quadrado:
index = (index + i^2) % size. - Reduz o problema de clusterização, mas é mais difícil de implementar.
Duplo hash (Double Hashing):
- Uso de uma segunda função de hash para calcular o passo:
index = (index + i * hash2(key)) % size. - Menos problemas de clusterização, mas mais complexo na implementação.
Exemplo de implementação do método de endereçamento aberto (sondagem linear): Vou mostrar o código completo, mas para facilidade, você pode apenas examinar o funcionamento da função insert
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
def delete(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
return
index = (index + 1) % self.size
if index == original_index:
break
# Exemplo de uso:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Saída: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Saída: None
7.4 Impacto das colisões na tabela hash
Impacto das colisões no desempenho.
Tempo médio de acesso:
- Em condições ideais (sem colisões) o tempo médio de acesso aos elementos na tabela hash é
O(1). - Colisões aumentam o tempo de acesso, pois é necessário lidar com cadeias ou sondagem de células, aumentando o número de operações.
Aumento das cadeias:
- No método de encadeamento, o aumento das cadeias com muitas colisões pode levar a um tempo de acesso linear
O(n)para operações de busca, inserção e exclusão. - Cadeias longas aumentam o número de comparações necessárias para encontrar ou inserir um elemento.
Complexidade espacial:
- No método de encadeamento, é necessária memória adicional para armazenar ponteiros nas listas ligadas.
- No método de endereçamento aberto, o preenchimento da tabela acima de certo nível (geralmente cerca de 70-80%) aumenta significativamente a quantidade de colisões e, consequentemente, o tempo de acesso.
Clusterização: No método de endereçamento aberto (especialmente na sondagem linear), ocorre clusterização quando várias células consecutivas ficam ocupadas, aumentando a probabilidade de colisões e piorando o desempenho.
Exemplo de análise do impacto das colisões no desempenho:
Isso é para os curiosos que querem se aprofundar
import time
import random
# Sondagem linear
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
# Gerando uma grande quantidade de dados para inserção
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]
# Inserindo dados e medindo o tempo
start_time = time.time()
for key in keys:
hash_table.insert(key, key)
print(f"Tempo de inserção: {time.time() - start_time:.6f} segundos")
# Buscando dados e medindo o tempo
start_time = time.time()
for key in keys:
hash_table.search(key)
print(f"Tempo de busca: {time.time() - start_time:.6f} segundos")
GO TO FULL VERSION