Binary Search Tree vs Hash Table

In the Concept of Hashing in programming, blog, we learned the concept of Hashing. So, now we know the concepts of both the hash tables and of binary search trees also. So, which data structure should be used? Should we use the Hash Table or BST? Let's find out.

Comparison: BST vs HashTable

When to use which data structure?

So we have seen the differences between the Binary Search Tree and Hash Table. Now, the question that arises here is that when should we use BST over Hash Table and where should we prefer Hash Table over BST? Should we always use a Hash Table because the time complexity of insertion, deletion, and searching is O(1) or we should use BST?

The usage of BST and Hash Table depends on the need of the situation. Let's see how!

• The input size is known: If the input size is known then we can use the hash table and make some hash function that will generate the key uniformly. If the input size is not known to you in advance, then use the Hash Table.
• Range Search: If you want to perform range search i.e. searching some key in between some keys, then you should go with Binary Search Tree because, in Binary Search Tree, you ignore that subtree which is impossible to have the answer.
• Cache friendly: If you want to make some cache-friendly application, then you should go with the Hash Table because it requires less memory reads.
• Hash Function: Hash functions are the most important part of the Hash Table. So, if your Hash Function is such that it uniformly distributes the keys, then you should go with the Hash Table. But if you are finding it hard to make some Hash Function, then go for Binary Search Tree.

Conclusion

If you know the size of the input, then you can use the Hash Table. But if you are not sure about the input size, then you should go with BST. Also, if you are not so familiar with the input size, but after inserting all the data, the operation that you are following is retrieval, deletion, then you should use the Hash Table. But if you are continuously inserting, updating, deleting, and retrieving data, then go for BST.

Therefore, the use of Hash Table and BST depends on the problem at hand!

That's it for this blog.

Happy Learning, Enjoy Algorithms!

Team AfterAcademy!