Menu
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.
283
HashMap is non-syncronized and is not thread safe while HashTable is thread safe and is synchronized. HashMap allows one null key and values can be null whereas HashTable doesn't allow null key or value. HashMap is faster than HashTable. HashMap iterator is fail-safe where HashTable iterator is not fail-safe.
HashMap is faster than Hashtable due to the fact that Hashtable implicitly checks for synchronization on each method call even in a single thread environment. HashMap allows storing null values, while Hashtable doesn't. HashMap can be iterated by an Iterator which is considered as fail-fast .
You can use one null key and which kind of null values you want for HashMap but Hashtable does not allow null key or null values. Basically under HashSet is working HashMap where value is Object hence HashSet values are unique because HashMap keys are unique.
HashMap is a non-synchronized class of the Java Collection Framework that contains null values and keys, whereas Map is a Java interface, which is used to map key-pair values.
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.
160
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
