Implementando Tabela Hash (Hash Table) com NodeJS e Javascript

Buscar um usuário por id num array de 50 mil registros é O(n). Com hash table bem feita, vira O(1) na média — é por isso que cache, contagem e índices em memória usam essa estrutura o tempo todo.

O que você vai aprender:

• Como chave → índice via função hash
• Implementar tabela com array + tratamento básico de colisão
• Quando o Map nativo do JS já resolve
• Colisões e por que “tabela cheia” degrada performance

Pré-requisitos: grafos (ep. 7) ou o resumo.

Hash table: chave, hash e bucket

As Hash Tables ou tabelas de hash (é muito ruim ficar traduzindo esse nome vou chamar de Hash Tables blz?!), bom, HashTable é um tipo de estrutura de dados que o foco, ou o objetivo é otimizar a busca, inserção e remoção de elementos, ou seja, deixar tudo isso o mais rápido possível.

Quando usamos Hash Tables isso permite um acesso praticamente instantâneo na informação/dados dos elementos pelas keys (chaves) únicas... isso te lembra algo? Você acessa o valor de um elemento por uma key/chave, lembra alguma coisa?

Estamos falando de tabelas, mas quando você acessa um objeto JSON, você acessa por uma chave única certo? e acessa direto o valor daquela chave... É uma comparação meio estranha mas é pra te ajudar a entender de forma simples... ai pensa que no JSON você tem uma chave e um valor, e na HashTable você tem uma chave e um valor, a diferença é que na HashTable a gente tem um algoritmo que calcula um valor único para cada chave, então a gente não sabe exatamente o valor dessa chave igual no JSON, mas sabemos que a chave ta lá...e essa chave que leva pra um elemento da nossa tabela.

Mas, relaxa, que você não vai lembrar tudo de cabeça 100% do tempo, por isso, vem aqui pra lembrar sempre que precisar.

Mão na Massa

O JavaScript já tem uma implementação nativa de HashTable que é o Map, sempre que usamos o Map no NodeJS/Javascript a gente ta usando uma implementação de HashTables.

Mas, pra que eu ia te fazer ler até aqui e falar pra você ir usar o Map né? Vamo tentar fazer esse trambolho na raça e ver o que sai...

Agora a Prática

Então abre aí o seu VSCode ou sua IDE favorita e vamos lá, crie um arquivo chamado hash-table.js e cola o código abaixo:

class HashTable {
  constructor(size = 100) {
    this.table = new Array(size)
    this.size = size
  }
 
  _hash(key) {
    let hash = 0
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.size
    }
    return hash
  }
}

Agora vamos explicar um pouco o código acima antes de continuar:

• A gente tem uma classe HashTable que recebe o size como parâmetro (opcional) caso não tenha size a gente coloca como 100 o valor padrão
• A gente inicia/cria um novo array chamado table com o tamanho definido pelo size e seta a propriedade size
• A gente tem uma função _hash que recebe uma key como parâmetro e calcula o valor do "hash" baseado nos caracteres da chave e seus valores ASCII
  • O valor do hash é calculado somando o valor ASCII de cada caractere na chave
  • Depois o valor ASCII é multiplicado pela sua própria posição no array da chave
  • Depois a gente calcula o valor do módulo da soma dessa conta de ascii+posição com o tamanho da tabela para obter o valor final do hash

A função _hash parece um pouco complexa, e é meio chatinho de entender, mas lembra, o objetivo é ter um valor de hash e que esse valor do hash é a chave que leva pra um elemento da nossa tabela...Lógico que pra fins de teste, você pode ter uma função hash muito mais simples, que retorne um random ou algo do tipo, a ideia é que o valor do hash seja único para cada chave.

Se quiser entender e aprofundar um pouco mais, essa função _hash é uma implementação simples da Função de hHash "djb2" que é uma função de hash usada em muitas aplicações.

Agora vamos seguir e implementar mais uns negocinhos, dentro da classe HashTable logo depois da função _hash vamos adicionar a função set, get e remove:

set(key, value) {
  const index = this._hash(key);
  console.log('#set: setting a new value on the hastable', { index, key, value })
  if (!this.table[index]) {
      this.table[index] = [];
  }
  this.table[index].push([key, value]);
}
 
get(key) {
  const index = this._hash(key);
  console.log('#get: getting the value from the hastable', { index, key })
  const items = this.table[index];
  if (items) {
      for (let item of items) {
          if (item[0] === key) {
              return item[1];
          }
      }
  }
  return undefined;
}
 
remove(key) {
  const index = this._hash(key);
  const items = this.table[index];
  if (items) {
      for (let i = 0; i < items.length; i++) {
          if (items[i][0] === key) {
              items.splice(i, 1);
              return true;
          }
      }
  }
  return false;
}

Eu não vou aprofundar muito nas funções acima com um passo a passo, porque a lógica dessas é mais simples, todas elas usam a função _hash para calcular e descobrir qual é o index do elemento que vamos colocar, buscar ou remover, e depois usando esse index a gente faz o set (incluir), get (busca) e o remove (deleta) o elemento...O ponto que vale citar aqui é que no set e no get colocamos um log pra ver o que ta acontecendo.

Agora vamos adicionar mais umas linhas de código só pra testar a HashTable que a gente fez, no final do arquivo (depois da classe) coloca isso aqui:

const hashTable = new HashTable()
hashTable.set('hello', 'world')
hashTable.set('hash', 'table')

No código aí em cima, a gente tá criando uma nova instância da nossa HashTable e adicionando dois elementos, um com a chave hello e valor world e outro com a chave hash e valor table, dai agora vamos colocar uns logs e fazer o get desses elementos, coloca mais esse código e depois vamos executar esse arquivo JS:

console.log('\n#when getting "hello" from table, result should be = "world"')
const resultGetFoo = hashTable.get('hello')
console.log('# result:', {
  result: resultGetFoo,
})
 
console.log('\n#when getting "hash" from table, result should be = "table"')
const resultGetBaz = hashTable.get('hash')
console.log('# result:', {
  result: resultGetBaz,
})

Agora, abre o terminal e executa o arquivo hash-table.js com o NodeJS:

node hash-table.js

Você deve ver algo parecido com isso no seu terminal:

# set: setting a new value on the hastable { index: 85, key: 'hello', value: 'world' }
# set: setting a new value on the hastable { index: 39, key: 'hash', value: 'table' }
 
# when getting "hello" from table, result should be = "world"
# get: getting the value from the hastable { index: 85, key: 'hello' }
# result: { result: 'world' }
 
# when getting "hash" from table, result should be = "table"
# get: getting the value from the hastable { index: 39, key: 'hash' }
# result: { result: 'table' }

Explicando:

• A gente adicionou dois elementos na nossa HashTable, um com a chave hello e valor world e outro com a chave hash e valor table
• Quando adicionamos, podemos ver nas 2 primeiras linhas o log que mostra o index, a chave e o valor que estamos adicionando, ou seja, quando vamos adicionar um novo item na nossa tabela, o index já é calculado e sabemos onde colocar o elemento na tabela, graças a nossa função _hash, esse log é mostrado 2 vezes, uma pra cada elemento que adicionamos ("hello" e "hash")
• Depois a gente faz um get de cada um desses elementos e vemos que o resultado é o esperado, o valor que a gente adicionou é o valor que a gente recebeu de volta, e podemos ver no log também que não precisamos percorrer toda a tabela pra encontrar "hello", a primeira coisa que o get faz é calcular o index e ir direto no index que a chave "hello" está, e o mesmo acontece com a chave "hash", nesse momento que vemos o poder das HashTables, imagina se tivesse 1 milhão de itens nessa tabela, se não fosse hash, a gente teria que percorrer sei lá quantos itens pra encontrar o valor, mas com hash, a gente vai direto no index que a chave tá.

Vou parar por aqui e deixar esse código pra você brincar e testar, se quiser, pode adicionar mais elementos, remover, etc... e se tiver alguma dúvida, só falar que a gente tenta se ajudar.

Aonde Você Pode Usar/Ver

Gerenciamento de Cache

Hash Tables são ideais para implementações de cache, porque em vez de realizar uma busca por varios elementos o index é calculado e já sabemos onde encontrar o elemento e se tratando de cache onde precisamos responder o mais rápido possível as Hash Tables caem como uma luva.

Evitar Items Duplicados

Se você tem alguma necessidade de evitar itens duplicados, as Hash Tables conseguem ser muito melhores pra evitar um item duplicado do que outras implementações normais de tabelas, pois se o hash for calculado e já tiver sendo usado você consegue saber que aquele item já existe antes de adicionar um duplicado.

Edge cases: colisão e objetos como chave

Duas chaves diferentes podem cair no mesmo bucket (colisão). Sem encadeamento ou probing, a segunda inserção sobrescreve a primeira — bug silencioso.

"Tá Jon, posso usar objeto {} como hash table?"

Pode, mas chaves são sempre string ([object Object] se você errar). Map aceita qualquer tipo de chave e é o padrão em Node.js moderno.

TL;DR — Hash table

Próximos passos

• Heaps (ep. 9): prioridade ordenada — Implementando Heaps
• Maps e Sets (ep. 11): API de alto nível em cima da mesma ideia — Implementando Maps e Sets

Antes de fechar

Onde você mais usa Map no trampo — cache, agrupamento, dedupe? Se viu cagada no post ou quer um follow-up só de colisões, comenta.