A tabela de hash suporta as seguintes operações em tempo Θ (1).
1) Pesquisar
2) Inserir
3) Excluir

A complexidade de tempo das operações acima em uma árvore de busca binária de auto-equilíbrio (BST) (como Red-Black Tree , AVL Tree , Splay Tree , etc) é O (Logn).

Portanto, o Hash Table parece superar o BST em todas as operações comuns. Quando devemos preferir BST em vez de tabelas de hash, quais são as vantagens. A seguir estão alguns pontos importantes em favor dos BSTs.

1. Podemos obter todas as chaves em ordem apenas fazendo Inorder Traversal do BST. Esta não é uma operação natural em tabelas de hash e requer esforços extras.
2. Fazer estatísticas de pedidos , encontrar os elementos mais baixos e maiores mais próximos , fazer consultas de intervalo são fáceis de fazer com BSTs. Assim como a classificação, essas operações não são uma operação natural com tabelas de hash.
3. Os BSTs são fáceis de implementar em comparação com o hashing, podemos implementar facilmente nosso próprio BST personalizado. Para implementar o Hashing, geralmente contamos com bibliotecas fornecidas por linguagens de programação.
4. Com os BSTs de auto-balanceamento, todas as operações têm a garantia de funcionar no tempo O (Logn). Mas com o Hashing, Θ (1) é o tempo médio e algumas operações específicas podem ser caras, especialmente quando ocorre o redimensionamento da tabela.

Este artigo é uma contribuição de Himanshu Gupta . Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima