Collections Map — HashMap, TreeMap, LinkedHashMap, EnumMap, and IdentityHashMap

In this tutorial, you will learn about Collections Map. We cover key concepts, practical examples, and best practices to help you master this topic.

The Java Map interface stores key-value pairs, with implementations optimized for different ordering and performance requirements. Maps are the most versatile collection type — they power caches, configuration stores, indexes, and virtually every data structure that requires fast lookup by key.

What You'll Learn

• HashMap: constant-time key-value lookups
• TreeMap: sorted key-value pairs
• LinkedHashMap: insertion-order or access-order iteration
• EnumMap and IdentityHashMap: specialized maps

Why It Matters

Maps are everywhere in Java: HTTP request parameters, JSON objects, database result sets, configuration properties, and caching. Understanding the different implementations helps you choose the right tool and avoid subtle bugs.

Real-World Use

Spring's ApplicationContext stores beans in a map. JPA's EntityManagerFactory caches entities. Every HTTP session is a map of attributes. JSON objects are maps.

The Map Interface

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Charlie", 92);

Integer aliceScore = scores.get("Alice");  // 95
Integer daveScore = scores.get("Dave");    // null (not found)

boolean hasKey = scores.containsKey("Bob");   // true
boolean hasValue = scores.containsValue(100); // false

scores.remove("Charlie");
int size = scores.size();  // 2

// Iterate entries
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

HashMap

Backed by a hash table (array of buckets):

Map<String, String> capitals = new HashMap<>();
capitals.put("France", "Paris");
capitals.put("Japan", "Tokyo");
capitals.put("Brazil", "Brasilia");

Characteristics

• O(1) average for put, get, containsKey
• No ordering guarantees
• Allows one null key and multiple null values
• Initial capacity 16, load factor 0.75

How HashMap Works

1. hashCode() of the key determines the bucket index
2. If the bucket is empty, the entry is placed there
3. If occupied (collision), entries are stored in a Linked List or tree (Java 8+: tree when bucket reaches 8 entries)
4. On get(), the key's hash code finds the bucket, then equals() compares keys

TreeMap

Backed by a red-black tree, keys are sorted:

Map<String, String> sortedCapitals = new TreeMap<>();
sortedCapitals.put("Zimbabwe", "Harare");
sortedCapitals.put("Brazil", "Brasilia");
sortedCapitals.put("Argentina", "Buenos Aires");
System.out.println(sortedCapitals.keySet());
// [Argentina, Brazil, Zimbabwe] — sorted alphabetically

Characteristics

• O(log n) for put, get, containsKey
• Keys sorted by natural order or Comparator
• Implements SortedMap and NavigableMap
• Does not allow null keys

NavigableMap Operations

NavigableMap<Integer, String> map = new TreeMap<>();
map.put(1, "One");
map.put(3, "Three");
map.put(5, "Five");
map.put(7, "Seven");

map.lowerKey(5);    // 3
map.floorKey(5);    // 5
map.ceilingKey(4);  // 5
map.higherKey(5);   // 7
map.firstKey();     // 1
map.lastKey();      // 7

LinkedHashMap

Extends HashMap with a linked list maintaining iteration order:

Map<String, String> insertionOrder = new LinkedHashMap<>();
insertionOrder.put("A", "Apple");
insertionOrder.put("C", "Cat");
insertionOrder.put("B", "Ball");
System.out.println(insertionOrder);
// {A=Apple, C=Cat, B=Ball} — insertion order

Access-Order Mode

Useful for LRU caches:

// LRU cache: most recently accessed entries move to end
LinkedHashMap<String, String> lru = new LinkedHashMap<>(16, 0.75f, true);
lru.put("A", "1");
lru.put("B", "2");
lru.put("C", "3");
lru.get("A"); // A moves to end
System.out.println(lru.keySet()); // [B, C, A] — A is now last

EnumMap

Specialized map for enum keys — extremely fast and memory-efficient:

enum Day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY }

Map<Day, String> schedule = new EnumMap<>(Day.class);
schedule.put(Day.MONDAY, "Team meeting");
schedule.put(Day.FRIDAY, "Code review");

EnumMap uses an array indexed by ordinal. It is faster than HashMap for enum keys and never requires hashing.

IdentityHashMap

Uses reference equality (==) instead of equals() for key comparison:

Map<String, String> identityMap = new IdentityHashMap<>();
String key1 = new String("key");
String key2 = new String("key");
identityMap.put(key1, "value1");
identityMap.put(key2, "value2");
System.out.println(identityMap.size()); // 2 (different references)

Useful for:

• Object interning
• Tracking proxy objects
• Serialization/deserialization graphs where reference identity matters

Common Map Methods (Java 8+)

Map<String, Integer> map = new HashMap<>();

// Compute if absent
map.computeIfAbsent("key", k -> k.length()); // inserts 3

// Merge
map.merge("key", 1, Integer::sum); // adds 1 to existing or inserts 1

// ForEach
map.forEach((k, v) -> System.out.println(k + " -> " + v));

// Get with default
map.getOrDefault("missing", 0); // 0, not null

Common Mistakes

1. Using mutable objects as map keys. If the key's hashCode() or equals() changes, the map becomes corrupted — entries become unreachable.
2. Forgetting that put() returns the previous value. Map.put() returns the old value (or null). This is useful but often overlooked.
3. Modifying a map while iterating over entrySet(). Use <a href="/design-patterns/iterator/">Iterator</a>.remove() or ConcurrentHashMap for concurrent modification.
4. Assuming null is always a valid key. TreeMap and ConcurrentHashMap do not allow null keys. Hashtable does not allow null keys or values.
5. Using HashMap when ordering matters. If you rely on iteration order, use LinkedHashMap or TreeMap.

Practice Questions

1. What is the time complexity of get() on a HashMap?
O(1) average, O(n) worst case (if all keys hash to the same bucket).

2. How does LinkedHashMap maintain insertion order?
It maintains a doubly-linked list running through all entries, recording the insertion order.

3. What is the difference between HashMap and IdentityHashMap?
HashMap uses equals() and hashCode(). IdentityHashMap uses == and System.identityHashCode() — reference equality.

4. What is a suitable Map implementation for a cache?
LinkedHashMap in access-order mode for an LRU cache. ConcurrentHashMap for a thread-safe cache. Caffeine (external library) for advanced caching.

5. What does computeIfAbsent do?
If the key is not already associated with a value, it computes a value using the provided function and inserts it. Returns the existing or computed value.

Challenge Question:
Implement a simple LRU cache using LinkedHashMap with a maximum capacity of 100 entries. Override removeEldestEntry(Map.Entry eldest) to return true when size exceeds capacity. The cache should automatically evict the least recently accessed entry. Test it by adding 105 entries and verifying only 100 remain.

FAQ

Mini Project

Write a program MapDemo.java that:

1. Creates a HashMap of product names (key) to prices (value) — add 10 products
2. Uses computeIfAbsent to add a default price for missing products
3. Uses merge() to apply a discount to all prices
4. Creates a LinkedHashMap in access-order mode and demonstrates LRU behavior
5. Creates a TreeMap with a custom Comparator that sorts strings by length (then alphabetically)
6. Creates an EnumMap for OrderStatus enum to status description mapping
7. Demonstrates the difference between IdentityHashMap and HashMap with new String("key")

Print the contents of each map at each step.

What's Next

Maps handle key-value associations. But what about ordered processing of elements? Lesson 26 covers the Queue and Deque interfaces — PriorityQueue, ArrayDeque, and BlockingQueue implementations for FIFO, priority, and concurrent processing.