Tabelas Hash

Dificuldade ★★☆

5 minutos de Leitura 🕒

O que é uma Tabela Hash?

Uma Tabela Hash (Hash Table) é uma estrutura de dados não linear que mantém uma coleção associativa de elementos chave-valor. Essa estrutura possibilita a recuperação eficiente de dados.

Onde Tabelas Hash são Usados?

  • Indexação e Busca - Tabelas Hash são ideais para implementar estruturas de indexação, onde as chaves são usadas para recuperar rapidamente os valores associados. Por exemplo, em mecanismos de busca, uma tabela hash pode ser usado para mapear palavras-chave para documentos relevantes, permitindo uma busca rápida e eficiente.

  • Implementação de Caches - Tabelas Hash são usados em sistemas cache para armazenar resultados pré-computados ou dados frequentemente acessados, onde as chaves são usadas para identificar os itens armazenados. Dessa forma, os valores podem ser rapidamente recuperados, em vez de recalculados ou buscados em um local mais lento.

Quais são as operações básicas de uma Tabela Hash?

  • inserir() adiciona um novo valor à tabela hash.
  • remover() exclui um valor da tabela hash.
  • recuperar() recupera o valor associado a uma chave existente na tabela hash.

Como implementar uma Tabela Hash?

uma tabela hash pode ser implementado como um arranjo de elementos chave-valor e uma função de mapeamento, ou função hash, que mapeia um valor à uma chave.

ESTRUTURA Chave-Valor
    Identificador: chave
    Dado: valor

ESTRUTURA TabelaHash
    Chave-Valor[]: elementos[]
    Função: hash(ChaveValor)

Operação Inserir

FUNÇÃO inserir(TabelaHash: tabelaHash, Valor: dado):
    // Calcular o hash do valor para obter a chave de acesso.
    Identificador chave = tabelaHash.hash(valor)

    // Verificar se a chave está presente na tabela hash.
    SE a chave está presente na tabela hash:
        // Se estiver, tratar conflito ou retornar "valor presente na tabela hash".
        RETORNAR "valor presente na tabela hash"
    SENÃO:
        // Se não estiver, inserir valor na tabela hash e retornar a chave de acesso.
        dicionario.elementos[chave] = valor
        RETORNAR chave

Operação Remover

FUNÇÃO remover(TabelaHash: tabelaHash, Identificador chave):
    // Verificar se a chave está presente na tabela hash.
    SE a chave está presente na tabela hash:
        // Se estiver, remover o valor correspondente da tabela hash.
        remover(tabelaHash.elementos[chave])
    SENÃO:
        // Se não estiver, retornar "chave não encontrada".
        RETORNAR "chave não encontrada"

Operação Recuperar

FUNÇÃO RECUPERAR(TabelaHash: tabelaHash, Identificador: chave):
    // Verificar se a chave está presente na tabela hash.
    SE a chave está presente na tabela hash:
        // Se estiver, retornar valor correspondente.
        RETORNAR tabelaHash.elementos[chave]
    SENÃO:
        // Se não estiver, retornar "chave não encontrada".
        RETORNAR "chave não encontrada"

Como escolher a função hash de uma Tabela Hash?

A função hash de uma tabela hash é usado na operação inserir() para computar uma chave de acesso a partir do valor sendo inserido na tabela hash. A escolha de uma função hash adequada consiste em um ponto central do projeto de uma Tabela Hash. Algumas considerações são:

  • Eficiência - A função hash deve ser eficiente para calcular, para que não se torne um gargalo nas operações da tabela hash.

  • Baixa Chance de Colisões - A função hash deve ser capaz de retornar chaves de acesso únicas para quaisquer valores diferentes. Caso contrário, ocorrerá um conflito e o desempenho da tabela hash será impactado negativamente.

Como resolver conflitos em uma Tabela Hash?

Em uma tabela hash, um conflito (ou colisão) ocorre quando dois valores são mapeados para a mesma chave de acesso. Para possibilitar que valores conflitantes sejam armazenados simultaneamente em uma tabela hash, uma técnica de resolução de conflitos deve ser adotada. Existem duas abordagens para isso:

  • Encadeamento (Chaining) - Nessa abordagem, cada posição da tabela hash mantém uma estrutura de dados adicional, como uma lista encadeada, que contém os valores que colidem. Quando ocorre uma colisão, o novo valor é simplesmente adicionado a essa estrutura de dados adicional na posição correspondente. Dessa forma, vários valores podem ser armazenados na mesma chave de acesso da tabela hash. Ao buscar um valor, a chave é calculada, e em seguida, é feita uma busca na estrutura de dados adicional para encontrar o valor correto.

  • Resolução por Sondagem (Probing): Nessa abordagem, quando ocorre uma colisão, uma nova posição é calculada com base na posição original do índice. Nesse caso, a nova posição pode ser calculada por diferentes métodos:

    • Sondagem Linear: Nesse método, o algoritmo verifica as posições subsequentes até encontrar uma posição vazia para inserir o novo valor.

    • Sondagem Quadrática: Nesse método, o algoritmo utiliza uma função de sondagem quadrática para calcular as novas posições após uma colisão. A função de sondagem pode ser algo como: chave = (chave + i^2) % tamanho_da_tabela_hash, onde i representa o número de tentativas.

    • Sondagem Duplamente Hashed: Nesse método, o algoritmo utiliza duas funções de hash para calcular as novas posições após uma colisão. Isso ajuda a distribuir melhor os pares chave-valor na tabela hash e reduzir colisões.

Qual o desempenho de uma Tabela Hash?

Uma implementação eficiente de Tabela Hash para resolução de conflitos entrega uma complexidade computacional constante para as operações básicas de inserção, remoção e recuperação:

  • Inserção: O(1) comparações
  • Remoção: O(1) comparações
  • Recuperação: O(1) comparações