Pular para o conteúdo
</> Entendendo Algoritmos

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