HashMap VS BST

Advantages of BST over Hash Table

Summary:

1 - Order

2- Easy to implement

3- self-balance BST worst case O(logN), Hash resizing table O(n)

4-the worst-case guarantee on the running time - Real Time Application

5- Space

Hash Tablesupports following operations in Θ(1) time.
1) Search
2) Insert
3) Delete

The time complexity of above operations in a self-balancingBinary Search Tree (BST)(likeRed-Black Tree,AVL Tree,Splay Tree, etc) is O(Logn).

So Hash Table seems to beating BST in all common operations. When should we prefer BST over Hash Tables, what are advantages. Following are some important points in favor of BSTs.

1. We can get all keys in sorted order by just doing Inorder Traversal of BST. This is not a natural operation in Hash Tables and requires extra efforts.
2. Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs. Like sorting, these operations are not a natural operation with Hash Tables.
3. BSTs are easy to implement compared to hashing, we can easily implement our own customized BST. To implement Hashing, we generally rely on libraries provided by programming languages.
4. With Self-Balancing BSTs, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.

1. When you care about the order of the keys and want to use it for some operations.
2. When you need the worst-case guarantee on the running time. Especially when the requests are coming from outside, and you don’t control or restrict them in any way, an adversary could potentially make your service respond very slowly if you use a hash table
3. When you want some tricky operations to work fast, like cutting a segment from a string and then inserting it back at another position
4. Another reason you might use a balanced tree for an unordered set is if you're working on some kind of real-time application. A hash table will use O(n) time for a single operation when a table resize must be performed. Though this happens infrequently, this kind of slow operation might be a problem for a real-time application that needs to have sub-millisecond responsiveness.
5. Hash tables don't fit very well into the framework of functional languages with no mutable state, so those languages often use balanced trees for unordered sets as well.If you are constantly adding and removing items to and from the collection, then a binary search tree tends to be a better bet
6. Moving all the items to a larger container in the hash-map takes O(n) time
7. Removing items from a hash-map doesn’t free up as much memory as removing them from a binary-search-tree. Unless you place the remaining items in a smaller (pre-sized) container, which would take O(n) time to do.