Q13 of 40 · Core Java
Compare HashMap, LinkedHashMap, and TreeMap. When would you use each?
Short answer
Short answer: HashMap gives O(1) average get/put with no ordering guarantee. LinkedHashMap preserves insertion order at slight memory cost. TreeMap keeps keys sorted (natural order or Comparator) at O(log n) per operation. Choose by whether you need order: none → HashMap, insertion → LinkedHashMap, sorted → TreeMap.
Detail
All three implement Map<K, V> with the same API, but their internal structures produce different ordering and performance characteristics.
HashMap: backed by a hash table (array of buckets, each a linked list or, since Java 8, a balanced tree when the bucket exceeds 8 entries). Average O(1) for get/put/remove assuming a good hash function. No guarantees about iteration order — it changes on resize. Use this as your default map when order doesn't matter.
LinkedHashMap: extends HashMap but maintains a doubly-linked list connecting entries in insertion order (or optionally access order). Iteration always returns entries in insertion order. Slightly higher memory footprint per entry (two extra pointers) and slightly slower than HashMap due to list maintenance. Use when you need predictable iteration order — e.g., a test fixture that builds JSON in a consistent field order, or an LRU cache (access-order mode + removeEldestEntry).
TreeMap: backed by a red-black tree. Keys are sorted by natural order (if they implement Comparable) or by a provided Comparator. Every operation is O(log n). Provides useful navigation methods: firstKey(), lastKey(), headMap(), tailMap(), floorKey(), ceilingKey(). Use when you need sorted keys — e.g., a time-ordered log of test events, a priority queue by severity.
For test code: LinkedHashMap is the right choice when you're building request bodies or JSON objects where field order should be deterministic for snapshot assertions. TreeMap is right when you want to iterate over test scenarios sorted by ID or name.
// EXAMPLE
MapComparison.java
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.TreeMap;
// HashMap — fastest, no ordering
Map<String, String> env = new HashMap<>();
env.put("BASE_URL", "https://api.staging.com");
env.put("TIMEOUT", "5000");
// iteration order unpredictable
// LinkedHashMap — insertion order preserved
Map<String, Object> requestBody = new LinkedHashMap<>();
requestBody.put("name", "Alice");
requestBody.put("email", "alice@example.com");
requestBody.put("role", "admin");
// serialises to JSON in this exact order — predictable snapshot assertions
// TreeMap — sorted by key
Map<String, Integer> testResults = new TreeMap<>();
testResults.put("TC_003_Checkout", 1);
testResults.put("TC_001_Login", 0);
testResults.put("TC_002_Search", 1);
// iterates as TC_001, TC_002, TC_003 — alphabetical
// TreeMap navigation methods
var firstFailing = testResults.entrySet().stream()
.filter(e -> e.getValue() == 0)
.findFirst();