Programacao · conceitos · estruturas de dados

O que e uma hash table?

Por ColdwastAtualizado a 16 jul. 20268 min de leitura#data-structures#hash-table#concepts

Codigo de programacao colorido num ecra — Uma hash table e a estrutura por tras dos dicionarios e mapas que usa todos os dias - transforma uma chave diretamente numa localizacao.

Uma hash table (tambem chamada hash map) e uma estrutura de dados que armazena pares chave-valor e permite encontrar qualquer valor pela sua chave em, em media, tempo constante - independentemente da quantidade de dados que contem. E uma das estruturas mais uteis de toda a programacao e e o que da poder aos dicionarios e mapas integrados em praticamente todas as linguagens. Depois de ver como funciona, muitos momentos de "como e que isto e tao rapido?" passam a fazer sentido.

O problema que resolve

Imagine armazenar uma lista telefonica como uma simples lista. Para encontrar uma pessoa, pode ter de percorrer cada entrada - um trabalho lento que fica mais lento a medida que a lista cresce, uma operacao O(n). A promessa de uma hash table e diferente: da-lhe a chave e ela salta mais ou menos diretamente para o valor, sem percorrer nada. E essa a diferenca entre verificar cada entrada e saber exatamente onde procurar.

Como funciona: a hash function e os buckets

Por baixo, uma hash table e suportada por um array de posicoes chamadas buckets. O ingrediente magico e a hash function: pega na sua chave e transforma-a num numero, que e mapeado para um indice nesse array.

index = hash(key) % number_of_buckets

Para armazenar um valor, passa a chave pela hash para obter um indice e coloca o valor nesse bucket. Para le-lo de volta, passa a mesma chave pela hash outra vez, chega ao mesmo indice e recolhe o valor. Como calcular a hash e indexar um array sao ambos passos rapidos e de custo fixo, as pesquisas nao ficam mais lentas a medida que a tabela cresce. E esse o truque todo.

Colisoes e como sao tratadas

Duas chaves diferentes podem ter hash para o mesmo bucket. Isso chama-se colisao e toda a hash table real tem de lidar com isso. Existem duas estrategias comuns:

Chaining: cada bucket contem uma pequena lista, e as entradas em colisao sao armazenadas juntas nessa lista. As pesquisas verificam depois a lista (normalmente muito curta) no bucket correto.
Open addressing: se um bucket estiver ocupado, a tabela procura a proxima posicao livre segundo uma regra fixa, e as pesquisas seguem a mesma regra.

Com uma boa hash function e buckets suficientes, as colisoes mantem-se raras e essas listas mantem-se minusculas, pelo que as pesquisas permanecem rapidas.

Codigo de programacao vibrante exibido num ecra de computador — A hash function e o que faz uma chave mapear para um bucket; uma boa function distribui as chaves uniformemente e mantem as colisoes raras.

E quanto ao desempenho?

E aqui que as hash tables brilham, e onde vive a ressalva honesta. Em media, insercao, pesquisa e remocao sao todas O(1) - tempo constante. No pior caso, se uma ma hash function ou uma entrada hostil despejar todas as chaves num unico bucket, essas operacoes degradam-se para O(n), porque volta a percorrer uma unica lista longa. As boas implementacoes evitam isto usando hash functions solidas e fazendo resizing (rehashing para um array maior) quando a tabela fica demasiado cheia, o que mantem o desempenho num O(1) amortizado. Se quiser rever esta notacao, consulte o nosso guia sobre notacao Big O.

Onde ja usa uma

Usa hash tables constantemente, muitas vezes sem lhes dar nome. Os tipos dicionario e mapa na maioria das linguagens sao hash tables por baixo: Python dict, Java HashMap, JavaScript Map e objeto, Ruby Hash, Go map. Sao tambem a ferramenta de eleicao para caches, para eliminar duplicados e para contar ocorrencias. A otimizacao classica de transformar uma pesquisa lenta com ciclos aninhados numa rapida - baixando de O(n²) para O(n) - e quase sempre feita substituindo varreduras repetidas por uma pesquisa em hash table.

Os compromissos

Rapida, mas sem ordem. Uma hash table basica nao mantem as chaves em qualquer ordem ordenada ou de insercao (embora algumas versoes de linguagem acrescentem ordenacao por cima).
Usa memoria extra. Manter as colisoes raras significa manter buckets sobresselentes, pelo que uma hash table troca alguma memoria pela sua velocidade.
O pior caso e real. O O(1) e uma media; uma entrada adversarial pode forcar o caminho lento, o que importa para codigo sensivel a seguranca.

FAQ

Uma hash table e o mesmo que um dicionario? Em termos do dia a dia, sim - um dicionario ou mapa e a ideia geral (chave para valor), e uma hash table e a forma mais comum de o implementar. Quando alguem diz Python "dict" ou Java "HashMap", esta a usar uma hash table.

Porque e que a pesquisa e O(1) em media? Porque calcula a hash da chave e indexa diretamente num array, em vez de percorrer entradas. Ambos os passos levam tempo constante independentemente de quantos itens estao armazenados, pelo que o custo medio nao cresce com os dados.

O que e uma colisao? Quando duas chaves diferentes tem hash para o mesmo bucket. E normal e esperado; as hash tables tratam disso com chaining ou open addressing, e mantem-na rara com uma boa hash function e resizing.

Quando nao devo usar uma hash table? Quando precisa das chaves mantidas em ordem ordenada, ou de consultas por intervalo ordenado - uma estrutura baseada em arvore encaixa melhor. Tambem quando a memoria e extremamente limitada, ja que as hash tables mantem espaco sobresselente para se manterem rapidas.

Guia independente, mantido pela comunidade. coldwa.st e um site de recursos de programacao; este explicador aborda as hash tables a nivel introdutorio. As complexidades e comportamentos descritos sao resultados padrao das ciencias da computacao.