compare Hash with Binary search tree
We all know that a hash table has O(1) time for both inserts and look-ups if the hash function was well chosen. So, what are the reason we want to use Binary Search Tree? Just because a perfect hash function was hard to design?
Here how I come up with this question?
I notice that Standard C++ STL has set and map which are implemented with Binary search tree ,but has no hash (not talking about non-stardard hash_set , hash_map). While, Ruby has only Hash. I want to understand the rational behind this difference.
Answer
Trees allow in-order traversion.
The worst case performance for a hash table is O(N) (linear search through one bucket), a binary search is bound by O(log N).
NB: this requires the tree to be balanced - that's why typical implementation use a self-balancing tree, suhc as a red-black tree.
While such a degradation is unlikely, it is not impossible and depends strongly on the ability to chose an appropriate hash function and the distribution of the actual data.
A tree implementation also grows trivially to the required size, whereas a hashmap starts to degrade when it gets full (for most implementations, it's said around 70% of the buckets filled). You either need to rehash the entire table (again, bad fo real time apps), or incrementally move to a new table, which is not a simple implementation.
In the end, STL probably just went with one "base" container template, the tree, to avoid the additional implementation complexity.