Usos da tabela hash
Além de guardar pares chave → valor, a tabela hash resolve, em tempo O(1), dois problemas práticos que o livro destaca: saber se algo já foi visto (duplicatas) e guardar respostas para não repetir um trabalho caro (cache).
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
// Duplicatas: um conjunto (tabela hash) responde "já vi?" em uma consulta
function votar(jaVotaram, nome) {
const chave = nome.trim().toLowerCase();
if (jaVotaram.has(chave)) return false; // já votou: barra
jaVotaram.add(chave);
return true;
}
// Cache: se a página já está guardada, devolve na hora
function acessar(cache, url, buscarNoServidor) {
if (cache.has(url)) return cache.get(url); // acerto
const pagina = buscarNoServidor(url); // falha: caro
cache.set(url, pagina); // guarda para a próxima vez
return pagina;
}1. Detectar duplicatas: a votação
Cada pessoa só pode votar uma vez. Antes de aceitar um voto, o sistema precisa saber se o nome já votou. Em uma lista, é preciso comparar com cada nome; em uma tabela hash, é uma única consulta.
Votos aceitos
0
Duplicatas barradas
0
Comparações: lista × hash
0 × 0
2. Guardar respostas: o cache
Gerar uma página no servidor é caro. O cache é uma tabela hash cuja chave é o endereço da página e cujo valor é a página pronta: se já está lá, devolve na hora; senão, gera, guarda e devolve. Neste exemplo, buscar no servidor custa 800 ms e usar o cache custa 1 ms.
Acessar uma página
Acertos no cache
0 de 0
Tempo com cache
0 ms
Tempo sem cache
0 ms
Guardado no cache
vazio