The surprising truth about Java’s Map implementations is that HashMap doesn’t actually store your keys in insertion order, or any predictable order for that matter.
Let’s see what that means in practice. Imagine we have a HashMap and we’re adding some key-value pairs:
import java.util.HashMap;
import java.util.Map;
public class MapDemo {
public static void main(String[] args) {
Map<String, Integer> myMap = new HashMap<>();
myMap.put("apple", 1);
myMap.put("banana", 2);
myMap.put("cherry", 3);
myMap.put("date", 4);
System.out.println("HashMap contents:");
for (Map.Entry<String, Integer> entry : myMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
When you run this, you might see output like:
HashMap contents:
apple: 1
banana: 2
date: 4
cherry: 3
Or, if you run it again, it might be different:
HashMap contents:
cherry: 3
date: 4
apple: 1
banana: 2
The order is not guaranteed. This is because HashMap uses hashing to determine where to store elements, aiming for fast lookups.
The Problem Map Implementations Solve
At its core, a Map is a data structure that stores associations between keys and values. Think of it like a dictionary: you look up a word (the key), and you get its definition (the value). The primary goal is efficient retrieval of a value given its key.
How HashMap Works Internally
HashMap uses an array of "buckets" (often implemented as linked lists or, in more modern Java, trees for efficiency when buckets get too full). When you put(key, value), HashMap calculates a hash code for the key. This hash code is then used to determine which bucket the entry should go into. When you get(key), it recalculates the hash code, finds the bucket, and then searches within that bucket for the specific key.
The magic (and the unpredictability of order) comes from the hash function and the internal array’s size. The hash function aims to distribute keys as evenly as possible across the buckets to minimize collisions (multiple keys mapping to the same bucket). The internal array resizes dynamically as more elements are added, which also shuffles the bucket assignments. This is why iteration order is not stable.
TreeMap: Order by Natural Sorting or Comparator
If you need your map entries to be ordered, TreeMap is your go-to. It stores entries in a sorted order based on the keys’ natural ordering (if they implement Comparable) or a custom Comparator you provide.
import java.util.TreeMap;
import java.util.Map;
public class TreeMapDemo {
public static void main(String[] args) {
Map<String, Integer> myTreeMap = new TreeMap<>();
myTreeMap.put("apple", 1);
myTreeMap.put("banana", 2);
myTreeMap.put("cherry", 3);
myTreeMap.put("date", 4);
System.out.println("TreeMap contents:");
for (Map.Entry<String, Integer> entry : myTreeMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
Output:
TreeMap contents:
apple: 1
banana: 2
cherry: 3
date: 4
TreeMap typically uses a Red-Black Tree internally. This tree structure inherently maintains sorted order. Insertion, deletion, and retrieval are generally O(log n) operations, which is slower than HashMap’s average O(1) but offers guaranteed ordering and efficient range queries.
LinkedHashMap: Order by Insertion or Access
LinkedHashMap bridges the gap. It maintains a doubly-linked list running through all of its entries. This list defines the iteration order. By default, this order is the insertion order.
import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapDemo {
public static void main(String[] args) {
Map<String, Integer> myLinkedHashMap = new LinkedHashMap<>();
myLinkedHashMap.put("apple", 1);
myLinkedHashMap.put("banana", 2);
myLinkedHashMap.put("cherry", 3);
myLinkedHashMap.put("date", 4);
System.out.println("LinkedHashMap (insertion order) contents:");
for (Map.Entry<String, Integer> entry : myLinkedHashMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
Output:
LinkedHashMap (insertion order) contents:
apple: 1
banana: 2
cherry: 3
date: 4
The internal structure of LinkedHashMap is a combination of a hash table (like HashMap) for quick lookups and a linked list for maintaining order. This gives you the O(1) average time complexity for basic operations like get and put, while also providing predictable iteration order.
There’s a less commonly known but powerful feature of LinkedHashMap: access order. If you initialize LinkedHashMap with new LinkedHashMap<>(initialCapacity, loadFactor, true), it will reorder the linked list to reflect the order in which entries were last accessed (i.e., via get or put). This is incredibly useful for implementing caches like LRU (Least Recently Used).
import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapAccessOrderDemo {
public static void main(String[] args) {
// true indicates access order
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true);
lruCache.put("a", 1);
lruCache.put("b", 2);
lruCache.put("c", 3);
System.out.println("Initial state:");
lruCache.forEach((k, v) -> System.out.print(k + " ")); // a b c
lruCache.get("b"); // Access 'b'
System.out.println("\nAfter accessing 'b':");
lruCache.forEach((k, v) -> System.out.print(k + " ")); // a c b
lruCache.put("a", 10); // Access 'a' again
System.out.println("\nAfter accessing 'a':");
lruCache.forEach((k, v) -> System.out.print(k + " ")); // c b a
}
}
Output:
Initial state:
a b c
After accessing 'b':
a c b
After accessing 'a':
c b a
When iterating over a LinkedHashMap configured for access order, the most recently accessed items appear last. This is because accessing an item moves it to the tail of the internal doubly-linked list.
Understanding these internal mechanics allows you to choose the right Map for the job: HashMap for speed with no order guarantees, TreeMap for sorted order, and LinkedHashMap for insertion or access order.
The next step is often understanding how to efficiently iterate over these maps, especially when dealing with large datasets or concurrent modifications.