The most commonly used operations on any data structure are insertion, deletion, and searching. Hash Table is able to perform these three operations with the average time complexity of O(1), while self-balancing Binary Search Trees take O(log n) time complexity.
At first, it seems as Hash Tables are better than self-balancing BSTs in all the formats, as the time complexity of operations in Hash Table is less than that in BST. But there some conditions or requirements where we prefer BSTs over Hash Tables.
Advantages of BST over Hash Table
- Self-balancing binary search trees store the data in sorted form, that is, we can obtain the sorted data just by doing an in-order traversal in the BST. But in Hash Tables, we have to traverse all the elements and sort them using some sorting technique.
Time Complexity (Hash Table)= O(n log(n))
Time Complexity (BST) = O(n) - Find the maximum node, minimum node, node closest to given value or node just greater than a given value, etc. All the operations can be done in O(log n) time in a self-balancing binary search tree. But in the case of Hash Tables, we have to traverse all the elements to get the answer to the mentioned queries.
Time Complexity (Hash Table) = O(n)
Time Complexity (BST) = O(log n) - Implementation of customized Binary Search Tree is much simpler than the implementation of customized Hash Table. Different languages provide in-build libraries for the implementation of customized Hash Tables.
- The upper limit for all the operations like insert, delete, update, and search in a self-balancing Binary Search Tree is O(log n). But in the case of Hash Tables there is no upper bound. The operations take place at an average complexity of O(1) but in some cases, the complexity might increase. The increase may occur due to the way in which the library implements the Hash Table. Especially, when hash table resizing is done, it is a very costly operation.
So both Binary Search Trees and Hash Tables have their own advantages in different situations. Depending on the requirements one must choose between a Binary Search Tree and a Hash Table.