O que é uma tabela hash?

Uma tabela de dispersão (ou matriz associativa, dicionário) é uma estrutura de dados que implementa a interface de matriz associativa, ou seja, permite armazenar pares "chave-valor" e realizar buscas rápidas do valor pela chave.

O princípio de funcionamento baseia-se no uso de uma função de dispersão, que transforma a chave em um índice (hash) dentro do array (ou balde).

Operações principais:

1. Inserção: Calcula-se o hash da chave, e o par "chave-valor" é colocado no balde correspondente.
2. Remoção: Calcula-se o hash da chave, encontra-se o balde correspondente, e o par é removido.
3. Busca: Calcula-se o hash da chave, encontra-se o balde correspondente, e busca-se o par com a chave desejada.

As tabelas de dispersão oferecem, em média, alto desempenho para operações de inserção, remoção e busca (idealmente $O(1)$). No entanto, no pior caso (quando há muitas colisões, ou seja, diferentes chaves que se transformam no mesmo índice), o desempenho pode diminuir para $O(n)$.

Existem várias estratégias para resolver colisões:

• Método de encadeamento (Separate Chaining): Cada balde armazena uma lista (por exemplo, uma lista ligada) de elementos com o mesmo hash.
• Endereçamento aberto (Open Addressing): Quando ocorre uma colisão, a busca por um espaço livre é feita por um algoritmo predefinido (sondagem linear, quadrática, etc.).

Exemplo conceitual (simplificado):

// Exemplo de função de dispersão simplificada
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Transformação em inteiro de 32 bits
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Método de encadeamento
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Verifica se a chave já existe para atualizar o valor
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Chave não encontrada
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Removido com sucesso
      }
    }
    return false; // Chave não encontrada
  }
}

// Uso
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

Em JavaScript, objetos ({}) e mapas (Map) são exemplos de implementações de tabelas de dispersão. Map é frequentemente preferido, pois suporta chaves de qualquer tipo e mantém a ordem de inserção.

Propriedades de uma boa função de dispersão:

• Cálculo rápido.
• Distribuição uniforme de hashes para diferentes chaves.
• Minimização de colisões.