Battle of the Maps – HashTable vs HashMap vs TreeMap vs LinkedHashMap

Map Overview

There are 4 commonly used implementations of Map in Java SE – HashMap, TreeMap, Hashtable and LinkedHashMap.

All four classes implement the Map interface and offer mostly the same functionality. If we use one sentence to describe each implementation, it would be the following:

  1. HashMap is implemented as a hash table, and there is no ordering on keys or values.
  2. TreeMap is implemented based on red-black tree structure, and it is ordered by the key.
  3. LinkedHashMap preserves the insertion order
  4. Hashtable is synchronized, in contrast to HashMap.

This gives us the reason that HashMap should be used if it is thread-safe, since Hashtable has overhead for synchronization.

Some more differences between these data-structures in java are as follows –

  • Hashtable is the generic name for hash-based maps. In the context of the Java API, Hashtable is an obsolete class from the days of Java 1.1 before the collections framework existed. It should not be used anymore, because its API is cluttered with obsolete methods that duplicate functionality, and its methods are synchronized (which can decrease performance and is generally useless). Use ConcurrrentHashMap instead of Hashtable.
    • same as hash map
    • it does not allows null keys and null values
  • HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.
    • It has pair values(keys,values)
    • NO duplication key values
    • unordered unsorted
    • it allows one null key and more than one null values
    • Size : [32 * SIZE + 4 * CAPACITY bytes]
  • TreeMap will iterate according to the “natural ordering” of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order.
    • Ordered and sortered version
    • based on hashing data structures
    • Size : [40 * SIZE bytes]
  • LinkedHashMap will iterate in the order in which the entries were put into the map
    • It is ordered version of map implementation
    • Based on linked list and hashing data structures
    • Size : [40 * SIZE + 4 * CAPACITY bytes]


Visual presentation:


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s