Java provides a rich library of different data structures to store and perform operations on those data. Java collection framework classes HashMap, LinkedHashMap, TreeMap, and HashTable provides an implementation of Map interface. All these are used as key and value store data structures. The map is the most used collection class after arrays and lists.

Map-based classes used to store data based on key and value, these classes provide fast searching based on key along with several other functionalities. They why these 4 flavors of Map implementation?

Key Differences Between Java Provided Map Classes

HashMap

• It contains values based on the key.
• It contains only unique elements.
• It may have one null key and multiple null values.
• It maintains no order.
• This extends AbstractMap class which implements Map interface

LinkedHashMap

• It has all the properties except no order.
• LinkedHashMap maintains the insertion order of elements as specified during the object construction. You can also specify accessOrder parameter to true, then it will maintain item order as they accessed. This makes it the most efficient class to implement LRU cache.
• For maintaining order it uses a doubly-linked list, which is an extra resource uses for maintaining before and after pointers.

TreeMap

• A TreeMap implemented using a Red-Black binary search tree.
• It contains values based on the key. It implements the NavigableMap interface, SortedMap and extends AbstractMap class.
• It contains only unique elements.
• It cannot have the null key but can have multiple null values.
• It has the same functionality as HashMap instead maintains ascending order(Sorted using the natural order of its key.) or based on the implementation of Comperator interface of key object.

HashTable

• A Hashtable is an array of lists. Each list is known as a bucket. The position of the bucket is identified by calling the hashcode() method.
• A Hashtable contains values based on the key.
• It contains only unique elements.
• It may have not had any null key or value.
• It is synchronized.
• It is a legacy class.

Performance Comparison

Search wise HashMap, LinkedHashMap and HashTable have the same performance as O(1). Only TreeMap has O log(n).

How to decide between these?

As per the above comparison for general-purpose key-value store, one should always use HashMap as this is the fastest one and in the case of synchronized application, one should use ConcurrentHashMap instead of HashTable as HashTable is deprecated now.

LinkedHashMap should be used only when we want iteration in order of insertion of sorted as it has two extra pointer overhead. For example, we can easily implement an efficient LRU cache using LinkedHashMap.

TreeMap should be used when we want to iterate in sorted order of key and additionally we need to navigate based on keys and function of NavigationMap interface.