Map Interface

The Map interface stores key-value pairs. Keys are unique; values can repeat. Map is a separate hierarchy — it does not extend Collection.

Map Hierarchy

Map<K,V>
├── HashMap<K,V>              — hash table, O(1) ops, no ordering
├── LinkedHashMap<K,V>        — insertion or access order
├── SortedMap → NavigableMap
│   └── TreeMap<K,V>          — red-black tree, sorted keys
├── Hashtable<K,V>            — synchronized (legacy, avoid)
└── ConcurrentMap
    ├── ConcurrentHashMap     — high-performance concurrent map
    └── ConcurrentSkipListMap — concurrent + sorted

Implementation Comparison

	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap
get/put/remove	O(1)*	O(1)*	O(log n)	O(1)*
Ordering	None	Insertion/Access	Sorted	None
Null keys	1 allowed	1 allowed	No	No
Null values	Yes	Yes	Yes	No
Thread-safe	No	No	No	Yes

*Average — O(n) worst case from hash collisions

Basic Operations

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

// Insert
scores.put("Alice", 95);
scores.put("Bob", 87);

// Retrieve
scores.get("Alice");                  // 95
scores.get("Unknown");                // null
scores.getOrDefault("Unknown", 0);    // 0

// Check
scores.containsKey("Alice");          // true
scores.containsValue(87);             // true

// Remove
scores.remove("Bob");                 // 87
scores.remove("Alice", 100);          // false — value doesn't match

// Size
scores.size();
scores.isEmpty();

Iteration

// Over entries (most common)
for (Map.Entry<String, Integer> e : map.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

// Over keys
for (String key : map.keySet()) { ... }

// Over values
for (Integer val : map.values()) { ... }

// forEach (Java 8+)
map.forEach((key, val) -> System.out.println(key + " = " + val));

Java 8+ Compute Methods

These eliminate the common “check-then-act” patterns:

// Add only if key is absent
map.putIfAbsent("Alice", 100);               // won't overwrite existing 95

// Compute if absent — lazy value creation
map.computeIfAbsent("counts", k -> new ArrayList<>()).add(item);

// Compute if present — update existing value
map.computeIfPresent("Alice", (k, v) -> v + 5);  // 95 → 100

// Merge — combine old and new values
map.merge("Alice", 10, Integer::sum);             // 100 → 110

// Replace
map.replace("Alice", 110, 120);                   // only if current value is 110

HashMap

The default choice. Uses hashing for O(1) average-case operations.

Map<String, Integer> map = new HashMap<>();           // capacity 16, load 0.75
Map<String, Integer> map = new HashMap<>(100);        // pre-size
Map<String, Integer> map = new HashMap<>(existing);   // copy

Important: Keys must have consistent hashCode() and equals(). If you use mutable objects as keys and modify them after insertion, the map breaks silently.

Capacity and load factor: When the number of entries exceeds capacity × loadFactor, the map rehashes into a larger table. Pre-sizing avoids costly rehashing.

LinkedHashMap

Same as HashMap but preserves insertion order. Can also be configured for access order (most recently accessed last) — useful for building LRU caches.

// Insertion order (default)
Map<String, Integer> map = new LinkedHashMap<>();

// Access order — entries move to end when accessed
Map<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);

// LRU Cache — evict oldest entry when size exceeds limit
Map<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100;
    }
};

TreeMap

Keeps keys sorted (natural order or via Comparator). Backed by a red-black tree.

TreeMap<Integer, String> map = new TreeMap<>();
map.put(5, "five");
map.put(2, "two");
map.put(8, "eight");
// keySet iteration: 2, 5, 8

// Navigable methods
map.ceilingKey(6);     // 8   — smallest key >= 6
map.floorKey(6);       // 5   — largest key <= 6
map.higherKey(5);      // 8   — smallest key > 5
map.lowerKey(5);       // 2   — largest key < 5

// Range views
map.subMap(2, true, 8, true);   // {2=two, 5=five, 8=eight}
map.headMap(5);                  // {2=two}
map.tailMap(5);                  // {5=five, 8=eight}

map.firstEntry();   // 2=two
map.lastEntry();    // 8=eight

Immutable Maps

// Java 9+ — up to 10 entries
Map<String, Integer> map = Map.of("a", 1, "b", 2, "c", 3);

// Java 9+ — any number of entries
Map<String, Integer> map = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2),
    Map.entry("c", 3)
);

// Unmodifiable wrapper
Map<String, Integer> unmod = Collections.unmodifiableMap(mutableMap);

When to Use Which

Scenario	Use
General-purpose key-value storage	HashMap
Need insertion order	LinkedHashMap
Need sorted keys or range queries	TreeMap
LRU cache	LinkedHashMap (access-order mode)
Thread-safe	ConcurrentHashMap
Thread-safe + sorted	ConcurrentSkipListMap