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
}Itens
0
Baldes
8
Fator de carga
0.00
- 0vazio
- 1vazio
- 2vazio
- 3vazio
- 4vazio
- 5vazio
- 6vazio
- 7vazio