Como funciona uma tabela hash?

Uma tabela de dispersão (hash table) é uma estrutura de dados que implementa um array associativo.

Princípio de funcionamento:

1. Hashing. Para cada chave (key), calcula-se um código de hash (hash code) usando uma função de hash (hash function). O código de hash é um número inteiro.
2. Indexação. O código de hash é usado para determinar um índice (index) no array (ou vetor) da estrutura interna da tabela de dispersão. Normalmente, o índice é calculado como hash_code % tamanho_do_array, onde tamanho_do_array é o tamanho do array.
3. Armazenamento. No índice encontrado, armazena-se o valor (value) associado à chave.

Problemas e soluções:

• Colisões. Chaves diferentes podem gerar o mesmo código de hash e, consequentemente, o mesmo índice no array. Isso é chamado de colisão.
  • Métodos para resolver colisões:
    • Método de encadeamento (Separate Chaining): Em cada célula do array, armazena-se uma lista (lista, vetor, etc.) de pares "chave-valor". Em caso de colisão, o novo par é adicionado a essa lista. Para procurar por índice, percorre-se a lista correspondente para encontrar a chave desejada.
    • Método de endereçamento aberto (Open Addressing): Em caso de colisão, busca-se outra célula livre no array seguindo uma regra determinada (sondagem).
      • Sondagem linear (Linear Probing): Verificam-se sequencialmente as células index + 1, index + 2, etc., módulo o tamanho do array.
      • Sondagem quadrática (Quadratic Probing): Verificam-se as células index + 1^2, index + 2^2, etc., módulo o tamanho do array.
      • Doble hashing (Double Hashing): Usa-se uma segunda função de hash para determinar o passo da sondagem.

Vantagens:

• Em média, as operações de inserção, remoção e busca são realizadas com complexidade O(1).

Desvantagens:

• No pior caso (por exemplo, muitas colisões ou má função de hash), a complexidade pode atingir O(n), onde n é o número de elementos.
• Requer memória adicional (por exemplo, para listas no método de encadeamento ou para sondagem no endereçamento aberto).

Exemplo de uso em C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Criação da tabela de dispersão (unordered_map)
    std::unordered_map<std::string, int> idades;

    // Inserção de elementos
    idades["Alice"] = 30;
    idades["Bob"] = 25;
    idades["Charlie"] = 35;

    // Obter valor pela chave
    std::cout << "Idade de Alice: " << idades["Alice"] << std::endl;

    // Procurar elemento
    if (idades.count("Bob")) {
        std::cout << "Bob está na tabela." << std::endl;
    }

    // Remover elemento
    idades.erase("Charlie");

    return 0;
}