Difference between HashMap, LinkedHashMap, and TreeMap

java

map-implementation

data-structures

time-complexity

byAnton Shumikhin·Sep 2, 2024

Load up on Java Maps insight here! HashMap is your fastest, unordered associate—O(1) for get and put. LinkedHashMap is a reliable friend, always remembering the insertion order but cost you a smidge more in memory. Finally, the sophisticated TreeMap sorts keys by their natural order or supplied Comparator, but at a small price: O(log n) for get and put.

HashMap<Integer, String> hashMap = new HashMap<>();
LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();
TreeMap<Integer, String> treeMap = new TreeMap<>();

hashMap.put(1, "One Single Map");     // A: "What did one map say to another?" B: "I'm 'hash'ing you out, bro!"
linkedHashMap.put(2, "Linked Twice"); // Oh no! 2 Chainz started rapping in Java 😉
treeMap.put(3, "Tree's Company");     // Unlike in sitcoms, 3's company here 

System.out.println(hashMap.keySet());       // Output: [A random number that identifies as 1]
System.out.println(linkedHashMap.keySet()); // Output: [2, or so it says]
System.out.println(treeMap.keySet());       // Output knows its place: [3]

HashMap: Quick as a hare, but don't ask about order. LinkedHashMap: Loyal to order but takes an extra byte. TreeMap: Look no further for sorted keys and range queries.

Selecting the Right Map for your Needs

To choose the optimal map, reflect on these guiding lights:

Order: If the sequence is vital, let LinkedHashMap serve. If you need a sorted setup, ask TreeMap.
Performance: For lighting look-ups, HashMap shines. If you exchange speed for sorted operations, TreeMap is your map.
Null-Acceptance: Fancy null as a key? HashMap and LinkedHashMap say yes. TreeMap though, is nullophobic with keys, but cool with null values.

For cache implementations, where elder entries must go, an access-order configured LinkedHashMap pulls the strings.

With concurrent manipulation, ConcurrentHashMap overtakes all three. Neither HashMap, LinkedHashMap, nor TreeMap promises thread-safety implicitly.

Recitals of Use Cases

Selection is helped by knowing the expected behavior of maps:

In Null-We-Trust:

HashMap and LinkedHashMap embrace null.
TreeMap plays hard to get with null keys due to comparison commitments.

In Order-We-Trust:

HashMap: Scorns any form of order.
LinkedHashMap: Honors insertion order, or caters to access order if requested.
TreeMap: Ensures keys are in line.

In Concurrent-World:

HashMap, LinkedHashMap, and TreeMap flake under multi-threaded scenarios. Ring fence with Collections.synchronizedMap() or switch to ConcurrentHashMap.

In Range-Queries-We-Delve:

TreeMap flaunts functions like subMap(), headMap(), and tailMap(), thanks to SortedMap.

Dive into the Mechanism

Unveiling the mechanical gears of maps may aid selection:

HashMap: Houses an array of buckets holding map entries. Hashing rules the entry's seat. In each bucket resides linked lists or balanced trees (when lists overgrow).
LinkedHashMap: Inherits from HashMap but adds link pointers to maintain sequence (in a doubly-linked list style).
TreeMap: Uses a Red-Black tree to render ordered storage.

All implement the Map interface—empowering you with polymorphism. With it, you can switch the map gears without revamping much of your codebase.

Pick Wisely:

Caching: LinkedHashMap excels with least recently accessed eviction policy.
Trade Time Complexity: HashMap for swift insertions but TreeMap for manipulation in sorted data.
Collections: Opt for TreeMap if collections need sorting. Otherwise, call HashMap.

Deep Dive: Understanding Data Structures, Time Complexity, and Nulls

Time for a more in-depth analysis of these maps:

Structural Uniqueness:

HashMap employs a bucket array.
LinkedHashMap builds on HashMap and incorporates a doubly-linked list.
TreeMap is built using a Red-Black tree for sorting purposes.

Complexity Comparison:

HashMap: Constant time for add, remove, and contains.
LinkedHashMap: Ditto to HashMap, but a tad slower thanks to its attention to order.
TreeMap: Log(n) time for add, remove, and contains, but that's the price for guaranteed order.

Behavior with Nulls:

HashMap: Welcomes one null key and multiple null values with equal fervor.
LinkedHashMap: Inherits the null-loving nature from HashMap with an added flavor of insertion order.
TreeMap: Null keys are enemies due to the need to navigate. But null values? Absolutely fine.