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).

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.

Answer 4

Correct, printing sorted data stored in a hash table would be slower because a hash table is not sorted data. It just gives you a quick way to find a particular item. In "Big O Notation" it is said that the item can be found in constant time, i.e. O(1) time.

On the other hand, you can find an item in a binary search tree in "logarithmic time" (O(log n)) because the data has already been sorted for you.

So if you goal is to print a sorted list, you are much better off having the data stored in a sorted order (i.e. a binary tree).

Enjoy,

Robert C. Cartaino

Answer 5

This brings up a couple of interesting questions. Is a search tree still faster considering the following?

1. Incorporating the setup time for both the Hash Table and the BST?
2. If the hash algorithm produces a sorted list of words. Technically, you could create a hash table which uses an algorithm which does. In which case the the speed of the BST vs the Hash table would have to come down to the amount of time it takes to fill the hash table in the sorted order.

Answer 6

Also check out related considerations of Skip List vs. Binary Tree: http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree