Pular para o conteúdo
</> Entendendo Algoritmos

Tabelas hash

Uma função hash transforma a chave em um número, que indica o balde onde o valor fica guardado. Busca, inserção e remoção levam O(1) no caso médio. Quando duas chaves caem no mesmo balde, há uma colisão e os itens formam uma lista.

hash(chave) = soma dos códigos dos caracteres % tamanho da tabela

Explicação do algoritmo: escolha um nível para ler.

{ }Ver o código
function funcaoHash(chave, tamanho) {
  let soma = 0;
  for (let i = 0; i < chave.length; i++) {
    soma += chave.charCodeAt(i);   // soma os códigos das letras
  }
  return soma % tamanho;           // posição (balde) da chave
}

function inserir(tabela, chave, valor) {
  const balde = tabela[funcaoHash(chave, tabela.length)];
  const existente = balde.find((e) => e.chave === chave);

  if (existente) existente.valor = valor;   // chave repetida: atualiza
  else balde.push({ chave, valor });        // colisão? entra na lista do balde
}

function buscar(tabela, chave) {
  const balde = tabela[funcaoHash(chave, tabela.length)];
  return balde.find((e) => e.chave === chave)?.valor;   // só compara dentro do balde
}

Inserir

Buscar

Itens
0
Baldes
8
Fator de carga
0.00
  1. 0
    vazio
  2. 1
    vazio
  3. 2
    vazio
  4. 3
    vazio
  5. 4
    vazio
  6. 5
    vazio
  7. 6
    vazio
  8. 7
    vazio