Qual é a velocidade de funcionamento da tabela de hash?

A velocidade de trabalho de uma tabela hash, ou o tempo de acesso aos dados (procura, inserção, remoção), no melhor caso é O(1) — constante.

Isto é alcançado através do uso de uma função hash que transforma rapidamente a chave em um índice de array.

A velocidade real depende de:

• A qualidade da função hash: Uma boa função distribui as chaves uniformemente, minimizando colisões.
• As estratégias de resolução de colisões:
  • Encadeamento separado (separate chaining): Em caso de colisão, os elementos com a mesma hash são armazenados numa lista ligada ou noutro array dinâmico. O tempo de acesso pode chegar a O(N) no pior caso (todos os elementos na mesma "cesta"), onde N é o número de elementos.
  • Endereçamento aberto (open addressing): Em caso de colisão, procura-se a próxima célula livre no array. O tempo de acesso também pode piorar com muitas colisões.
• O fator de carga (load factor): A relação entre o número de elementos e o tamanho da tabela hash. Um fator de carga elevado aumenta a probabilidade de colisões e diminui a performance. Quando um limite é atingido, é necessário rehashing (aumentar o tamanho da tabela e recalcular os hashes de todos os elementos), o que é uma operação relativamente cara (O(N)).

Portanto, embora a velocidade teórica O(1) seja o melhor caso, na prática ela pode ser um pouco maior devido às colisões e à necessidade de rehashing, especialmente com grandes volumes de dados ou funções hash não eficientes.