5

I have a confusion:

I have read in many posts that Hash-maps are implemented as binary search trees which makes the various operations time complexity of logarithmic order.

Hashtables on the other hand provide constant time fetching.

But, as I read in this post, no difference has been provided in terms of the complexity for retrieval/searching of elements in the two data structures.

So, here is my question-

Since hashtables are guaranteed to provide constant searching time complexity, their implementation must differ from those of hash-maps. So, why will someone ever use hash-maps if they do not provide constant time searching. Also, why in the first place, they are implemented as binary search trees?

I know hash maps store the keys in sorted form and provide iteration through the map. But, the same could also be provide in the hashtable too.

Community
  • 1
  • 1
Sankalp
  • 2,718
  • 2
  • 28
  • 42
  • 1
    Before you retagged it, the question mentioned neither Java nor C++, but used Java terminology throughout and linked to a question that was specifically about Java. It would help avoid confusion if you tagged questions appropriately from the get-go (and ideally used standard terminology for the language you're asking about). – NPE May 18 '13 at 05:11

1 Answers1

8

Your confusion stems from the following:

Hash-maps are implemented as binary search trees

They are not. No sensible naming convention would use the term "hashmap" to describe a structure based on a tree.

For example, in Java, HashMap is based on a hash table and TreeMap is based on a tree.

C++ uses neither "hash" nor "tree" in the naming of its standard containers. The two containers that broaly correspond to HashMap and TreeMap are std::unordered_map and std::map.

Gabriel Staples
  • 22,024
  • 5
  • 133
  • 166
NPE
  • 464,258
  • 100
  • 912
  • 987