DataslopeMaps
HashMap, LinkedHashMap, TreeMap, EnumMap — and the Map interface that powers almost every "lookup by key" you'll ever write
A map is a function from keys to values. If Set answers "is
this in here?", Map answers "what is associated with this?".
Maps are arguably the most powerful container in any program. Caches, indexes, configuration, frequency counts, lookup tables, JSON objects, and the symbol tables of every compiler in the world are maps under the skin.
The Map interface
Map<K, V> is its own root — it does not extend Collection,
because its elements are pairs (Map.Entry<K, V>), not single
values.
The three views — keySet(), values(), entrySet() — are how you
iterate a map. Of those, entrySet() is almost always what you want.
HashMap
HashMap is the workhorse. Average O(1) for put, get,
containsKey. No order guarantee.
merge(key, defaultValue, remapping) is the single most useful
HashMap method most people never learn. It atomically combines
"insert if absent, update if present" — perfect for histograms.
How HashMap actually works
Worth understanding the data structure once.
- Internally there is an
Object[] tableof buckets. - A key's bucket index is computed from its
hashCode. - If two keys hash to the same bucket (a collision), they are stored in a linked list inside that bucket — or, since Java 8, a red-black tree once the chain grows past 8 entries.
- When the table is too full (the load factor, default
0.75, is exceeded), the table doubles and every entry is rehashed into a fresh, larger table.
This explains a lot:
- Why
putandgetareO(1)average but worst-caseO(log n)(post-Java-8) after collisions. - Why a bad
hashCode(constant, or near-constant) destroys performance — every operation falls back to walking a long chain. - Why a
HashMapuses more memory than you'd guess: it has empty buckets to keep the load factor low.
LinkedHashMap
LinkedHashMap is to HashMap what LinkedHashSet is to HashSet:
it threads a linked list through the entries to preserve insertion
order (or, optionally, access order, for LRU caches).
Use it when the order in which entries were added matters for display or determinism — for example, JSON-like response objects.
TreeMap
TreeMap keeps keys in sorted order (red-black tree). O(log n)
everywhere, but in exchange you get range queries, firstKey,
lastKey, floorKey, ceilingKey, and subMap.
This is what makes TreeMap shine for ranges and bands — pricing
tiers, age groups, time windows.
EnumMap
When the key type is an enum, EnumMap is dramatically more
efficient than HashMap: it's just an array indexed by the enum
ordinal. Use it whenever you have an enum-keyed lookup.
The handful of Map methods worth memorizing
Java 8 added a small set of methods that eliminate a lot of "if present, update; else insert" boilerplate. Learn them and your code shrinks.
| Method | What it does |
|---|---|
getOrDefault(k, d) | get(k) if present, else d |
putIfAbsent(k, v) | put only if no existing entry |
computeIfAbsent(k, fn) | put fn.apply(k) if absent; useful for "map of lists" |
computeIfPresent(k, fn) | Update only if already present |
compute(k, fn) | Update unconditionally, with current value (or null) |
merge(k, v, fn) | If absent, put v; else put fn.apply(old, v) |
The most useful idiom of all is "map of lists":
Without computeIfAbsent that loop would be five lines of "if not
present, put an empty list, then add."
A common pitfall: null keys and null values
HashMap allows one null key and any number of null values.
TreeMap does not allow null keys (it would crash in
compareTo). The immutable Map.of(...) factories do not allow
null keys or values at all. Reading map.get(k) returns null
both when the key is absent and when the key's value is null —
use containsKey to distinguish.
Multi-file example: an in-memory cache
A real memoizer in 12 lines of Cache.java. The discipline of
computeIfAbsent is what makes it both compact and race-free against
itself (within a single thread).
Practice
Implement Grouper.byLength(List<String> words) that returns a Map<Integer, List<String>> where the key is the word's length and the value is the list of words of that length, in original order.
Expected output (a TreeMap is used in the driver only to make the printout deterministic):
3 -> [the, fox, dog]
4 -> [over, lazy]
5 -> [quick, brown, jumps]
Test your understanding
Which Map operation is the modern, one-liner equivalent of "if the key is not present, put an empty list; in any case, add the new value to the list at that key"?
put
merge
computeIfAbsent(key, k -> new ArrayList<>()).add(value)
putIfAbsent
When should you reach for TreeMap over HashMap?
When you need higher throughput
When you need keys iterated in sorted order, range queries (subMap), or "next key after x" (ceilingKey, floorKey)
When the keys are strings
When values can be null
Why is EnumMap preferred over HashMap when keys are enum constants?
HashMap is forbidden for enum keys
EnumMap is backed by a plain array indexed by the enum's ordinal, so it's faster and far more compact than a hash table
It throws on a missing key, which is desirable
It is automatically thread-safe