Cada coisa é uma coisa
Antes de mais nada, é importante entender que cada tipo de estrutura de dados possui uma aplicação mais específica. Então, dizer que hashes são mais rápidos que listas encadeadas é comparar laranjas com bananas.
Uma "tabela" é bastante eficiente para recuperar um elemento contido nela a partir de uma chave. Isso significa que é rápido encontrar uma agulha no palheiro se você tiver uma forma (hash) de identificar a agulha.
Entretanto, percorrer uma tabela inteiro é, em geral, menos eficiente que percorrer uma lista inteiro.
Além disso, somente uma lista baseada em vetores permite acessar elementos aleatórios de forma eficiente.
Hashes
São valores numéricos calculados por uma função a partir de um valor original de tamanho arbitrário. Existem vários algoritmos de hash, sendo que os melhores são os que emitem o menor número possível de hashes repetidos.
Por exemplo, a classe String
do Java possui o seguinte método para gerar o hash code:
public int More ...hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
A documentação do método afirma que o hash é calculado da seguinte forma:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
Onde:
s[i]
: i
-ésimo caractere da String.
m
: tamanho da String, em caracteres
Em resumo, gerar um hash é como gerar um ID numérico para o objeto.
Em Java, qualquer objeto pode ter uma implementação próprio do hashCode
. Essa implementação deve considerar todos os atributos que identificam o objeto. É importante que objetos diferentes tenham hashes diferentes, tanto quanto possível.
Tabelas de Hashes
O número gerado por uma função hash
pode ser usado para localizar facilmente um objeto numa espécie de "tabela".
Internamente, no Java por exemplo, essa tabela é um vetor. A cada posição do vetor é atribuído uma faixa de números. Seria como slots de uma prateleira.
Armazenando valores
Vamos supor que criamos um Hashtable
e o vetor interno tem 10 posições (slots). Suponha ainda que adicionamos objetos e informemos chaves valores de hash variem de 1 a 100. Dessa forma, hashes que retornem valores de 1 a 10 serão colocados no primeiro slot, os que retornem valores de 11 a 20 no segundo slot e assim por diante.
Se adicionarmos um objeto (1) cujo hash da chave seja 20 ele será colocado no segundo slot. Se adicionarmos outro objeto (2) com chave de hash 45 ele será colocado quinto slot. Se adicionarmos ainda outro objeto (3) com chave de hash 15, ele será colocando também no segundo slot. Teríamos a seguinte estrutura de dados:
Slot 1:
Slot 2: Objeto 1, Objeto 3
Slot 3:
Slot 4:
Slot 5: Objeto 2
Slot 6:
Slot 7:
Slot 8:
Slot 9:
Slot 10:
Note que cada item da tabela é também um tipo de vetor. Em Java, na classe Hashtable
, isso é implementado através de uma lista ligada de objetos do tipo Entry
(entrada).
Recuperando valores
Então, para recuperar um objeto, basta passar a chave para a tabela, esta calculará o hash e irá diretamente ao slot para recuperar o item.
Continuando o exemplo mais acima, se eu quisesse recuperar o Objeto 3, teria que passar a chave do mesmo. A tabela iria calcular o hash code da chave, que retornaria o valor 15. Hashes sempre retornam o mesmo valor para a mesma chave. Então com uma conta simples eu sei que o item será encontrado no segundo slot. Porém, como ainda temos uma lista de objetos, a tabela terá que percorrer a lista de entradas do slot 2 e verificar, um a um, qual é realmente o Objeto 3.
Implicações
As explicações acima possuem várias implicações:
- Se houver muita colisão de hashes, muitos objetos acabarão caindo em poucos slots. havendo uma distribuição ruim, cada vez que for necessário recuperar um item a eficiência será ruim, pois será necessário percorrer a lista de elementos do slot e comparar um a um.
- O tamanho interno da tabela precisa ser bem calculado, para que não haja muitos itens em cada slot, nem muitos slots vazios. Na implementação do Java, quando os slots começam a ficar cheios o
Hashtable
aumenta o número de slots e faz uma redistribuição.
- No Java, o método que gera o hash pode ser chamado várias vezes, então é importante cuidar do desempenho e fazer cache do valor quando possível.
- Dependendo da implementação da hash table, incluir muitos itens repetidamente pode ser bem ineficiente, já que haverá repetidas pausas para adicionar novos slots e redistribuir os elementos.
Diferentes tipos de implementações
Uma grande parte do que foi descrito acima é apenas um dos tipos possíveis de implementação de uso de hashes para recuperar valores.
Por exemplo, em Java, existe o TreeMap, uma "tabela" cujos hashes das entradas não ficam armazenadas num vetor, mas em uma árvore binária.
Há várias implicações nisso. Dependendo do balanceamento da árvore pode ser mais ou menos eficiente recuperar elementos. Comparando uma árvore balanceada com uma implementação de vetores com slots cheios a árvore iria ganhar.
Porém, já fiz algumas implementações que precisavam carregar árvores bem grandes em memória e o TreeMap
foi muito mais eficiente.