Big O of Hash Table vs binary search tree

Question

Will it take longer?

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

Will it take longer to print the hash table items in sorted order because the hash table is never sorted correctly? and BST is?

Answer 1

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

Please note, however, that in Java, for example, there is a LinkedHashSet and LinkedHashMap, which gives you some advantages of the Hash, but which can be traversed in the order in which it was added so that you can sort it and be able to go through it in this sorted order as well as hash extraction.

Answer 2

That's right, the hash table doesn't sort as you probably want. Items in the hash tables are not completely sorted, as a rule, although the location is often in the vicinity of the sort. But they are ordered according to a hash function, which is usually wildly different from similar phrases. This is not sorting by any metric that a person would use.

If the main thing you do with your collection is to print it in sorted order, you are better off using some type of BST.

Answer 3

The binary search tree is stored in such a way that if you perform the first pass of the depth, you will find the elements in sorted order (provided that you have a function for consistent comparison). Big O just returned the elements already in the tree, would be big O crossing the tree.

You are right in the hash tables, they are not sorted. In fact, to list everything in a simple hash table, you have to check each bucket to see what's there, pull it out, and then sort what you get. A lot of work to get a sorted list.

Answer 4

Correct, print sorted data stored in the hash table will be slower because the hash table does not sort the data. It just gives you a quick way to find a specific item. The Big O Notation says that an element can be found in constant time, i.e. Time O (1).

On the other hand, you can find the item in the binary search tree in “logarithmic time” (O (log n)), since the data has already been sorted for you.

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

Enjoy,

Robert C. Cartayneau

Answer 5

This raises some interesting questions. Is the search tree even faster considering the following?

• Including installation time for both a Hash table and a BST?
• If the hash algorithm creates a sorted list of words. Technically, you can create a hash table that uses an algorithm that does. In this case, the BST speed against the Hash table should decrease to the amount of time needed to fill the hash table in sorted order.

Answer 6

Also check out the relevant considerations for a skipped list and binary tree: Skip list against binary tree