O que é uma tabela hash?

Uma tabela de hash, ou matriz associativa, é uma estrutura de dados que implementa a interface de matriz associativa, ou seja, relaciona chaves com valores. Utiliza uma função hash para calcular um índice, ou "hash", da caixa ou slot onde o valor procurado deve estar.

Componentes principais:

• Chave: Identificador único do elemento.
• Valor: Dados associados à chave.
• Função hash: Converte a chave num valor (hash), que é usado para determinar o índice da caixa.
• Caixas (Buckets): Array onde são armazenados pares chave-valor.
• Gestão de colisões: Mecanismo para resolver situações em que diferentes chaves geram o mesmo hash (e, portanto, apontam para a mesma caixa). Métodos comuns:
  • Encadeamento: Cada caixa armazena uma lista (por exemplo, lista ligada) de elementos cujos hashes apontam para essa caixa.
  • Endereçamento aberto: Em caso de colisão, procura-se a próxima caixa livre usando algoritmos como hashing linear, quadrático ou duplo hashing.

Princípio de funcionamento:

1. Inserção: A função hash é aplicada à chave para obter o hash. O hash é usado para determinar o índice da caixa. O par chave-valor é armazenado nessa caixa. Em caso de colisão, aplica-se o método de gestão de colisões.

   // Exemplo de inserção numa tabela de hash (encadeamento)
   function insert(key, value) {
     const hash = hashFunction(key); // Calcula o hash
     const bucketIndex = hash % tableSize; // Determina o índice da caixa
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Cria a lista se ainda não existir
     }
     buckets[bucketIndex].push({ key, value }); // Adiciona o par à lista
   }
   

2. Procura: A função hash é aplicada à chave para obter o hash. O hash é usado para determinar o índice da caixa. Depois, nessa caixa, procura-se o elemento com a chave dada. No método de encadeamento, procura-se na lista dentro da caixa. No endereçamento aberto, verifica-se sucessivamente outras caixas até encontrar o elemento ou determinar que não existe.

   // Exemplo de procura numa tabela de hash (encadeamento)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Calcula o hash
     const bucketIndex = hash % tableSize; // Determina o índice da caixa
   
     if (buckets[bucketIndex]) {
       // Procura na lista da caixa
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Se for necessário remover
           return value; // Retorna o valor
         }
       }
     }
     return undefined; // Elemento não encontrado
   }
   

Vantagens:

• Operações de inserção, procura e remoção rápidas em média (O(1)).
• Uso eficiente de memória em comparação com um array de endereços diretos (se as chaves estiverem dispersas).

Desvantagens:

• O desempenho pode diminuir em caso de muitas colisões (no pior caso O(n)).
• A ordem de inserção dos elementos não é mantida.
• Requer uma boa função hash para uma distribuição uniforme das chaves.

Em JavaScript, as tabelas de hash são implementadas pelo objeto embutido Map e, historicamente, Object. Map é preferido, pois permite usar qualquer tipo de dado como chave e mantém a ordem de inserção. Object converte todas as chaves em strings.