8

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,796
  • 3
  • 30
  • 43
  • 2
    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

9

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
  • 36,492
  • 15
  • 194
  • 265
NPE
  • 486,780
  • 108
  • 951
  • 1,012