Big O of Hash Table vs. Binary Search Tree

Question

Which would take longer?

print all items stored in a binary search tree in sorted order or print all items stored in a hash table in sorted order.

It would take longer to print the items of a hash table out in sorted order because a hash table is never sorted correct? and a BST is?

Answer 1

You are correct. Hashtables are sorted by some hash function, not by their natural sort order, so you'd have to extract all the entries O(N) and sort them O(NlogN) whereas you can traverse a binary search tree in natural order in O(N).

Note however that in Java, for instance, there is a LinkedHashSet and LinkedHashMap which gives you some of the advantages of Hash but which can be traversed in the order it was added to, so you could sort it and be able to traverse it in that sorted order as well as extracting items by hash.

Answer 2

Correct, a hash table is not "sorted" in the way you probably want. Elements in hash tables are not quite fully sorted, usually, although the arrangement is often kind of in the neighborhood of a sort. But they are arranged according to the hash function, which is usually wildly different for similar phrases. It's not a sort by any metric a human would use.

If the main thing you are doing with your collection is printing it in sorted order, you're best off using some type of BST.

Answer 3

A binary search tree is stored in a way that if you do a depth first traversal, you will find the items in sorted order(assuming you have a consistent compare function). The Big O of simply returning items already in the tree would be the Big O of traversing the tree.

You are correct about hash tables, they are not sorted. In fact, in order to enumerate everything in a plain hash table, you have to check every bucket to see what is in there, pull it out, then sort what you get. Lots of work to get a sorted list out of that.