Tabela hash (ou tabela de dispersão) é uma estrutura de dados que guarda pares de chave e valor e usa uma conta feita com a chave para descobrir em que posição o valor deve ficar. Por isso ela encontra um valor sem precisar procurar item por item.
No artigo sobre árvore binária, o desafio era inserir os valores 45, 25, 65, 10 e 30. A resposta: o 45 é a raiz, o 25 fica à esquerda dele e o 65 à direita. O 10 fica à esquerda do 25 e o 30 à direita do 25. As folhas são 10, 30 e 65, e o percurso em ordem mostra 10, 25, 30, 45 e 65. Bateu com o seu desenho?
Como funciona uma tabela hash?
Pense no armário de gavetas numeradas de uma secretaria, com gavetas de 0 a 7. Para guardar a ficha de alguém, você não escolhe a gaveta no olho: faz uma conta com o nome da pessoa, e o resultado diz o número da gaveta. Para achar a ficha depois, é só repetir a mesma conta com o mesmo nome e ir direto na gaveta certa. Sem abrir as outras!
A tabela hash como armário de gavetas: a conta com o nome diz onde guardar e onde procurar.
Essa conta se chama função hash. Ela recebe a chave e devolve um número, que vira a posição dentro de um vetor.
Chave: o que você usa para procurar. No nosso exemplo, o nome da pessoa.
Valor: o que fica guardado. No nosso exemplo, o ramal do telefone.
Função hash: a conta que transforma a chave em posição.
Exemplo de função hash passo a passo
Vamos usar uma função bem simples: somar o código de cada letra da chave e pegar o resto da divisão pelo número de gavetas, que aqui é 8.
Chave
Códigos das letras
Soma
Resto da divisão por 8
Ana
65 + 110 + 97
272
0
Bruno
66 + 114 + 117 + 110 + 111
518
6
Eva
69 + 118 + 97
284
4
O resto da divisão é o número da gaveta de cada chave.
Então a Ana vai para a gaveta 0, o Bruno para a 6 e a Eva para a 4. Para buscar o ramal do Bruno, o programa refaz a conta, chega no 6 e pronto!
E se duas chaves caírem na mesma gaveta?
Acontece, e tem nome: colisão. Com a nossa função, “Eva” e “Caio” dão o mesmo resultado: as somas 284 e 380 deixam resto 4 na divisão por 8. As duas chaves disputam a gaveta 4!
Uma solução bem comum é o encadeamento: cada gaveta guarda uma pequena lista. Quem cai na mesma gaveta entra na lista dela, e na hora de buscar o programa percorre só essa listinha, comparando as chaves. Lembra da lista encadeada? Olha ela aparecendo de novo!
Da chave à gaveta: a função hash calcula a posição, e duas chaves na mesma gaveta formam uma colisão.Ver a animação da tabela hash, passo a passo
A conta com a chave aponta a gaveta. Na colisão, a gaveta vira uma pequena lista.
Tabela hash em PHP, Python, C e Java
Veja em PHP:
<?php
class TabelaHash
{
private array $gavetas;
public function __construct(private int $tamanho = 8)
{
$this->gavetas = array_fill(0, $tamanho, []);
}
private function hash(string $chave): int
{
$soma = 0;
foreach (str_split($chave) as $letra) {
$soma += ord($letra); // soma o código de cada letra
}
return $soma % $this->tamanho; // o resto da divisão vira a posição
}
public function guardar(string $chave, string $valor): void
{
$posicao = $this->hash($chave);
foreach ($this->gavetas[$posicao] as $i => [$chaveGuardada]) {
if ($chaveGuardada === $chave) {
$this->gavetas[$posicao][$i] = [$chave, $valor]; // chave repetida: troca o valor
return;
}
}
$this->gavetas[$posicao][] = [$chave, $valor];
}
public function buscar(string $chave): ?string
{
$posicao = $this->hash($chave);
foreach ($this->gavetas[$posicao] as [$chaveGuardada, $valor]) {
if ($chaveGuardada === $chave) {
return $valor;
}
}
return null; // a chave não existe
}
}
$ramais = new TabelaHash();
$ramais->guardar('Ana', '2101');
$ramais->guardar('Bruno', '2102');
$ramais->guardar('Eva', '2103');
echo $ramais->buscar('Bruno'), PHP_EOL; // 2102
echo $ramais->buscar('Eva'), PHP_EOL; // 2103
Em Python:
class TabelaHash:
def __init__(self, tamanho=8):
self.tamanho = tamanho
self.gavetas = [[] for _ in range(tamanho)]
def _hash(self, chave):
soma = 0
for letra in chave:
soma += ord(letra) # soma o código de cada letra
return soma % self.tamanho # o resto da divisão vira a posição
def guardar(self, chave, valor):
gaveta = self.gavetas[self._hash(chave)]
for item in gaveta:
if item[0] == chave:
item[1] = valor # chave repetida: troca o valor
return
gaveta.append([chave, valor])
def buscar(self, chave):
gaveta = self.gavetas[self._hash(chave)]
for chave_guardada, valor in gaveta:
if chave_guardada == chave:
return valor
return None # a chave não existe
ramais = TabelaHash()
ramais.guardar("Ana", "2101")
ramais.guardar("Bruno", "2102")
ramais.guardar("Eva", "2103")
print(ramais.buscar("Bruno")) # 2102
print(ramais.buscar("Eva")) # 2103
E em C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TAMANHO 8
struct Item {
const char *chave;
int valor;
struct Item *proximo;
};
struct Item *gavetas[TAMANHO];
int hash(const char *chave) {
int soma = 0;
for (int i = 0; chave[i] != '\0'; i++) {
soma += (unsigned char) chave[i]; // soma o código de cada letra
}
return soma % TAMANHO; // o resto da divisão vira a posição
}
void guardar(const char *chave, int valor) {
int posicao = hash(chave);
for (struct Item *item = gavetas[posicao]; item != NULL; item = item->proximo) {
if (strcmp(item->chave, chave) == 0) {
item->valor = valor; // chave repetida: troca o valor
return;
}
}
struct Item *novo = malloc(sizeof(struct Item));
if (novo == NULL) {
return; // sem memória
}
novo->chave = chave;
novo->valor = valor;
novo->proximo = gavetas[posicao]; // entra no início da lista da gaveta
gavetas[posicao] = novo;
}
int buscar(const char *chave) {
for (struct Item *item = gavetas[hash(chave)]; item != NULL; item = item->proximo) {
if (strcmp(item->chave, chave) == 0) {
return item->valor;
}
}
return -1; // a chave não existe
}
int main(void) {
guardar("Ana", 2101);
guardar("Bruno", 2102);
guardar("Eva", 2103);
printf("%d\n", buscar("Bruno")); // 2102
printf("%d\n", buscar("Eva")); // 2103
for (int i = 0; i < TAMANHO; i++) {
while (gavetas[i] != NULL) {
struct Item *proximo = gavetas[i]->proximo;
free(gavetas[i]); // em C, você devolve a memória de cada item
gavetas[i] = proximo;
}
}
return 0;
}
E em Java:
import java.util.ArrayList;
import java.util.List;
public class Main {
static class TabelaHash {
private final int tamanho;
private final List<List<String[]>> gavetas = new ArrayList<>();
TabelaHash(int tamanho) {
this.tamanho = tamanho;
for (int i = 0; i < tamanho; i++) {
gavetas.add(new ArrayList<>());
}
}
private int hash(String chave) {
int soma = 0;
for (char letra : chave.toCharArray()) {
soma += letra; // soma o código de cada letra
}
return soma % tamanho; // o resto da divisão vira a posição
}
void guardar(String chave, String valor) {
List<String[]> gaveta = gavetas.get(hash(chave));
for (String[] item : gaveta) {
if (item[0].equals(chave)) {
item[1] = valor; // chave repetida: troca o valor
return;
}
}
gaveta.add(new String[] {chave, valor});
}
String buscar(String chave) {
for (String[] item : gavetas.get(hash(chave))) {
if (item[0].equals(chave)) {
return item[1];
}
}
return null; // a chave não existe
}
}
public static void main(String[] args) {
TabelaHash ramais = new TabelaHash(8);
ramais.guardar("Ana", "2101");
ramais.guardar("Bruno", "2102");
ramais.guardar("Eva", "2103");
System.out.println(ramais.buscar("Bruno")); // 2102
System.out.println(ramais.buscar("Eva")); // 2103
}
}
Observe que guardar e buscar seguem o mesmo roteiro: calcular a posição com a função hash e olhar só aquela gaveta. E repare em um detalhe do guardar: se a chave já existe, o valor é trocado, porque em uma tabela hash cada chave aparece uma vez só.
Comparação entre as formas de busca que vimos até aqui.
Mas ATENÇÃO: isso só vale quando a função hash espalha bem as chaves. Se todas caírem na mesma gaveta, a busca vira uma busca item por item dentro dela. A documentação do Python faz o mesmo aviso sobre os dicionários: as operações são rápidas no caso médio, e no pior caso, quando todas as chaves resultam no mesmo hash, o tempo passa a crescer junto com a quantidade de itens.
E tem um preço: a tabela hash não guarda as chaves em ordem de tamanho. Se você precisa dos valores em ordem crescente, quem resolve é a árvore binária de busca. Cada estrutura tem a sua hora!
Aí você pergunta: já usei tabela hash sem saber?
Muito provavelmente! O manual do PHP diz que os arrays da linguagem são, na verdade, tabelas hash ordenadas. E o dicionário do Python também trabalha com o hash das chaves. Veja em PHP:
E em Java, a classe pronta é a HashMap, que a documentação descreve como uma implementação de mapa baseada em tabela hash:
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<String, String> ramais = new HashMap<>();
ramais.put("Ana", "2101");
ramais.put("Bruno", "2102");
ramais.put("Eva", "2103");
System.out.println(ramais.get("Bruno")); // 2102
}
}
Toda vez que você escreve $ramais['Bruno'], acontece por baixo dos panos o que você acabou de aprender: uma conta com a chave e um pulo direto para a posição. Quem diria… Agora você sabe o que está por trás!
Agora é com você!
No papel: em qual gaveta a nossa função hash coloca a chave Bia? Os códigos das letras são B = 66, i = 105 e a = 97. Ela colide com alguém do exemplo? Depois confira no código, mostrando na tela o resultado da função hash para “Bia”.
E um desafio maior: crie o método remover, que apaga uma chave da tabela. Pense antes de digitar: em qual gaveta procurar? Tente sozinho, sem pedir a resposta pronta para ninguém. Você consegue!
Com a tabela hash fechamos a trilha de estruturas de dados: lista encadeada, fila, árvore binária e tabela hash. Se você acompanhou e fez os desafios, já tem uma base firme para seguir em frente. No próximo artigo começamos outra trilha, a de orientação a objetos na prática, com os princípios SOLID. Até lá!
Oracle, documentação do Java 21. Classe HashMap (em inglês), com o mapa baseado em tabela hash, sem garantia de ordem, e o tempo constante de get e put quando a função hash espalha bem os elementos.
Os exemplos foram executados em PHP 8.3, Python 3.13, GCC 13 e Java 21.
Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".
Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.
Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.
Usamos cookies necessários para o site funcionar. Com a sua permissão, também usamos cookies de estatística e de publicidade, com ou sem personalização. Você pode mudar a escolha quando quiser em Preferências de cookies. Política de privacidade
Continue a conversa