Map Implementations: HashMap, TreeMap, and Friends

Map Implementations: HashMap, TreeMap, and Friends

A Map stores keys mapped to values and is arguably the most used data structure in Java after the List. Each key can appear only once, and looking up a value by key is the whole point. Java provides several implementations to suit different ordering and concurrency needs, so you need to know which knob to turn.

HashMap

HashMap is a hash-table-based map giving O(1) average put, get, and containsKey. It makes no ordering guarantee and allows one null key and many null values. For the vast majority of cases this is the right default. From Java 8 onward, buckets that grow long convert to trees, so degenerate cases degrade gracefully.

TreeMap

TreeMap keeps keys sorted in natural or Comparator order using a red-black tree. It gives you firstKey, lastKey, higherKey, and range views like subMap. Choose it when you need keys in sorted order or range queries across a slice of the key space.

LinkedHashMap

LinkedHashMap keeps insertion order (or access order when configured) while behaving like a HashMap. That makes it the classic building block for LRU caches via removeEldestEntry.

Concurrent maps

For multithreaded code, ConcurrentHashMap provides thread-safe access with far better scalability than wrapping a plain map in Collections.synchronizedMap. ConcurrentSkipListMap offers a thread-safe, sorted alternative.

Map<String, Integer> scores = new HashMap<>();
scores.put("alice", 92);
scores.put("bob", 85);
scores.putIfAbsent("alice", 100);
System.out.println(scores.get("alice"));
System.out.println(scores.keySet());

Choosing a Map

Start with HashMap. If you need ordered iteration, pick LinkedHashMap. If you need sorted keys or range queries, pick TreeMap. If multiple threads mutate the map, pick ConcurrentHashMap. Also use modern defaults like Map.of for small immutable maps.

Key Points

• Map maps unique keys to values; each key maps to at most one value.
• HashMap is the fast, unordered default.
• LinkedHashMap preserves insertion or access order.
• TreeMap keeps keys sorted and supports range views.
• ConcurrentHashMap is the safe choice for concurrent mutation.