[Advanced Java] Advanced Map Implementations: TreeMap, LinkedHashMap, Hashtable and ConcurrentHashMap

HashMap answers exactly one question quickly — what is stored under this key — and promises nothing else. It does not promise an order, it does not promise safety when two threads write at once, and it cannot answer "what is the largest key that is still below 1999" without scanning every entry you gave it.

The other implementations of Map each buy one of those guarantees, and each charges for it in a different currency. TreeMap keeps the keys sorted and turns range questions into single calls. LinkedHashMap keeps a linked list alongside the table so iteration order is yours to choose. Hashtable locks the whole map on every call and should not appear in new code. ConcurrentHashMap locks one bin at a time and is the map to reach for the moment a second thread appears. This article is about the four of them and about which one a given requirement actually needs.

Every output line, error message and stack trace below was produced by compiling and running the code on OpenJDK 21.0.6. No elapsed time is reported anywhere in this article — cost is described structurally, as the number of comparisons or the granularity of a lock. The statements about behaviour under real concurrency are statements about the documented contract, quoted from the JDK source; a race is not reproducible on demand, so nothing here was verified by racing threads.

Four implementations behind one interface

All five maps in this article implement Map<K, V>, so put, get, remove, containsKey, getOrDefault, merge and computeIfAbsent mean the same thing in every one of them. Switching implementation is one word at the new expression. What changes is everything the Map interface deliberately leaves unspecified:

Two of those columns come as a surprise often enough to be worth stating up front. TreeMap accepts a null value but not a null key, because it has to compare the key with something. Hashtable and ConcurrentHashMap reject both, and the sections below quote the exact exceptions.

The class hierarchy is not what most people assume either:

System.out.println("LinkedHashMap super   = " + LinkedHashMap.class.getSuperclass().getName());
System.out.println("Hashtable superclass  = " + Hashtable.class.getSuperclass().getName());
System.out.println("HashMap superclass    = " + HashMap.class.getSuperclass().getName());
System.out.println("TreeMap interfaces    = " + Arrays.toString(TreeMap.class.getInterfaces()));
System.out.println("CHM interfaces        = " + Arrays.toString(ConcurrentHashMap.class.getInterfaces()));

LinkedHashMap super   = java.util.HashMap
Hashtable superclass  = java.util.Dictionary
HashMap superclass    = java.util.AbstractMap
TreeMap interfaces    = [interface java.util.NavigableMap, interface java.lang.Cloneable, interface java.io.Serializable]
CHM interfaces        = [interface java.util.concurrent.ConcurrentMap, interface java.io.Serializable]

LinkedHashMap really is a HashMap — it is the same bucket table with a doubly linked list threaded through the entries. Hashtable extends Dictionary, an abstract class that predates the collections framework entirely. And TreeMap and ConcurrentHashMap each implement a sub-interface of Map that carries the extra operations their structure makes possible: NavigableMap and ConcurrentMap. Those two interfaces are where most of this article lives.

TreeMap keeps the keys sorted

A TreeMap is a red-black tree, not a hash table. There is no hashCode() call anywhere in a TreeMap lookup; every operation walks down from the root comparing keys, which is O(log n) instead of O(1) but comes with an ordering that a hash table structurally cannot provide.

import java.util.*;

public class TreeBasics {
    public static void main(String[] args) {
        TreeMap<String, Integer> stock = new TreeMap<>();
        stock.put("washer", 85);
        stock.put("bolt", 120);
        stock.put("nut", 340);
        stock.put("screw", 60);
        stock.put("anchor", 12);

        System.out.println("map        = " + stock);
        System.out.println("firstKey   = " + stock.firstKey());
        System.out.println("lastKey    = " + stock.lastKey());
        System.out.println("firstEntry = " + stock.firstEntry());
        System.out.println("lastEntry  = " + stock.lastEntry());
    }
}

map        = {anchor=12, bolt=120, nut=340, screw=60, washer=85}
firstKey   = anchor
lastKey    = washer
firstEntry = anchor=12
lastEntry  = washer=85

The keys came out sorted although they went in scrambled, and firstKey/lastKey are O(log n) walks to the leftmost and rightmost node rather than a scan. firstEntry and lastEntry return the whole Map.Entry, which saves the second lookup a get(firstKey()) would cost.

There is a destructive pair as well. pollFirstEntry and pollLastEntry return the entry and remove it, which turns a TreeMap into a priority structure keyed by whatever you sorted on:

System.out.println("pollFirstEntry    = " + stock.pollFirstEntry());
System.out.println("pollLastEntry     = " + stock.pollLastEntry());
System.out.println("after polls       = " + stock);

pollFirstEntry    = anchor=12
pollLastEntry     = washer=85
after polls       = {bolt=120, nut=340, screw=60}

The threshold lookup a HashMap cannot answer

This is the case that makes TreeMap worth its extra log factor. A rate table, a grade band, a tax bracket and a shipping tariff are all the same shape: a small set of thresholds, and a question of the form "which band does this value fall into". The key you have is almost never a key in the map.

import java.util.*;

public class RateTable {

    static final NavigableMap<Integer, String> SHIPPING = new TreeMap<>(Map.of(
            0,     "0.00 - free pickup",
            500,   "2.50 - small parcel",
            2000,  "4.90 - standard parcel",
            10000, "12.00 - heavy parcel",
            30000, "29.00 - freight"));

    static String rateFor(int grams) {
        return SHIPPING.floorEntry(grams).getValue();
    }

    public static void main(String[] args) {
        int[] weights = {0, 120, 499, 500, 1999, 2000, 9999, 25000, 30000, 84000};
        for (int g : weights) {
            Map.Entry<Integer, String> band = SHIPPING.floorEntry(g);
            System.out.printf("%6d g -> band %-6d %s%n", g, band.getKey(), band.getValue());
        }
        System.out.println("floorEntry(-1) = " + SHIPPING.floorEntry(-1));
    }
}

     0 g -> band 0      0.00 - free pickup
   120 g -> band 0      0.00 - free pickup
   499 g -> band 0      0.00 - free pickup
   500 g -> band 500    2.50 - small parcel
  1999 g -> band 500    2.50 - small parcel
  2000 g -> band 2000   4.90 - standard parcel
  9999 g -> band 2000   4.90 - standard parcel
 25000 g -> band 10000  12.00 - heavy parcel
 30000 g -> band 30000  29.00 - freight
 84000 g -> band 30000  29.00 - freight

floorEntry(g) is the greatest key less than or equal to g, with its value. That is the whole band lookup, in one call, in O(log n), with no if chain to keep in sync with the table and no loop to write. Adding a band is adding one line to the map. When the argument is below every key, floorEntry returns null rather than throwing — floorEntry(-1) above — so a table that has to accept anything should start at the minimum of the key type.

The same table in a HashMap cannot do it. HASH.get(1999) is null, because 1999 is not a key, and there is no way to ask a hash table for a neighbour. What you write instead is a full scan of the key set:

static final Map<Integer, String> HASH = new HashMap<>(Map.of(
        0, "0.00", 500, "2.50", 2000, "4.90", 10000, "12.00", 30000, "29.00"));

static String rateFor(int grams) {
    int best = Integer.MIN_VALUE;
    for (int threshold : HASH.keySet()) {
        if (threshold <= grams && threshold > best) best = threshold;
    }
    return best == Integer.MIN_VALUE ? null : HASH.get(best);
}

HashMap iteration order = [0, 2000, 10000, 30000, 500]
120 g -> 0.00
1999 g -> 2.50
25000 g -> 12.00
HASH.get(1999) = null

It produces the right answers and it is O(n) in the number of bands on every single lookup, plus a second hash lookup at the end. Look at the printed iteration order, too: the bands come out of the HashMap in an order that has nothing to do with their values, which is exactly why the loop needs the running maximum instead of being able to stop early.

floorKey, ceilingKey, lowerKey and higherKey

NavigableMap has four neighbour lookups, and the only thing separating them is which direction they search and whether an exact match counts. Each has an ...Key form returning the key and an ...Entry form returning the whole entry.

Against the shipping table, asking about the key 2000, which is present:

And against a key that is absent, "m" in the hardware map, plus the two edges:

System.out.println("floorKey(m)       = " + stock.floorKey("m"));
System.out.println("ceilingKey(m)     = " + stock.ceilingKey("m"));
System.out.println("floorKey(a)       = " + stock.floorKey("a"));
System.out.println("ceilingKey(z)     = " + stock.ceilingKey("z"));

floorKey(m)       = bolt
ceilingKey(m)     = nut
floorKey(a)       = null
ceilingKey(z)     = null

For a key that is not in the map, floor and lower agree, and so do ceiling and higher — the inclusive/exclusive distinction only bites on an exact hit. All four return null when nothing qualifies, which is the case you have to handle at the ends of the range.

headMap, tailMap, subMap and descendingMap

The range methods return views, not copies. Every one of them is backed by the original tree, costs nothing to create, and reflects later changes to the map.

System.out.println("headMap(nut)      = " + stock.headMap("nut"));
System.out.println("headMap(nut,true) = " + stock.headMap("nut", true));
System.out.println("tailMap(nut)      = " + stock.tailMap("nut"));
System.out.println("tailMap(nut,fal)  = " + stock.tailMap("nut", false));
System.out.println("subMap(b,s)       = " + stock.subMap("b", "s"));
System.out.println("subMap(bolt..scr) = " + stock.subMap("bolt", true, "screw", true));
System.out.println("descendingMap     = " + stock.descendingMap());
System.out.println("descendingKeySet  = " + stock.descendingKeySet());

headMap(nut)      = {anchor=12, bolt=120}
headMap(nut,true) = {anchor=12, bolt=120, nut=340}
tailMap(nut)      = {nut=340, screw=60, washer=85}
tailMap(nut,fal)  = {screw=60, washer=85}
subMap(b,s)       = {bolt=120, nut=340}
subMap(bolt..scr) = {bolt=120, nut=340, screw=60}
descendingMap     = {washer=85, screw=60, nut=340, bolt=120, anchor=12}
descendingKeySet  = [washer, screw, nut, bolt, anchor]

The defaults are asymmetric and worth memorising: headMap excludes its bound, tailMap includes it, and subMap(from, to) includes from and excludes to — the same half-open convention as String.substring. Every one of them has an explicit overload taking boolean inclusive flags, and using the explicit form is how you stop guessing.

Being a view has two consequences. Writes go through to the backing map, and writes outside the range are rejected:

TreeMap<String, Integer> t = new TreeMap<>();
t.put("apple", 1); t.put("banana", 2); t.put("cherry", 3); t.put("date", 4);

SortedMap<String, Integer> head = t.headMap("cherry");
System.out.println("headMap        = " + head);
head.put("avocado", 9);
System.out.println("backing map    = " + t);
try { head.put("zebra", 0); }
catch (Exception e) { System.out.println("put outside range -> " + e); }
t.put("blueberry", 7);
System.out.println("view sees new  = " + head);

headMap        = {apple=1, banana=2}
backing map    = {apple=1, avocado=9, banana=2, cherry=3, date=4}
put outside range -> java.lang.IllegalArgumentException: key out of range
view sees new  = {apple=1, avocado=9, banana=2, blueberry=7}

descendingMap is a view too, so removing through it removes from the original. And an inverted range is an error rather than an empty map:

try { t.subMap("c", "a"); } catch (Exception e) { System.out.println("subMap(c,a) -> " + e); }

subMap(c,a) -> java.lang.IllegalArgumentException: fromKey > toKey

Ordering comes from Comparable or from a Comparator

A TreeMap has to compare keys, so it needs one of two things: keys that implement Comparable, or a Comparator handed to the constructor. If it has neither, the failure arrives on the very first put, not on the second:

class Box { final int n; Box(int n){this.n=n;} public String toString(){ return "Box(" + n + ")"; } }

Map<Box, String> m = new TreeMap<>();
m.put(new Box(1), "one");
System.out.println("first put ok: " + m);

Exception in thread "main" java.lang.ClassCastException: class Box cannot be cast to class java.lang.Comparable (Box is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.TreeMap.compare(TreeMap.java:1604)
	at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:811)
	at java.base/java.util.TreeMap.put(TreeMap.java:820)
	at java.base/java.util.TreeMap.put(TreeMap.java:569)
	at TreeNotComparable.main(TreeNotComparable.java:8)

"first put ok" never printed. Inserting into an empty tree still calls compare(key, key), purely so the type error surfaces immediately instead of when a second key arrives. Passing a Comparator fixes it without touching Box:

Map<Box, String> byN = new TreeMap<>(Comparator.comparingInt(b -> b.n));
byN.put(new Box(3), "three");
byN.put(new Box(1), "one");
byN.put(new Box(2), "two");
System.out.println("with comparator = " + byN);

with comparator = {Box(1)=one, Box(2)=two, Box(3)=three}

The comparator does more than order the keys — it defines key identity. A TreeMap never calls equals or hashCode on a key; two keys are the same key when the comparison returns zero. That is easy to see and easy to be caught by:

TreeMap<String, Integer> ci = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
ci.put("Bolt", 1);
ci.put("bolt", 2);
ci.put("NUT", 3);
System.out.println("case-insensitive     = " + ci);
System.out.println("size                 = " + ci.size());
System.out.println("get(\"BOLT\")          = " + ci.get("BOLT"));
System.out.println("\"Bolt\".equals(\"bolt\") = " + "Bolt".equals("bolt"));

case-insensitive     = {Bolt=2, NUT=3}
size                 = 2
get("BOLT")          = 2
"Bolt".equals("bolt") = false

Two entries, not three: "bolt" overwrote "Bolt" while leaving the original key object in place, and "BOLT" finds it. The same map in a HashMap would hold three separate entries, because String.equals is case-sensitive. Neither is wrong — but a map whose notion of equality disagrees with equals is a map you have to be deliberate about.

That comparator is part of the map's identity, and it survives only one of the two copy constructors:

System.out.println("copy from SortedMap keeps comparator: " + new TreeMap<>(ci).comparator());
Map<String, Integer> plain = new HashMap<>(ci);
System.out.println("copy from Map loses it:               " + new TreeMap<>(plain).comparator());

copy from SortedMap keeps comparator: java.lang.String$CaseInsensitiveComparator@7f31245a
copy from Map loses it:               null

new TreeMap<>(SortedMap) copies the comparator; new TreeMap<>(Map) reverts to natural ordering. Round-tripping a case-insensitive map through a HashMap silently gives you a case-sensitive one.

Finally, the null key. TreeMap cannot compare null with anything, so it rejects it — and on an empty map the JDK's helpful NullPointerException message spells out exactly why:

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Comparable.compareTo(Object)" because "k1" is null
	at java.base/java.util.TreeMap.compare(TreeMap.java:1604)
	at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:811)
	at java.base/java.util.TreeMap.put(TreeMap.java:820)
	at java.base/java.util.TreeMap.put(TreeMap.java:569)
	at TreeNullEmpty.main(TreeNullEmpty.java:5)

get(null) and containsKey(null) throw NullPointerException as well. A null value is accepted without complaint, since values are never compared.

LinkedHashMap: insertion order, and access order

LinkedHashMap is a HashMap with a doubly linked list running through all the entries. Lookups still use the bucket table and still cost O(1) on average; the list only decides what the iterator sees and in which order. The extra cost is two references per entry.

By default the list is in insertion order, and it is stable across everything that reorders a HashMap:

Map<Integer, Integer> h = new HashMap<>();
Map<Integer, Integer> l = new LinkedHashMap<>();
for (int i = 1; i <= 12; i++) { h.put(i * 7, i); l.put(i * 7, i); }
System.out.println("HashMap       12 entries: " + h.keySet());
System.out.println("LinkedHashMap 12 entries: " + l.keySet());
h.put(91, 13); l.put(91, 13);
System.out.println("HashMap       13 entries: " + h.keySet());
System.out.println("LinkedHashMap 13 entries: " + l.keySet());

HashMap       12 entries: [49, 35, 84, 21, 70, 7, 56, 42, 28, 77, 14, 63]
LinkedHashMap 12 entries: [7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84]
HashMap       13 entries: [35, 70, 7, 42, 77, 14, 49, 84, 21, 56, 91, 28, 63]
LinkedHashMap 13 entries: [7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91]

The thirteenth entry triggers the resize that scrambles the HashMap completely. The LinkedHashMap resizes too — same table, same load factor — and its iteration order does not move, because the list is not the table.

One rule about that list: re-putting an existing key does not move it, but removing and re-adding does.

Map<String, Integer> ins = new LinkedHashMap<>();
ins.put("bolt", 1); ins.put("nut", 2); ins.put("washer", 3); ins.put("anchor", 4);

ins.put("nut", 99);
System.out.println("after put(nut,99)    = " + ins.keySet());
ins.remove("bolt"); ins.put("bolt", 1);
System.out.println("after remove+re-put  = " + ins.keySet());

after put(nut,99)    = [bolt, nut, washer, anchor]
after remove+re-put  = [nut, washer, anchor, bolt]

Access order is the constructor argument nobody uses

LinkedHashMap has a three-argument constructor whose last parameter is accessOrder. Set it to true and the list is maintained in least-recently-used first order instead: every access moves the entry to the end.

Map<String, Integer> acc = new LinkedHashMap<>(16, 0.75f, true);
acc.put("bolt", 1); acc.put("nut", 2); acc.put("washer", 3); acc.put("anchor", 4);
System.out.println("access order start   = " + acc.keySet());
acc.get("bolt");
System.out.println("after get(bolt)      = " + acc.keySet());
acc.get("washer");
System.out.println("after get(washer)    = " + acc.keySet());
acc.put("nut", 99);
System.out.println("after put(nut,99)    = " + acc.keySet());
acc.containsKey("anchor");
System.out.println("after containsKey    = " + acc.keySet());
acc.getOrDefault("anchor", 0);
System.out.println("after getOrDefault   = " + acc.keySet());
acc.merge("bolt", 1, Integer::sum);
System.out.println("after merge(bolt)    = " + acc.keySet());
for (String k : acc.keySet()) { }
System.out.println("after for-each       = " + acc.keySet());

access order start   = [bolt, nut, washer, anchor]
after get(bolt)      = [nut, washer, anchor, bolt]
after get(washer)    = [nut, anchor, bolt, washer]
after put(nut,99)    = [anchor, bolt, washer, nut]
after containsKey    = [anchor, bolt, washer, nut]
after getOrDefault   = [bolt, washer, nut, anchor]
after merge(bolt)    = [washer, nut, anchor, bolt]
after for-each       = [washer, nut, anchor, bolt]

Read that output carefully, because "access" is a precise word with a surprising membership list. get, put on an existing key, getOrDefault and merge all count as an access and move the entry. containsKey does not — it answers without touching the list. Neither does iterating: the for-each walked all four entries and left the order exactly as it found it, which is what makes an access-ordered map safe to print.

⚠️ An access-ordered LinkedHashMap is structurally modified by a plain get. Two threads calling only get on the same map are still both writers, and the map is no more thread-safe here than a HashMap is.

An LRU cache with removeEldestEntry

Access order alone is only half a cache. The other half is removeEldestEntry, a protected method the map calls after every insertion, handing you the entry at the old end of the list. The base implementation returns false and nothing is ever evicted; override it to return true and that entry is dropped. The whole cache is five lines:

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(16, 0.75f, true);       // true = access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

With a capacity of three:

LruCache<String, Integer> cache = new LruCache<>(3);
cache.put("a", 1);   System.out.println("put a   -> " + cache);
cache.put("b", 2);   System.out.println("put b   -> " + cache);
cache.put("c", 3);   System.out.println("put c   -> " + cache);
cache.get("a");      System.out.println("get a   -> " + cache);
cache.put("d", 4);   System.out.println("put d   -> " + cache);
cache.get("c");      System.out.println("get c   -> " + cache);
cache.put("e", 5);   System.out.println("put e   -> " + cache);
System.out.println("get b (evicted) -> " + cache.get("b"));
System.out.println("size            -> " + cache.size());

put a   -> {a=1}
put b   -> {a=1, b=2}
put c   -> {a=1, b=2, c=3}
get a   -> {b=2, c=3, a=1}
put d   -> {c=3, a=1, d=4}
get c   -> {a=1, d=4, c=3}
put e   -> {d=4, c=3, e=5}
get b (evicted) -> null
size            -> 3

The eviction is the interesting line. When d arrives the cache is full, and the entry that goes is b — not a, which was inserted first, because the get("a") on the previous line moved a to the young end. Two steps later get("c") rescues c and it is a that falls off. That is precisely the LRU policy, and none of it is code you wrote: it is accessOrder plus one return size() > capacity.

Three details make the difference between this working and quietly not:

• The comparison is size() > capacity, not >=. removeEldestEntry is called after the new entry is in, so the map is momentarily one over.
• super(16, 0.75f, true) is mandatory. With the no-argument constructor you get insertion order, removeEldestEntry still fires, and you have built a FIFO cache that will happily evict the entry you read a microsecond ago.
• The method is protected, so this only works from a subclass. That is the intended design, not a workaround.

Hashtable is legacy, and its own documentation says so

Hashtable shipped with Java 1.0, before the collections framework existed. It was fitted with the Map interface afterwards, and the class documentation is unusually direct about what to do with it:

As of the Java 2 platform v1.2, this class was retrofitted to implement the Map interface, making it a member of the Java Collections Framework. Unlike the new collection implementations, Hashtable is synchronized. If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use ConcurrentHashMap in place of Hashtable.

Its thread safety is the bluntest possible instrument: the synchronized keyword on almost every public method, so every call — including every read — takes the same single lock on the map object.

static void report(Class<?> c) {
    int total = 0, sync = 0;
    for (Method m : c.getDeclaredMethods()) {
        if (!Modifier.isPublic(m.getModifiers())) continue;
        total++;
        if (Modifier.isSynchronized(m.getModifiers())) sync++;
    }
    System.out.printf("%-22s public methods %3d, synchronized %3d%n", c.getSimpleName(), total, sync);
}

Hashtable              public methods  30, synchronized  26
HashMap                public methods  25, synchronized   0
ConcurrentHashMap      public methods  65, synchronized   0

Note the third line: ConcurrentHashMap has no synchronized methods at all. It is thread-safe by an entirely different mechanism, which is the subject of the next section.

Hashtable also rejects null in both positions, and the two rejections come from different places:

put(null, "v")  java.lang.NullPointerException: Cannot invoke "Object.hashCode()" because "key" is null
put("k", null)  java.lang.NullPointerException

The key rejection is incidental — it falls out of calling hashCode() on the key. The value rejection is deliberate; the stack trace lands on an explicit check in Hashtable.put:

Exception in thread "main" java.lang.NullPointerException
	at java.base/java.util.Hashtable.put(Hashtable.java:476)
	at HtNullValue.main(HtNullValue.java:5)

One last legacy artefact: Hashtable predates Iterator, so it also exposes keys() and elements() returning Enumeration. Those old enumerations do not check for modification, while the modern collection views do:

Enumeration completed, visited [b, a, c]

The map was modified during that enumeration and nothing complained. The keySet() iterator on the same map throws ConcurrentModificationException in the same situation. Two APIs on one object with two different failure modes is exactly the kind of thing a class accumulates in thirty years.

What to use instead. For a single-threaded map, HashMap. For several threads, ConcurrentHashMap. Collections.synchronizedMap(new HashMap<>()) gives you Hashtable's locking model applied to a modern map — one lock over everything, and it accepts null keys and values because the underlying HashMap does:

synchronizedMap accepts nulls = {null=1, k=null}
synchronizedMap class = java.util.Collections$SynchronizedMap

It is a reasonable wrapper for a map that is rarely touched. It is not a substitute for ConcurrentHashMap.

What ConcurrentHashMap actually promises

Threads are a later topic in this course, so this section is deliberately about the contract rather than about concurrency itself. Everything below is either quoted from the class documentation in the JDK 21 source or demonstrated by running single-threaded code that exposes the mechanism.

The headline difference from Hashtable is lock granularity. Hashtable takes one lock over the entire map for every operation, so a writer touching one key excludes every other writer and every reader on every other key. ConcurrentHashMap locks the individual bin a key hashes to; two writers whose keys land in different bins do not interact at all, and reads are not blocked by writes.

That is a structural argument, not a benchmark: with one lock, contention grows with the number of threads touching the map; with per-bin locks, it grows with the number of threads touching the same bin, which the table's size and hash spread keep small. This article publishes no timing for that claim.

You can see the per-bin lock without a second thread. computeIfAbsent runs your function while holding the bin's lock, so a function that writes back into the same bin deadlocks against itself — and the JDK detects that and throws:

ConcurrentHashMap<String, Integer> m = new ConcurrentHashMap<>();
m.computeIfAbsent("a", k -> {
    m.put("ab", 2);      // "ab" hashes to the same bin as "a"
    return 1;
});

Exception in thread "main" java.lang.IllegalStateException: Recursive update
	at java.base/java.util.concurrent.ConcurrentHashMap.putVal(ConcurrentHashMap.java:1063)
	at java.base/java.util.concurrent.ConcurrentHashMap.put(ConcurrentHashMap.java:1006)
	at Recursive2.lambda$main$0(Recursive2.java:6)
	at java.base/java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1708)
	at Recursive2.main(Recursive2.java:5)

Change the inserted key to one that hashes elsewhere and the identical code succeeds:

m.computeIfAbsent("a", k -> {
    m.put("b", 2);       // different bin
    return 1;
});
System.out.println(m);

{a=1, b=2}

Same operation, same thread, two different outcomes decided purely by which bin the second key falls into. That is the locking granularity made visible. The practical rule that follows: never modify a ConcurrentHashMap from inside its own compute, computeIfAbsent or merge function.

The iterator is weakly consistent, not fail-fast

A HashMap iterator throws ConcurrentModificationException the moment the map is structurally modified underneath it. A ConcurrentHashMap iterator never does. The documentation states it plainly:

Iterators, Spliterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException.

That word is weakly consistent, and it is observable from one thread:

static void walk(String name, Map<String, Integer> m) {
    List<String> seen = new ArrayList<>();
    try {
        for (String k : m.keySet()) {
            seen.add(k);
            if (k.equals("b")) {
                m.put("zz", 99);
                m.remove("d");
            }
        }
        System.out.println("  completed, visited " + seen);
    } catch (Exception e) {
        System.out.println("  visited " + seen + " then threw " + e);
    }
}

--- HashMap ---
  visited [a, b] then threw java.util.ConcurrentModificationException
--- LinkedHashMap ---
  visited [a, b] then threw java.util.ConcurrentModificationException
--- TreeMap ---
  visited [a, b] then threw java.util.ConcurrentModificationException
--- Hashtable ---
  visited [b] then threw java.util.ConcurrentModificationException
--- ConcurrentHashMap ---
  completed, visited [a, b, c]

Four maps abort; ConcurrentHashMap finishes the walk. Note what it did not do: it never saw zz, the key added mid-iteration. That is the second half of "weakly consistent" — an entry inserted after the iterator started may or may not appear, and there is no rule you can lean on. Insert five different keys at the same point in the same iteration and the iterator sees two of them:

static List<String> run(String inserted) {
    Map<String, Integer> m = new ConcurrentHashMap<>();
    m.put("a", 1); m.put("b", 2); m.put("c", 3); m.put("d", 4);
    List<String> seen = new ArrayList<>();
    for (String k : m.keySet()) {
        seen.add(k);
        if (k.equals("a")) m.put(inserted, 99);
    }
    return seen;
}

iteration order = [a, b, c, d]
insert zz after visiting a -> [a, b, c, d]
insert e  after visiting a -> [a, b, c, d, e]
insert x  after visiting a -> [a, b, c, d, x]
insert aa after visiting a -> [a, b, c, d]
insert q  after visiting a -> [a, b, c, d]

e and x land in bins the iterator has not reached yet, so they show up. zz, aa and q land behind it and do not. An iteration of a ConcurrentHashMap is therefore not a snapshot and not a live view — it is somewhere between, which is all the guarantee you get and all you should write code against.

The same weakness applies to the aggregate methods. size(), isEmpty() and containsValue() are documented as reflecting "transient states that may be adequate for monitoring or estimation purposes, but not for program control". mappingCount() is the version to prefer — it returns a long rather than an int, and its documentation says outright that "the value returned is an estimate; the actual count may differ if there are concurrent insertions or removals". In single-threaded code both are exact:

size()           = 3
mappingCount()   = 3

The compound operations are the atomic ones

get is atomic. put is atomic. get followed by put is two operations with a gap in the middle, and nothing in ConcurrentHashMap closes that gap for you. This is why ConcurrentMap exists as a separate interface: it specifies the compound operations that are single atomic steps.

ConcurrentMap<String, Integer> m = new ConcurrentHashMap<>();
System.out.println("putIfAbsent(a,1) = " + m.putIfAbsent("a", 1));
System.out.println("putIfAbsent(a,9) = " + m.putIfAbsent("a", 9));
System.out.println("replace(a,1,5)   = " + m.replace("a", 1, 5));
System.out.println("replace(a,1,7)   = " + m.replace("a", 1, 7));
System.out.println("remove(a,99)     = " + m.remove("a", 99));
System.out.println("remove(a,5)      = " + m.remove("a", 5));
System.out.println("map              = " + m);

putIfAbsent(a,1) = null
putIfAbsent(a,9) = 1
replace(a,1,5)   = true
replace(a,1,7)   = false
remove(a,99)     = false
remove(a,5)      = true
map              = {}

replace(key, oldValue, newValue) and remove(key, value) are the two-argument compare-and-set forms: they succeed only if the current value is the one you expected, and return false otherwise. Together with putIfAbsent, compute, computeIfAbsent, computeIfPresent and merge, they cover the read-modify-write cycle without a gap.

ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
for (String w : "the quick brown fox the fox the".split(" ")) counts.merge(w, 1, Integer::sum);
System.out.println("merge counts     = " + counts);
System.out.println("compute          = " + counts.compute("fox", (k, v) -> v == null ? 1 : v * 10));
System.out.println("compute -> null  = " + counts.compute("brown", (k, v) -> null));
System.out.println("map              = " + counts);

merge counts     = {the=3, quick=1, brown=1, fox=2}
compute          = 20
compute -> null  = null
map              = {the=3, quick=1, fox=20}

The word counter written as counts.put(w, counts.getOrDefault(w, 0) + 1) is correct in one thread and a lost-update bug in several. merge is the same line with the gap removed. The mapping function must be short and must not touch the map, for the reason the Recursive update exception demonstrated above.

No null keys, no null values

Both are rejected, from the same line of putVal:

Exception in thread "main" java.lang.NullPointerException
	at java.base/java.util.concurrent.ConcurrentHashMap.putVal(ConcurrentHashMap.java:1011)
	at java.base/java.util.concurrent.ConcurrentHashMap.put(ConcurrentHashMap.java:1006)
	at ChmNullValue.main(ChmNullValue.java:5)

get(null)         java.lang.NullPointerException: Cannot invoke "Object.hashCode()" because "key" is null
containsKey(null) java.lang.NullPointerException: Cannot invoke "Object.hashCode()" because "key" is null

The value rejection is the one with a real reason behind it. In a HashMap, get returning null is already ambiguous — absent key, or key present with a null value — and you resolve it by calling containsKey. In a map that another thread may be writing, that resolution does not work: between your get and your containsKey the entry can appear or vanish, so the pair of calls can report a combination that was never true at any single instant. Forbidding null values removes the ambiguity entirely, and get returning null means one thing: no mapping, at some point during the call.

Which map for which requirement

Two of those need a caveat. Map.copyOf is a snapshot and Collections.unmodifiableMap is a view, which is easy to get backwards:

Map<String, Integer> src = new LinkedHashMap<>();
src.put("b", 2); src.put("a", 1);

Map<String, Integer> ro = Map.copyOf(src);
Map<String, Integer> un = Collections.unmodifiableMap(src);
src.put("c", 3);
System.out.println("unmodifiableMap is a live view: " + un);
System.out.println("copyOf is a snapshot:           " + ro);

unmodifiableMap is a live view: {b=2, a=1, c=3}
copyOf is a snapshot:           {b=2, a=1}

Both refuse put with UnsupportedOperationException. Only one of them stops changing.

Common mistakes with these maps

Reaching for a TreeMap and then never using NavigableMap. If all you needed was sorted output, sorting a list once is cheaper than paying O(log n) on every put and get. The tree earns its keep when you call floorEntry, subMap, headMap or pollFirstEntry.

Assuming subMap and headMap have the same inclusivity. headMap excludes, tailMap includes, subMap includes the low end and excludes the high end. Use the explicit boolean overloads and stop guessing.

Forgetting that a TreeMap comparator defines key identity. equals is never called. A case-insensitive comparator makes "Bolt" and "bolt" the same key, and a comparator that returns zero for two objects you consider different will silently merge them.

Building an LRU cache on the two-argument LinkedHashMap constructor. Without accessOrder = true you have a FIFO cache. It compiles, it evicts, and it evicts the wrong entries.

Using >= in removeEldestEntry. The method is called after the insertion, so size() >= capacity keeps one entry fewer than you asked for.

Treating ConcurrentHashMap as making your code thread-safe. It makes each call atomic. A get followed by a put is still two calls; use merge, compute or the compare-and-set replace instead.

Modifying a ConcurrentHashMap from inside computeIfAbsent. It throws IllegalStateException: Recursive update when the key lands in the same bin, and quietly works when it does not — which is worse, because your tests may never hit the failing case.

Reading size() on a ConcurrentHashMap for program control. It is documented as a monitoring figure. Use mappingCount() if you need the number, and do not branch on it.

Writing Hashtable in new code. There is no requirement for which it is the right answer.

FAQ

When should I use TreeMap instead of HashMap in Java?

When you need the keys in order, or when you need to ask about keys you do not have. Sorted iteration, firstKey/lastKey, a range like subMap("b", "s"), and above all a threshold lookup such as floorEntry(1999) are things a hash table cannot do at any price. The cost is O(log n) per operation instead of O(1) average, plus a requirement that the keys be mutually comparable. If you only want sorted output once at the end, sort a list instead.

What is the difference between floorKey and lowerKey?

floorKey(k) returns the greatest key less than or equal to k; lowerKey(k) returns the greatest key strictly less than k. They differ only when k is itself in the map: on the shipping table, floorKey(2000) is 2000 and lowerKey(2000) is 500. ceilingKey and higherKey are the mirror image going upwards. All four return null when no key qualifies.

Why does TreeMap throw NullPointerException on a null key?

Because it has to compare the key with something, and null.compareTo(...) is not a call that can be made. On an empty map the message says so verbatim: Cannot invoke "java.lang.Comparable.compareTo(Object)" because "k1" is null. get(null) and containsKey(null) throw as well. A null value is fine — values are stored, never compared.

How do I make an LRU cache in Java?

Extend LinkedHashMap, call super(16, 0.75f, true) so the map is in access order, and override removeEldestEntry to return size() > capacity;. That is the whole implementation. The map then moves an entry to the young end on every get, put, getOrDefault or merge, and drops the entry at the old end whenever an insertion pushes it over capacity. It is not thread-safe, and in access order even a get is a modification.

Does iterating a LinkedHashMap in access order change the order?

No. Iterating any of the views walks the list without touching it, so the order after a full for-each is the same as before. containsKey also leaves the order alone. What does move an entry is get, getOrDefault, put on an existing key, merge and the compute family.

What is the difference between Hashtable and ConcurrentHashMap?

Lock granularity, and null handling is identical. Hashtable declares synchronized on 26 of its 30 public methods, so every call — reads included — serialises on one lock over the whole map. ConcurrentHashMap has no synchronized methods at all; a write locks only the bin its key hashes to, and reads are not blocked by writes. Both reject null keys and null values. Hashtable also carries a pre-collections Enumeration API that does not detect concurrent modification, while its Map views do.

What does weakly consistent mean for a ConcurrentHashMap iterator?

It means the iterator reflects the table's state at some point at or since it was created, and never throws ConcurrentModificationException. Concretely: modifying the map during a single-threaded for-each aborts on HashMap, LinkedHashMap, TreeMap and Hashtable, and completes on ConcurrentHashMap. An entry inserted after the iterator started may or may not be visited depending on which bin it landed in relative to the iterator's position, so you cannot treat the iteration as either a snapshot or a fully live view.

Is ConcurrentHashMap enough to make my code thread-safe?

Only per call. Each individual get, put, merge or compute is atomic, but a sequence of them is not, so if (!map.containsKey(k)) map.put(k, v) still has a gap in the middle. The interface that fixes this is ConcurrentMap: putIfAbsent, replace(k, old, new), remove(k, value), compute, computeIfAbsent and merge each do the whole read-modify-write as one step. Anything spanning more than one key needs coordination the map cannot supply.

Conclusion

Four implementations, four different things bought with the same interface. TreeMap trades O(1) for O(log n) and gets ordering back, and the payoff is not the sorted toString but NavigableMap — floorEntry turning a whole band table into one call, subMap and headMap returning live views instead of copies, pollFirstEntry making the map into a queue. Its comparator is not a display preference: it is the definition of key identity, and equals is never consulted.

LinkedHashMap costs two references per entry and buys a promise about iteration order — and the promise it can make is not just insertion. Access order plus removeEldestEntry is a complete LRU cache in five lines, and the trace above shows why get is the operation that decides which entry survives. Hashtable buys thread safety with one lock over everything, and its own documentation tells you to use HashMap or ConcurrentHashMap instead. ConcurrentHashMap buys the same safety at bin granularity, and hands back a different contract in exchange: an iterator that never throws but never promises a snapshot either, a size() that is a monitoring figure, no null anywhere, and a set of compound operations that exist because get-then-put has a gap in the middle.

Next in this series: Queue, Deque, Stack and PriorityQueue — the collections where the interesting question is not what is stored under a key but which element comes out next, and why Stack is on the same list as Hashtable.