Tratamento de colisões em tabelas hash
Colisões ocorrem quando a função hash gera o mesmo índice para chaves diferentes. É como tentar colocar dois livros na mesma prateleira quando só há espaço para um.
1. Endereçamento Fechado (Encadeamento Separado)
Cada posição da tabela mantém uma lista encadeada (Separate Chaining) para armazenar os elementos que foram mapeados para o mesmo índice.
Além da lista encadeada, podemos utilizar outras estrutura de dados dinâmica para armazenar esses valores com mesmo índice. Como por exemplo, o uso da AVL.
Implementação
public class HashNode<K,V> {
K chave;
V valor;
HashNode<K,V> proximo;
public HashNode(K chave, V valor) {
this.chave = chave;
this.valor = valor;
this.proximo = null;
}
}
public class TabelaHash<K,V> {
private ArrayList<HashNode<K,V>> bucketArray;
public void put(K chave, V valor) {
int indice = funcaoHash(chave);
HashNode<K,V> cabeca = bucketArray.get(indice);
// Procura se a chave já existe
while (cabeca != null) {
if (cabeca.chave.equals(chave)) {
cabeca.valor = valor;
return;
}
cabeca = cabeca.proximo;
}
// Insere novo nó no início da lista
HashNode<K,V> novoNo = new HashNode<>(chave, valor);
novoNo.proximo = bucketArray.get(indice);
bucketArray.set(indice, novoNo);
}
}2. Endereçamento Aberto
Nessa técnica não é utilizado uma estrutura auxiliar para armazenar os valores de chaves que colidiram, tudo é armazenado na própria tabela hash.
Neste caso, o tamanho da tabela deve ser pelo menos igual ao número total de chaves
Caso exista colisão, utilizado o método de sondagem linear (linear probing) onde olhamos as próximas posições na tabela hash, linearmente, até que encontremos uma posição livre (slot vago).
Sondagem Linear (Linear Probing)
public class TabelaHashAberta<K,V> {
private K[] chaves;
private V[] valores;
public void put(K chave, V valor) {
int indice = funcaoHash(chave);
while (chaves[indice] != null) {
if (chaves[indice].equals(chave)) {
valores[indice] = valor;
return;
}
indice = (indice + 1) % tamanho; // Sondagem linear
}
chaves[indice] = chave;
valores[indice] = valor;
}
}