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.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

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 ………