I'm trying to understand what is the advantage of a Binary Search Tree (BST) over a hash table whose collisions-managing is taken care of using BST.
In many places over the Internet I see that hash table is bad if you want to iterate over all the elements whose keys are within a certain range.
But why? I mean, why it is usual to use unordered keys instead of ordered keys? Why Isn't that a simple feature that the hash function could support (e.g., as said here)
Hash functions are meant to be as random as possible, so if they give you ordered keys (while it would be super useful for some things) it would kind of defeat the purpose of randomization and you'd most likely get more collissions than you would expect otherwise.
BST are better for sorting data because... well it gets sorted when you put it in there by default. It's possible to keep the data you put into a hashtable ordered in a seperate data structure (ex. put only the keys into a BST), so that way you have it sorted somewhere AND you get O(1) search time in your hashtable. But of course that requires you to implement another data structure, up more memory, perform additional operations, etc.
In conclusion: If you're going to rely heavily on the data being sorted and want to use relatively a lot of the data, a lot of the time, go with a BST. Otherwise, if you want to get specific things from your data structure very quickly, go with a HashTable (possibly with a BST of keys if you aren't worried about using memory).
There is no advantage of BST over hash table, depending of the use case you will select one or the another. If you look at Hash table, you can see that
A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
Since the index in the array is calculated and there are various hash functions, that means that no order of keys is guaranteed. Thus, you have to iterate over all indexes to find a given one.
Binary search tree compares keys to place them in the right place, so there is order of keys in BST; thus, one can iterate over range of keys.
On a hash table you don't have any control where the items are going to be placed so the only way to iterate them in the right order is to scan the entire list every time and find out the next element.
Hash table are good since the insertion time and retrieve time complexity is usually O(1) (plus collisions of course). Range iteration is very inefficient
BST insertion/retrieve time is O(Log(N)). Range iteration is efficient.
