# What are the differences between a hash table and a binary search tree? Suppose that you are trying to figure out which of those data structures to use when designing the address book for a cell phone that has limited memory. Which data structure would you use?

A hash table can insert and retrieve elements in O(1) (for a big-O refresher read here). A binary search tree can insert and retrieve elements in O(log(n)), which is quite a bit slower than the hash table which can do it in O(1).

## A hash table is an unordered data structure

When designing a cell phone, you want to keep as much data as possible available for data storage. A hash table is an unordered data structure – which means that it does not keep its elements in any particular order. So, if you use a hash table for a cell phone address book, then you would need additional memory to sort the values because you would definitely need to display the values in alphabetical order – it is an address book after all. So, by using a hash table you have to set aside memory to sort elements that would have otherwise be used as storage space.

## A binary search tree is a sorted data structure

Because a binary search tree is already sorted, there will be no need to waste memory or processing time sorting records in a cell phone. As we mentioned earlier, doing a lookup or an insert on a binary tree is slower than doing it with a hash table, but a cell phone address book will almost never have more than 5,000 entries. With such a small number of entries, a binary search tree’s O(log(n)) will definitely be fast enough. So, given all that information, a binary search tree is the data structure that you should use in this scenario, since it is a better choice than a hash table.

Subscribe to our newsletter for more free interview questions.

• Nicely and precisely explained.. Regards

• Wizzard

Wrong. It’s O(1) that’s the whole purpose for hashing.
It actually can be O(n) when your hashing function has a 100% collision probability.

• Luca

Actually the hash table search is O(n) not O(1)

• Divya

Good explanation

• venkatesh

http://www.sparknotes.com/cs/searching/hashtables/section1.html

more about hash table can be also found here

• Rambabu

Very nice article!

• ganesh

thanks

• K C Rana

thanks ………