Qual é o princípio de funcionamento de uma tabela hash?

Uma tabela de hash (ou matriz associativa) armazena pares de "chave-valor". O princípio de funcionamento baseia-se no uso de uma função de hash, que transforma a chave num índice numérico (hash), indicando o local de armazenamento do valor na matriz (cesto).

Passos:

1. Cálculo do hash: Para uma chave dada, calcula-se o hash.

   <?php
   $key = "example";
   $hash = crc32($key); // Exemplo de uma função de hash simples
   

2. Determinação do índice: O hash é transformado num índice da matriz, geralmente usando a operação módulo do tamanho da matriz.

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Acesso ao cesto: Acedemos ao cesto correspondente na matriz usando o índice calculado.
4. Resolução de colisões: Como diferentes chaves podem ter o mesmo hash (colisão), o cesto pode conter várias pares "chave-valor". Para resolver colisões, utilizam-se diferentes métodos:
   • Método de encadeamento (Separate Chaining): Cada cesto armazena uma lista (por exemplo, uma lista ligada) de pares "chave-valor" cujos hashes coincidem.
   • Método de endereçamento aberto (Open Addressing): Em caso de colisão, realiza-se uma busca repetida por uma célula livre na matriz segundo uma regra determinada (sondagem linear, quadrática, duplo hashing).

Operações:

• Inserção: Calcula-se o hash da chave, determina-se o índice, e o par "chave-valor" é colocado no cesto correspondente. Em caso de colisão, é adicionado à lista (encadeamento) ou procura-se um lugar livre (endereçamento aberto).
• Procura: Calcula-se o hash da chave, determina-se o índice. No cesto correspondente, procura-se o valor pela chave. No método de encadeamento, percorrem-se os elementos da lista; no endereçamento aberto, realiza-se uma busca sequencial.
• Remoção: Calcula-se o hash da chave, determina-se o índice. No cesto correspondente, encontra-se e remove-se a par pela chave.

Vantagens:

• Acesso rápido aos elementos (em média O(1)).
• Uso eficiente de memória.

Desvantagens:

• O desempenho pode deteriorar-se com um grande número de colisões.
• O tamanho da tabela pode requerer ajuste (rehashing) para manter a eficiência.