Hash tables versus binary trees?

Question

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL library implements dictionaries (they call them maps) using (balanced) binary search trees, and the .NET framework uses hash tables under the hood.> What are the advantages and disadvantages of these data structures? Is there some other option that is reasonable in certain situations?Note that I'm not particularly interested in cases where the keys have a strong underlying structure, say, they are all integers between 1 and n or something.

Answer 1

Binary search trees:

For using binary search trees, you need to make sure your customer ID is sortable. And to look up an ID, the response time is log(n). Plus you need to make sure your tree is balance while inserting new customer into the data structure.

Hash Table:

There are multiple ways to create a hash table. For instance, you can use array approach and map the object key into the bucket index, as long as you provide a hashCode() and equal() methods in your class.(The issue is, two object may have a same key, (you can do chaining, rehash, or multi-level hash.) If you can prevision your keys size, you can avoid collision. Getting a key in HashTable is O(c) cause your hashCode() provides the address of the object location in memory.