[Advanced Java] Map nâng cao trong Java: TreeMap, LinkedHashMap, Hashtable và ConcurrentHashMap

HashMap trả lời cực nhanh đúng một câu hỏi — cái gì đang nằm dưới key này — và không hứa gì thêm. Nó không hứa về thứ tự, không hứa an toàn khi hai thread cùng ghi, và không thể trả lời "key lớn nhất mà vẫn nhỏ hơn hoặc bằng 1999 là key nào" nếu không duyệt hết mọi entry bạn đã bỏ vào.

Các implementation còn lại của Map mỗi cái mua về một trong những cam kết đó, và mỗi cái trả bằng một loại chi phí khác nhau. TreeMap giữ key luôn sorted và biến các câu hỏi theo range thành một lệnh duy nhất. LinkedHashMap giữ thêm một linked list song song với table nên thứ tự duyệt là do bạn chọn. Hashtable lock cả map ở mọi lệnh và không nên xuất hiện trong code mới. ConcurrentHashMap chỉ lock từng bin và là lựa chọn ngay khi có thread thứ hai. Bài này nói về bốn cái đó, và về việc một yêu cầu cụ thể thật ra cần cái nào.

Mọi dòng output, mọi error message và mọi stack trace bên dưới đều lấy từ việc compile và chạy code thật trên OpenJDK 21.0.6. Bài viết không đưa ra bất kỳ con số thời gian nào — chi phí được mô tả theo cấu trúc, tức số phép so sánh hoặc mức chi tiết của lock. Những phát biểu về hành vi khi thật sự có nhiều thread là phát biểu về contract được document, trích từ source của JDK; một race condition không tái hiện được theo yêu cầu, nên không có kết luận nào ở đây được kiểm chứng bằng cách cho các thread đua nhau.

Bốn implementation sau lưng một interface

Cả năm map trong bài đều implement Map<K, V>, nên put, get, remove, containsKey, getOrDefault, merge và computeIfAbsent mang đúng một ý nghĩa ở mọi map. Đổi implementation chỉ là đổi một từ ở chỗ new. Cái thay đổi là toàn bộ những thứ mà interface Map cố tình không quy định:

Hai ô trong bảng đó gây bất ngờ đủ thường xuyên để phải nói ngay từ đầu. TreeMap chấp nhận value null nhưng từ chối key null, vì nó buộc phải đem key ra so sánh với thứ khác. Hashtable và ConcurrentHashMap từ chối cả hai, và các phần bên dưới trích nguyên văn exception.

Cây kế thừa cũng không giống điều phần lớn mọi người hình dung:

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 đúng nghĩa là một HashMap — vẫn bucket table đó, chỉ thêm một doubly linked list xâu qua các entry. Hashtable extend Dictionary, một abstract class có trước cả collections framework. Còn TreeMap và ConcurrentHashMap mỗi cái implement một interface con của Map, mang theo những operation mà cấu trúc của chúng cho phép: NavigableMap và ConcurrentMap. Phần lớn nội dung bài này nằm ở hai interface đó.

TreeMap giữ key luôn sorted

TreeMap là một red-black tree, không phải hash table. Trong một lượt lookup của TreeMap không có lời gọi hashCode() nào; mọi operation đều đi từ root xuống và so sánh key, tức O(log n) thay vì O(1), đổi lại là một thứ tự mà hash table về mặt cấu trúc không thể có.

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

Key đi vào lộn xộn nhưng đi ra đã sorted, và firstKey/lastKey là đường đi O(log n) tới node trái nhất và phải nhất chứ không phải một vòng quét. firstEntry và lastEntry trả về nguyên Map.Entry, tiết kiệm đúng lượt lookup thứ hai mà get(firstKey()) sẽ phải trả.

Còn một cặp nữa mang tính hủy. pollFirstEntry và pollLastEntry vừa trả entry vừa xóa nó, biến TreeMap thành một cấu trúc ưu tiên theo đúng tiêu chí bạn đã sort:

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}

Truy vấn theo ngưỡng mà HashMap không trả lời được

Đây chính là tình huống khiến TreeMap xứng đáng với cái log thừa ra. Bảng giá, khung điểm, bậc thuế và biểu cước vận chuyển đều cùng một hình dạng: một tập ngưỡng nhỏ, và câu hỏi dạng "giá trị này rơi vào khung nào". Cái key bạn có trong tay gần như không bao giờ là key có sẵn trong 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) nghĩa là key lớn nhất nhỏ hơn hoặc bằng g, kèm value của nó. Đó là toàn bộ phép tra khung, gọn trong một lệnh, chi phí O(log n), không có chuỗi if nào phải giữ đồng bộ với bảng và không có vòng lặp nào phải viết. Thêm một khung chỉ là thêm một dòng vào map. Khi tham số nhỏ hơn mọi key, floorEntry trả null chứ không ném exception — xem floorEntry(-1) ở trên — nên một bảng phải nhận mọi đầu vào thì nên bắt đầu từ giá trị nhỏ nhất của kiểu key.

Cũng bảng đó nhưng để trong HashMap thì không làm được. HASH.get(1999) ra null, vì 1999 không phải key, và không có cách nào hỏi hash table về hàng xóm của một key. Thứ bạn phải viết thay vào đó là một vòng quét toàn bộ 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

Nó ra kết quả đúng, và nó là O(n) theo số khung ở mọi lượt lookup, cộng thêm một lượt hash lookup nữa ở cuối. Hãy nhìn cả dòng in thứ tự duyệt: các khung ra khỏi HashMap theo một trật tự chẳng liên quan gì tới giá trị của chúng, và đó chính là lý do vòng lặp phải giữ biến best thay vì được phép dừng sớm.

floorKey, ceilingKey, lowerKey và higherKey

NavigableMap có bốn lookup lân cận, và điểm khác nhau duy nhất giữa chúng là tìm về hướng nào và có tính trường hợp trùng khớp hay không. Mỗi cái có dạng ...Key trả về key và dạng ...Entry trả về nguyên entry.

Hỏi trên bảng cước, với key 2000 vốn đang có trong map:

Còn với một key không có trong map, "m" trong map phụ tùng, cộng thêm hai đầu mút:

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

Với một key không nằm trong map thì floor và lower cho cùng đáp án, ceiling và higher cũng vậy — khác biệt inclusive/exclusive chỉ lộ ra khi trúng key thật. Cả bốn trả null khi không có key nào thỏa, và đó là trường hợp bạn buộc phải xử lý ở hai đầu range.

headMap, tailMap, subMap và descendingMap

Các method theo range trả về view, không phải bản sao. Mỗi cái đều tựa lên cây gốc, tạo ra gần như không tốn gì, và phản ánh cả những thay đổi diễn ra sau đó trên 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]

Mặc định của chúng bất đối xứng và đáng học thuộc: headMap loại bỏ cận của nó, tailMap giữ cận, còn subMap(from, to) giữ from và loại to — đúng quy ước nửa mở như String.substring. Cả ba đều có overload nhận cờ boolean inclusive, và dùng dạng tường minh là cách để thôi phải đoán.

Việc là view kéo theo hai hệ quả. Ghi qua view là ghi thẳng vào map gốc, và ghi ra ngoài range thì bị chặn:

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 cũng là view, nên xóa qua nó là xóa khỏi map gốc. Và một range đảo ngược là lỗi chứ không phải map rỗng:

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

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

Thứ tự đến từ Comparable hoặc từ một Comparator

TreeMap buộc phải so sánh key, nên nó cần một trong hai thứ: key implement Comparable, hoặc một Comparator truyền vào constructor. Nếu không có cái nào, lỗi nổ ngay ở lệnh put đầu tiên chứ không đợi tới lệnh thứ hai:

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)

Dòng "first put ok" không hề được in. Chèn vào một cây rỗng thì TreeMap vẫn gọi compare(key, key), thuần túy để lỗi kiểu lộ ra ngay lập tức thay vì đợi tới lúc có key thứ hai. Truyền vào một Comparator là xong, không phải đụng vào 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}

Comparator làm nhiều hơn là sắp thứ tự key — nó định nghĩa luôn thế nào là cùng một key. TreeMap không bao giờ gọi equals hay hashCode trên key; hai key là một khi phép so sánh trả về 0. Điều đó vừa dễ thấy vừa dễ dính:

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

Hai entry chứ không phải ba: "bolt" đã ghi đè "Bolt" nhưng giữ nguyên object key ban đầu, và "BOLT" vẫn tìm ra nó. Cũng dữ liệu đó bỏ vào HashMap sẽ thành ba entry riêng, vì String.equals phân biệt hoa thường. Không cái nào sai — nhưng một map có khái niệm bằng nhau khác với equals là map bạn phải chủ động biết mình đang dùng.

Comparator đó là một phần danh tính của map, và nó chỉ sống sót qua một trong hai copy constructor:

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) chép cả comparator; new TreeMap<>(Map) quay về natural ordering. Cho một map case-insensitive đi vòng qua một HashMap rồi quay lại là bạn nhận về một map phân biệt hoa thường mà chẳng có cảnh báo nào.

Cuối cùng là key null. TreeMap không so sánh null với thứ gì được nên từ chối thẳng — và trên một map rỗng, message NullPointerException của JDK nói rõ lý do:

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) và containsKey(null) cũng ném NullPointerException. Còn value null thì được nhận bình thường, vì value không bao giờ bị đem ra so sánh.

LinkedHashMap: insertion order, và access order

LinkedHashMap là một HashMap có thêm doubly linked list xâu qua toàn bộ entry. Lookup vẫn dùng bucket table và vẫn O(1) trung bình; cái list chỉ quyết định iterator nhìn thấy gì và theo thứ tự nào. Chi phí thêm là hai reference cho mỗi entry.

Mặc định list nằm theo insertion order, và nó ổn định qua đúng những thứ làm xáo trộn một 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]

Entry thứ mười ba kích hoạt lần resize làm đảo lộn hoàn toàn HashMap. LinkedHashMap cũng resize — cùng table, cùng load factor — và thứ tự duyệt của nó không nhúc nhích, vì cái list không phải cái table.

Một quy tắc về cái list đó: put lại một key đã có thì không làm nó đổi chỗ, nhưng xóa đi rồi thêm lại thì có.

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 là tham số constructor không ai dùng

LinkedHashMap có một constructor ba tham số mà tham số cuối tên là accessOrder. Đặt nó thành true thì list được duy trì theo thứ tự ít được dùng gần đây nhất đứng trước: mỗi lần truy cập, entry bị đẩy về cuối.

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]

Đọc kỹ output đó, vì "access" là một từ rất chính xác với danh sách thành viên khá bất ngờ. get, put lên key đã có, getOrDefault và merge đều tính là access và đều đẩy entry đi. containsKey thì không — nó trả lời mà không đụng vào list. Duyệt cũng không: vòng for-each đã đi qua cả bốn entry và để lại thứ tự y nguyên, và đó là điều khiến một map access order vẫn an toàn để in ra.

⚠️ Một LinkedHashMap ở chế độ access order bị thay đổi cấu trúc bởi chính một lệnh get. Hai thread chỉ gọi get trên cùng map vẫn là hai writer, và map lúc này không thread-safe hơn HashMap chút nào.

LRU cache với removeEldestEntry

Chỉ access order thôi mới là một nửa cache. Nửa còn lại là removeEldestEntry, một protected method mà map gọi sau mỗi lần chèn, đưa cho bạn entry đang nằm ở đầu cũ của list. Bản cài đặt gốc trả false nên không bao giờ có gì bị loại; override nó để trả true là entry đó bị bỏ. Toàn bộ cache gói trong năm dòng:

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;
    }
}

Với capacity bằng ba:

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

Dòng bị loại mới là dòng đáng chú ý. Khi d tới thì cache đã đầy, và cái ra đi là b — không phải a dù a được chèn đầu tiên, bởi vì lệnh get("a") ở dòng trên đã đẩy a về đầu trẻ. Hai bước sau, get("c") cứu c và lần này a là cái rơi ra. Đó đúng là chính sách LRU, và không dòng nào trong đó là code bạn viết: chỉ có accessOrder cộng với một return size() > capacity.

Ba chi tiết quyết định việc này chạy đúng hay âm thầm chạy sai:

• Điều kiện là size() > capacity, không phải >=. removeEldestEntry được gọi sau khi entry mới đã vào, nên map đang dư đúng một cái.
• super(16, 0.75f, true) là bắt buộc. Dùng constructor không tham số thì bạn được insertion order, removeEldestEntry vẫn chạy, và bạn vừa dựng xong một FIFO cache sẵn sàng loại đúng entry bạn vừa đọc.
• Method này là protected, nên chỉ dùng được từ một subclass. Đó là thiết kế có chủ đích, không phải mẹo lách.

Hashtable là legacy, và chính document của nó nói vậy

Hashtable có từ Java 1.0, trước khi collections framework tồn tại. Nó được gắn interface Map vào sau, và document của class nói thẳng một cách hiếm thấy về việc nên làm gì với nó:

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.

Tính thread-safe của nó là công cụ thô sơ nhất có thể: từ khóa synchronized gắn lên gần như mọi public method, nên mọi lệnh — kể cả mọi lệnh đọc — đều giành cùng một lock duy nhất trên chính object map.

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

Để ý dòng thứ ba: ConcurrentHashMap không có method synchronized nào cả. Nó thread-safe bằng một cơ chế hoàn toàn khác, và đó là nội dung của phần kế tiếp.

Hashtable cũng từ chối null ở cả hai vị trí, và hai lần từ chối đến từ hai chỗ khác nhau:

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

Từ chối key là hệ quả phụ — nó rơi ra từ việc gọi hashCode() trên key. Từ chối value là cố ý; stack trace dừng ngay tại một lệnh kiểm tra tường minh trong 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)

Còn một di tích legacy nữa: Hashtable có trước cả Iterator, nên nó còn phơi ra keys() và elements() trả về Enumeration. Những enumeration cũ đó không kiểm tra thay đổi, trong khi các collection view hiện đại thì có:

Enumeration completed, visited [b, a, c]

Map đã bị sửa ngay giữa lượt enumeration đó và không có gì phàn nàn. Iterator của keySet() trên cùng map ném ConcurrentModificationException trong đúng tình huống ấy. Hai API trên một object với hai kiểu hỏng khác nhau chính là thứ mà một class tích lũy được sau ba mươi năm.

Dùng gì thay thế. Map một thread thì dùng HashMap. Nhiều thread thì dùng ConcurrentHashMap. Collections.synchronizedMap(new HashMap<>()) cho bạn đúng mô hình lock của Hashtable áp lên một map hiện đại — một lock cho tất cả, và nó nhận key lẫn value null vì HashMap bên dưới nhận:

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

Đó là một wrapper hợp lý cho map hiếm khi bị đụng tới. Nó không phải thứ thay thế cho ConcurrentHashMap.

ConcurrentHashMap thực sự cam kết những gì

Thread là chủ đề của phần sau trong khóa này, nên phần này cố ý nói về contract thay vì về concurrency. Mọi điều bên dưới hoặc được trích từ document của class trong source JDK 21, hoặc được chứng minh bằng code một thread chạy thật làm lộ ra cơ chế bên trong.

Khác biệt lớn nhất so với Hashtable là mức chi tiết của lock. Hashtable giành một lock trên toàn bộ map ở mọi operation, nên một writer đụng vào một key sẽ loại trừ mọi writer và mọi reader ở tất cả các key khác. ConcurrentHashMap lock đúng cái bin mà key hash tới; hai writer có key rơi vào hai bin khác nhau thì hoàn toàn không đụng nhau, và đọc không bị ghi chặn.

Đó là lập luận về cấu trúc, không phải một benchmark: với một lock, mức tranh chấp tăng theo số thread đụng vào map; với lock theo bin, nó tăng theo số thread đụng vào cùng một bin, mà kích thước table và độ tán của hash giữ cho con số đó nhỏ. Bài viết này không công bố bất kỳ con số thời gian nào cho kết luận đó.

Bạn có thể thấy cái lock theo bin mà không cần thread thứ hai. computeIfAbsent chạy function của bạn trong lúc đang giữ lock của bin, nên một function ghi ngược vào chính bin đó sẽ tự khóa chính mình — và JDK phát hiện ra rồi ném exception:

ConcurrentHashMap<String, Integer> m = new ConcurrentHashMap<>();
m.computeIfAbsent("a", k -> {
    m.put("ab", 2);      // "ab" hash vào đúng bin của "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)

Đổi key được chèn thành một key hash đi chỗ khác thì đúng đoạn code đó chạy trót lọt:

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

{a=1, b=2}

Cùng một operation, cùng một thread, hai kết cục khác nhau chỉ do key thứ hai rơi vào bin nào. Đó là mức chi tiết của lock được nhìn thấy tận mắt. Quy tắc thực dụng rút ra: đừng bao giờ sửa một ConcurrentHashMap từ bên trong chính function của compute, computeIfAbsent hay merge của nó.

Iterator là weakly consistent, không phải fail-fast

Iterator của HashMap ném ConcurrentModificationException ngay khi map bị thay đổi cấu trúc bên dưới nó. Iterator của ConcurrentHashMap không bao giờ ném. Document viết rõ:

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.

Từ khóa ở đây là weakly consistent, và nó quan sát được chỉ với một 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]

Bốn map bỏ cuộc; ConcurrentHashMap đi hết vòng. Chú ý cái nó không làm: nó không hề thấy zz, key được thêm giữa lượt duyệt. Đó là nửa còn lại của "weakly consistent" — một entry chèn vào sau khi iterator bắt đầu thì có thể xuất hiện, có thể không, và không có quy tắc nào để bạn dựa vào. Chèn năm key khác nhau tại cùng một điểm trong cùng một lượt duyệt thì iterator thấy hai:

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 và x rơi vào những bin iterator chưa đi tới nên chúng hiện ra. zz, aa và q rơi lại phía sau nên không. Vậy một lượt duyệt ConcurrentHashMap không phải snapshot mà cũng không phải live view — nó nằm đâu đó ở giữa, và đó là toàn bộ cam kết bạn có cũng như toàn bộ thứ bạn được phép viết code dựa vào.

Điểm yếu tương tự áp cho các method tổng hợp. size(), isEmpty() và containsValue() được document là phản ánh "transient states that may be adequate for monitoring or estimation purposes, but not for program control". mappingCount() mới là bản nên dùng — nó trả long thay vì int, và document nói thẳng "the value returned is an estimate; the actual count may differ if there are concurrent insertions or removals". Trong code một thread thì cả hai đều chính xác:

size()           = 3
mappingCount()   = 3

Các compound operation mới là thứ atomic

get là atomic. put là atomic. get rồi put là hai operation với một khoảng trống ở giữa, và không có gì trong ConcurrentHashMap bịt hộ bạn khoảng trống ấy. Đó là lý do ConcurrentMap tồn tại như một interface riêng: nó đặc tả những compound operation đúng là một bước atomic.

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) và remove(key, value) là hai dạng compare-and-set: chúng chỉ thành công khi value hiện tại đúng bằng cái bạn kỳ vọng, còn không thì trả false. Cùng với putIfAbsent, compute, computeIfAbsent, computeIfPresent và merge, chúng phủ hết chu trình read-modify-write mà không để lại khoảng trống nào.

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}

Bộ đếm từ viết theo kiểu counts.put(w, counts.getOrDefault(w, 0) + 1) thì đúng với một thread và là bug mất cập nhật với nhiều thread. merge là đúng dòng đó nhưng đã bỏ khoảng trống đi. Function truyền vào phải ngắn và không được đụng vào map, đúng vì lý do mà exception Recursive update bên trên đã minh họa.

Không key null, không value null

Cả hai đều bị từ chối, từ cùng một dòng trong 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

Việc từ chối value mới là cái có lý do thật phía sau. Trong HashMap, get trả null vốn đã nhập nhằng — key vắng mặt, hay key có mặt với value null — và bạn gỡ nhập nhằng bằng containsKey. Trong một map mà thread khác có thể đang ghi, cách gỡ đó không còn dùng được: giữa lệnh get và lệnh containsKey của bạn, entry có thể xuất hiện hoặc biến mất, nên cặp lệnh đó có thể báo về một tổ hợp chưa từng đúng ở bất kỳ thời điểm nào. Cấm value null là xóa sạch nhập nhằng, và get trả null chỉ còn một nghĩa: không có mapping, tại một thời điểm nào đó trong lúc gọi.

Chọn map nào cho yêu cầu nào

Hai dòng cuối cần một lưu ý. Map.copyOf là snapshot còn Collections.unmodifiableMap là view, và rất dễ nhớ ngược:

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}

Cả hai đều từ chối put bằng UnsupportedOperationException. Nhưng chỉ một trong hai là ngừng thay đổi.

Những lỗi thường gặp với các map này

Chọn TreeMap rồi không bao giờ dùng tới NavigableMap. Nếu tất cả những gì bạn cần là output đã sorted thì sort một list một lần rẻ hơn là trả O(log n) ở mọi put và get. Cái cây chỉ đáng tiền khi bạn gọi floorEntry, subMap, headMap hay pollFirstEntry.

Tưởng subMap và headMap cùng quy ước inclusive. headMap loại cận, tailMap giữ cận, subMap giữ đầu thấp và loại đầu cao. Dùng overload boolean tường minh để khỏi phải đoán.

Quên rằng comparator của TreeMap định nghĩa danh tính key. equals không bao giờ được gọi. Một comparator case-insensitive biến "Bolt" và "bolt" thành một key, và một comparator trả 0 cho hai object mà bạn coi là khác nhau sẽ âm thầm gộp chúng lại.

Dựng LRU cache trên constructor hai tham số của LinkedHashMap. Không có accessOrder = true thì bạn có một FIFO cache. Nó compile được, nó vẫn loại entry, và nó loại nhầm entry.

Dùng >= trong removeEldestEntry. Method được gọi sau khi đã chèn, nên size() >= capacity giữ ít hơn bạn yêu cầu đúng một entry.

Coi ConcurrentHashMap là thứ làm code của bạn thread-safe. Nó làm từng lệnh trở thành atomic. Một get rồi một put vẫn là hai lệnh; hãy dùng merge, compute hoặc dạng compare-and-set của replace.

Sửa ConcurrentHashMap từ bên trong computeIfAbsent. Nó ném IllegalStateException: Recursive update khi key rơi vào cùng bin, và chạy êm ru khi không — điều này còn tệ hơn, vì test của bạn có thể không bao giờ chạm vào trường hợp hỏng.

Đọc size() của ConcurrentHashMap để điều khiển luồng chương trình. Nó được document là con số dùng để monitoring. Cần số lượng thì dùng mappingCount(), và đừng rẽ nhánh dựa trên nó.

Viết Hashtable trong code mới. Không có yêu cầu nào mà nó là câu trả lời đúng.

FAQ

Khi nào nên dùng TreeMap thay cho HashMap trong Java?

Khi bạn cần key theo thứ tự, hoặc khi bạn cần hỏi về những key mà bạn không có trong tay. Duyệt sorted, firstKey/lastKey, một range như subMap("b", "s"), và trên hết là truy vấn theo ngưỡng kiểu floorEntry(1999) — đó là những thứ hash table không làm được với bất kỳ giá nào. Cái giá là O(log n) mỗi operation thay vì O(1) trung bình, cộng với yêu cầu các key phải so sánh được với nhau. Nếu bạn chỉ muốn output đã sorted một lần ở cuối thì hãy sort một list.

floorKey và lowerKey khác nhau ở đâu?

floorKey(k) trả về key lớn nhất nhỏ hơn hoặc bằng k; lowerKey(k) trả về key lớn nhất nhỏ hơn hẳn k. Chúng chỉ khác nhau khi bản thân k có trong map: trên bảng cước, floorKey(2000) ra 2000 còn lowerKey(2000) ra 500. ceilingKey và higherKey là bản đối xứng đi lên. Cả bốn trả null khi không có key nào thỏa.

Vì sao TreeMap ném NullPointerException với key null?

Vì nó buộc phải đem key ra so sánh với thứ khác, mà null.compareTo(...) là lời gọi không thể thực hiện. Trên map rỗng, message nói đúng nguyên văn điều đó: Cannot invoke "java.lang.Comparable.compareTo(Object)" because "k1" is null. get(null) và containsKey(null) cũng ném. Còn value null thì không sao — value chỉ được lưu, không bao giờ bị so sánh.

Làm LRU cache trong Java thế nào?

Extend LinkedHashMap, gọi super(16, 0.75f, true) để map ở chế độ access order, rồi override removeEldestEntry thành return size() > capacity;. Đó là toàn bộ phần cài đặt. Map sẽ đẩy entry về đầu trẻ ở mỗi get, put, getOrDefault hay merge, và bỏ entry ở đầu cũ mỗi khi một lần chèn làm vượt capacity. Nó không thread-safe, và ở chế độ access order thì ngay cả get cũng là một thay đổi.

Duyệt một LinkedHashMap ở access order có làm đổi thứ tự không?

Không. Duyệt bất kỳ view nào cũng chỉ đi dọc list mà không đụng vào nó, nên thứ tự sau một vòng for-each y hệt lúc trước. containsKey cũng để nguyên thứ tự. Thứ thật sự làm entry đổi chỗ là get, getOrDefault, put lên key đã có, merge và họ compute.

Hashtable và ConcurrentHashMap khác nhau ở đâu?

Ở mức chi tiết của lock, còn cách xử lý null thì giống hệt. Hashtable khai báo synchronized trên 26 trong 30 public method, nên mọi lệnh — kể cả đọc — đều xếp hàng trên một lock trùm cả map. ConcurrentHashMap không có method synchronized nào; một lệnh ghi chỉ lock đúng cái bin mà key hash tới, và đọc không bị ghi chặn. Cả hai đều từ chối key null và value null. Hashtable còn mang theo API Enumeration có trước collections, và API đó không phát hiện thay đổi đồng thời trong khi các Map view của nó thì có.

Weakly consistent nghĩa là gì với iterator của ConcurrentHashMap?

Nghĩa là iterator phản ánh trạng thái của table tại một thời điểm nào đó bằng hoặc sau lúc nó được tạo, và không bao giờ ném ConcurrentModificationException. Cụ thể: sửa map giữa một vòng for-each một thread sẽ làm HashMap, LinkedHashMap, TreeMap và Hashtable bỏ cuộc, còn ConcurrentHashMap đi hết vòng. Một entry chèn vào sau khi iterator bắt đầu thì có được duyệt hay không tùy vào bin của nó nằm trước hay sau vị trí hiện tại của iterator, nên bạn không được coi lượt duyệt đó là snapshot mà cũng không được coi là live view đầy đủ.

Chỉ dùng ConcurrentHashMap đã đủ để code thread-safe chưa?

Chỉ đủ ở mức từng lệnh. Mỗi get, put, merge hay compute riêng lẻ là atomic, nhưng một chuỗi các lệnh đó thì không, nên if (!map.containsKey(k)) map.put(k, v) vẫn có khoảng trống ở giữa. Interface xử lý chuyện này là ConcurrentMap: putIfAbsent, replace(k, old, new), remove(k, value), compute, computeIfAbsent và merge mỗi cái làm trọn read-modify-write trong một bước. Còn thứ gì trải trên nhiều key thì cần một cơ chế phối hợp mà map không cung cấp được.

Kết luận

Bốn implementation, bốn thứ khác nhau mua được bằng cùng một interface. TreeMap đánh đổi O(1) lấy O(log n) và nhận lại thứ tự, mà phần thưởng không phải là cái toString đã sorted mà là NavigableMap — floorEntry biến cả một bảng khung thành một lệnh, subMap và headMap trả về view sống chứ không phải bản sao, pollFirstEntry biến map thành hàng đợi. Comparator của nó không phải tùy chọn hiển thị: nó là định nghĩa danh tính của key, và equals không bao giờ được hỏi tới.

LinkedHashMap tốn hai reference mỗi entry và mua về một cam kết về thứ tự duyệt — mà cam kết nó đưa ra được không chỉ là insertion. Access order cộng removeEldestEntry là một LRU cache hoàn chỉnh trong năm dòng, và cái trace ở trên cho thấy vì sao get mới là lệnh quyết định entry nào sống sót. Hashtable mua tính thread-safe bằng một lock trùm tất cả, và chính document của nó bảo bạn dùng HashMap hoặc ConcurrentHashMap thay thế. ConcurrentHashMap mua đúng tính an toàn đó ở mức từng bin, và đưa lại cho bạn một contract khác: một iterator không bao giờ ném nhưng cũng không hứa hẹn snapshot, một size() chỉ để monitoring, không null ở đâu cả, và một bộ compound operation tồn tại chính vì get rồi put có khoảng trống ở giữa.

Bài tiếp theo trong series: Queue, Deque, Stack và PriorityQueue — những collection mà câu hỏi thú vị không phải là cái gì nằm dưới một key, mà là phần tử nào sẽ ra tiếp theo, và vì sao Stack bị xếp cùng danh sách với Hashtable.