[Java Basics] HashMap trong Java: put, get, merge và quy tắc hashCode/equals

Một list trả lời đúng một câu hỏi: phần tử ở index 3 là gì. Một map trả lời câu khác: cái gì đang được lưu dưới key này. HashMap trả lời câu đó trong thời gian gần như không đổi, dù nó chứa mười entry hay mười triệu — đó là lý do nó xuất hiện trong hầu hết chương trình Java có độ phức tạp vừa trở lên.

Tốc độ đó được đánh đổi bằng một quy tắc ràng buộc giữa hashCode() và equals() mà compiler không kiểm tra giúp bạn. Phá vỡ nó thì không có gì bị throw cả — entry vẫn nằm trong map, vẫn được size() đếm, vẫn được toString() in ra, và đơn giản là không bao giờ tìm lại được nữa. Bài này đi qua API trước, rồi tới quy tắc, rồi tới chuyện gì thực sự xảy ra khi bạn làm sai.

Mọi dòng output, thông báo lỗi và con số đếm bên dưới đều được tạo ra bằng cách compile và chạy code thật trên OpenJDK 21.0.6. Chi phí được đo bằng số lần gọi hashCode() và equals() từ các class key có gắn counter, không bao giờ bằng thời gian chạy — counter cho cùng một con số trên mọi máy, còn đồng hồ bấm giờ thì không.

Vì sao Map không phải là Collection

Map thuộc về Java collections framework, nhưng nó không phải là một Collection. Nó là một interface riêng với hệ thống phân cấp riêng, và compiler nói rất thẳng:

import java.util.*;

public class NotCollection {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        Collection<String> c = stock;
        for (String s : stock) {
            System.out.println(s);
        }
    }
}

NotCollection.java:6: error: incompatible types: Map<String,Integer> cannot be converted to Collection<String>
        Collection<String> c = stock;
                               ^
NotCollection.java:7: error: for-each not applicable to expression type
        for (String s : stock) {
                        ^
  required: array or java.lang.Iterable
  found:    Map<String,Integer>
2 errors

Lý do nằm ở cấu trúc. Collection<E> lưu từng phần tử đơn lẻ thuộc một type E. Map lưu cặp, và không có một E nào mô tả được một cặp mà không phải bịa ra một type mới. Map cũng không extend Iterable, nên vòng for rút gọn từ chối nó ngay tại chỗ.

Thứ map cho bạn thay vì khả năng iterable là ba view — keySet(), values() và entrySet() — và cả ba đều là Collection. Phần sau của bài sẽ nói kỹ về chúng.

Tạo HashMap và những operation dùng nhiều nhất

Khai báo bằng interface, khởi tạo bằng implementation. Cả hai type argument đều phải là reference type, nên một value kiểu int sẽ thành Integer:

import java.util.HashMap;
import java.util.Map;

public class Basics {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("bolt", 120);
        stock.put("nut", 340);
        stock.put("washer", 85);

        System.out.println("size          = " + stock.size());
        System.out.println("get bolt      = " + stock.get("bolt"));
        System.out.println("get screw     = " + stock.get("screw"));
        System.out.println("containsKey   = " + stock.containsKey("screw"));
        System.out.println("containsValue = " + stock.containsValue(340));

        Integer prev = stock.put("bolt", 200);
        System.out.println("put returns   = " + prev);
        System.out.println("bolt now      = " + stock.get("bolt"));

        Integer gone = stock.remove("washer");
        System.out.println("remove returns= " + gone);
        System.out.println("remove missing= " + stock.remove("washer"));
        System.out.println("size          = " + stock.size());
        System.out.println("map           = " + stock);
    }
}

size          = 3
get bolt      = 120
get screw     = null
containsKey   = false
containsValue = true
put returns   = 120
bolt now      = 200
remove returns= 85
remove missing= null
size          = 2
map           = {bolt=200, nut=340}

Có ba điểm trong output đó đáng ghim lại.

Key là duy nhất, value thì không. put lên một key đã tồn tại sẽ thay value và trả về value cũ. Giá trị trả về đó là thông tin miễn phí mà hầu hết code vứt đi — nó cho bạn biết bạn vừa ghi đè lên cái gì đó hay chưa.

containsValue không phải containsKey. containsKey là một lần hash lookup và gần như không đổi về thời gian. containsValue không có index nào để dựa vào nên phải quét toàn bộ entry, tức là O(n). Gọi nó trong vòng lặp là cách kinh điển để biến một chương trình nhanh thành một chương trình chậm.

remove trả về value cũ, hoặc null nếu chẳng có gì ở đó. Giống put, nó đưa lại thứ mà nó vừa đẩy ra.

Vì sao get trả về null lại mơ hồ

HashMap cho phép value là null, và cho phép đúng một key null. Điều đó khiến null từ get mang hai ý nghĩa hoàn toàn khác nhau:

import java.util.HashMap;
import java.util.Map;

public class NullAmbig {
    public static void main(String[] args) {
        Map<String, String> config = new HashMap<>();
        config.put("host", "localhost");
        config.put("proxy", null);

        System.out.println("get(\"proxy\")       = " + config.get("proxy"));
        System.out.println("get(\"region\")      = " + config.get("region"));
        System.out.println("containsKey proxy  = " + config.containsKey("proxy"));
        System.out.println("containsKey region = " + config.containsKey("region"));
        System.out.println("size = " + config.size());

        System.out.println("getOrDefault region = " + config.getOrDefault("region", "us-east"));
        System.out.println("getOrDefault proxy  = " + config.getOrDefault("proxy", "us-east"));
    }
}

get("proxy")       = null
get("region")      = null
containsKey proxy  = true
containsKey region = false
size = 2
getOrDefault region = us-east
getOrDefault proxy  = null

Hai lời gọi get trả về cùng một thứ nhưng mang ý nghĩa ngược nhau: "proxy" có tồn tại và mang value null, còn "region" thì không tồn tại. Chỉ containsKey phân biệt được hai trường hợp đó.

getOrDefault cũng không gỡ được sự mơ hồ này — hãy nhìn dòng cuối. Nó chỉ thay bằng default khi key không tồn tại, mà một key được map tới null thì vẫn là tồn tại, nên nó trả về null. Đó là hành vi đúng như tài liệu mô tả, nhưng nó có nghĩa getOrDefault là tiện ích cho những map không bao giờ chứa null, chứ không phải một cơ chế chống null.

⚠️ Cách sửa đơn giản nhất là đừng bao giờ đặt null vào map. Khi đó null từ get chỉ còn đúng một nghĩa, getOrDefault hành xử như bạn mong đợi, và bạn không bao giờ cần cặp containsKey rồi get — vốn là hai lần hash lookup cho việc mà một lần là đủ.

putIfAbsent, merge và computeIfAbsent

Chu trình đọc - sửa - ghi lại, tức là lấy value hiện tại, chỉnh nó, rồi put ngược vào, là thứ người ta làm nhiều nhất với map, và Map có ba method gộp cả chu trình đó vào một lời gọi.

putIfAbsent(k, v) chỉ lưu v khi key chưa có value, và trả về thứ đã nằm sẵn ở đó:

Map<String, Integer> m = new HashMap<>();
System.out.println(m.putIfAbsent("a", 1));   // null  - nothing was there, 1 is stored
System.out.println(m.putIfAbsent("a", 99));  // 1     - already present, 99 discarded
System.out.println(m.get("a"));              // 1

null
1
1

Chú ý cách diễn đạt chính xác: chưa có value, không phải chưa có key. Một key được map thẳng tới null bị tính là chưa có, nên putIfAbsent sẽ ghi đè lên nó. Đó chính là sự mơ hồ của null ở phần trước xuất hiện lần thứ hai.

Đếm từ bằng merge

Đếm là ví dụ sách giáo khoa của đọc - sửa - ghi lại. Viết tay thì cần một lần kiểm tra null cho lần đầu gặp mỗi từ:

import java.util.HashMap;
import java.util.Map;

public class WordCount {
    public static void main(String[] args) {
        String text = "the quick brown fox jumps over the lazy dog the fox";

        Map<String, Integer> counts = new HashMap<>();
        for (String word : text.split(" ")) {
            counts.put(word, counts.getOrDefault(word, 0) + 1);
        }

        System.out.println(counts);
        System.out.println("distinct words = " + counts.size());
        System.out.println("the = " + counts.get("the"));
        System.out.println("cat = " + counts.get("cat"));
    }
}

{the=3, over=1, quick=1, lazy=1, jumps=1, brown=1, dog=1, fox=2}
distinct words = 8
the = 3
cat = null

merge(key, value, remappingFunction) nói đúng ngần đó trong một lời gọi: lưu value nếu key chưa tồn tại, còn nếu đã tồn tại thì thay value hiện tại bằng f(current, value).

for (String word : text.split(" ")) {
    counts.merge(word, 1, Integer::sum);
}

{over=1, the=3, quick=1, lazy=1, jumps=1, brown=1, dog=1, fox=2}

Vẫn tám key đó, vẫn tám con số đó — nhưng thứ tự in ra đã khác. counts.equals(other) cho true với hai map này trong khi counts.toString().equals(other.toString()) cho false. Hai cách viết mang cùng ý nghĩa với bạn vẫn có thể để lại trạng thái bên trong khác nhau, và thứ tự bạn nhìn thấy là hệ quả của trạng thái đó. Đừng suy diễn gì từ nó; phần nói về thứ tự bên dưới sẽ quay lại chuyện này.

Một tính chất nữa của merge: nếu remapping function trả về null, entry sẽ bị xóa. Nhờ vậy chuyện giảm về không gói gọn trong một dòng:

Map<String, Integer> stock = new HashMap<>();
stock.put("bolt", 3);
stock.merge("bolt", -3, (old, delta) -> old + delta == 0 ? null : old + delta);
System.out.println(stock + " containsKey=" + stock.containsKey("bolt"));

{} containsKey=false

Gom nhóm bằng computeIfAbsent

Gom nhóm cần một container cho mỗi key, và bản viết ngây thơ sẽ tạo container đó trước cả khi biết có cần hay không. computeIfAbsent(key, f) chỉ gọi f khi key chưa có value, lưu kết quả lại, và trả về value trong cả hai trường hợp — nên kết quả luôn là thứ bạn có thể gọi method lên ngay:

import java.util.*;

public class Grouping {
    public static void main(String[] args) {
        String[] names = {"Anh", "Binh", "Alice", "Chi", "Bob", "An"};

        Map<Character, List<String>> byLetter = new HashMap<>();
        for (String name : names) {
            byLetter.computeIfAbsent(name.charAt(0), k -> new ArrayList<>()).add(name);
        }

        System.out.println(byLetter);
    }
}

{A=[Anh, Alice, An], B=[Binh, Bob], C=[Chi]}

Lambda chạy một lần cho mỗi chữ cái khác nhau, chứ không phải một lần cho mỗi tên — nếu key đã có sẵn, computeIfAbsent trả về list cũ mà không hề gọi tới lambda. Kiểm chứng bằng cách throw ngay bên trong nó:

Map<String, List<String>> g = new HashMap<>();
g.put("a", new ArrayList<>(List.of("kept")));
g.computeIfAbsent("a", k -> { throw new IllegalStateException("not called"); }).add("added");
System.out.println(g);

{a=[kept, added]}

Cách HashMap chọn bucket cho một key

Bên trong, HashMap là một mảng — gọi là table — mà mỗi ô của nó gọi là bucket. Đặt một key vào cần ba bước: gọi hashCode() trên nó, trộn các bit cao của giá trị đó xuống các bit thấp, rồi cắt lấy đủ số bit thấp để ra một index trong table.

static int bucketOf(String key, int tableLength) {
    int h = key.hashCode();
    return (tableLength - 1) & (h ^ (h >>> 16));
}

Phép cắt này hoạt động được vì độ dài table luôn là lũy thừa của hai, nên length - 1 là một dãy bit 1 và phép & trở thành một phép chia lấy dư rất rẻ. Bước h ^ (h >>> 16) tồn tại bởi vì phép cắt đó vứt bỏ toàn bộ bit cao: không có bước trộn, hai key chỉ khác nhau từ bit 16 trở lên sẽ va nhau mọi lúc. Chạy thử trên tám từ của ví dụ đếm từ:

Tám key, mười sáu bucket, và chúng rơi vào bảy ô. Chín bucket rỗng, còn một ô — bucket 0 — chứa một chain gồm hai entry. Chuyện đó là bình thường và nó chính là ý nghĩa thực tế của "trung bình hằng số": get("dog") tính một index rồi đọc một ô, còn get("over") tính một index rồi đi hết một chain hai phần tử, so key bằng equals() cho tới khi khớp.

Từ việc table là một mảng còn suy ra hai điều nữa:

Table sẽ lớn lên. HashMap khởi đầu với 16 bucket và load factor 0.75, nên nó resize khi entry thứ mười ba xuất hiện — nhân đôi table và tính lại index của mọi entry. Vì vậy thêm đúng một entry cũng có thể đảo lại thứ tự của cả map:

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

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

Bạn có thể cấp phát trước. new HashMap<>(64) tạo sẵn một table lớn hơn. Việc đó đáng làm khi bạn đã biết sắp có khoảng bao nhiêu entry và muốn tránh chi phí rehash mỗi lần resize; nó không đáng làm theo kiểu phòng xa vô căn cứ.

Quy tắc hashCode và equals

Toàn bộ những gì ở trên dựa trên đúng một quy tắc, viết trong tài liệu của Object.hashCode():

Nếu hai object bằng nhau theo equals(Object), thì gọi hashCode() trên từng object phải cho ra cùng một số nguyên.

Chiều suy ra chỉ đi một hướng. Hai object bằng nhau bắt buộc phải trùng hash code; hai object không bằng nhau được phép trùng hash code, và với chỉ 2³² giá trị hash code khả dĩ thì đôi khi chúng buộc phải trùng.

Lý do quy tắc này tồn tại đã nằm sẵn trong hình. Một lần lookup dùng hashCode() để chọn bucket, và chỉ dùng equals() để so với những gì nằm trong bucket đó. Nếu hai key bằng nhau cho ra hash code khác nhau, lookup không bao giờ tới được bucket mà entry đang thực sự nằm, và equals() không bao giờ có cơ hội để nói "đúng rồi".

Override equals mà quên hashCode: entry biến mất

BadPoint override equals hoàn toàn đúng và để nguyên hashCode thừa kế từ Object, vốn dựa trên định danh của object:

import java.util.*;

class BadPoint {
    final int x, y;

    BadPoint(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof BadPoint)) return false;
        BadPoint p = (BadPoint) o;
        return x == p.x && y == p.y;
    }

    @Override
    public String toString() { return "(" + x + "," + y + ")"; }
}

public class Contract {
    public static void main(String[] args) {
        BadPoint a = new BadPoint(1, 2);
        BadPoint b = new BadPoint(1, 2);

        System.out.println("a.equals(b)         = " + a.equals(b));
        System.out.println("a.hashCode()        = " + a.hashCode());
        System.out.println("b.hashCode()        = " + b.hashCode());

        Map<BadPoint, String> map = new HashMap<>();
        map.put(a, "origin-ish");
        System.out.println("map.get(b)          = " + map.get(b));
        System.out.println("map.containsKey(b)  = " + map.containsKey(b));

        map.put(b, "again");
        System.out.println("map.size()          = " + map.size());
        System.out.println("map                 = " + map);
    }
}

a.equals(b)         = true
a.hashCode()        = 692404036
b.hashCode()        = 1554874502
map.get(b)          = null
map.containsKey(b)  = false
map.size()          = 2
map                 = {(1,2)=origin-ish, (1,2)=again}

Hai con số hash code phụ thuộc vào lần chạy JVM; việc chúng khác nhau thì không. Hãy đọc kỹ hai dòng cuối. Map đang chứa hai entry mà key của chúng tự khai là bằng nhau và in ra y hệt nhau, và sẽ không có lời gọi get nào với một (1,2) vừa tạo lấy lại được entry nào trong hai entry đó. Không có gì bị throw. Không có cảnh báo nào. Dữ liệu chỉ đơn giản là không với tới được nữa.

Thêm một hashCode tính từ đúng những field mà equals dùng là xong:

@Override
public int hashCode() {
    return Objects.hash(x, y);
}

a.equals(b)         = true
a.hashCode()        = 994
b.hashCode()        = 994
map.get(b)          = origin-ish
map.size()          = 1
map                 = {(1,2)=again}

Quy tắc rất máy móc: hashCode phải được tính từ đúng những field mà equals so sánh — không ít hơn, và không nhiều hơn. Ít hơn nghĩa là hai object khác nhau không bao giờ được tách sang hai bucket khác nhau, chuyện đó hợp lệ nhưng chậm. Nhiều hơn nghĩa là hai object bằng nhau có thể nhận hash code khác nhau, và đó chính là con bug ở trên.

Key bị thay đổi sau khi đã lưu

Quy tắc này không phải một lần kiểm tra duy nhất lúc put. Map đã tính index bucket từ hash code của key và cất entry ở đó; nếu hash code của key thay đổi sau đó, entry vẫn nằm nguyên chỗ cũ còn key thì không còn trỏ tới nó nữa.

import java.util.*;

class Tag {
    String name;

    Tag(String name) { this.name = name; }

    @Override
    public boolean equals(Object o) {
        return o instanceof Tag && name.equals(((Tag) o).name);
    }

    @Override
    public int hashCode() { return name.hashCode(); }

    @Override
    public String toString() { return "Tag(" + name + ")"; }
}

public class MutableKey {
    public static void main(String[] args) {
        Tag t = new Tag("draft");
        Map<Tag, String> m = new HashMap<>();
        m.put(t, "v1");
        System.out.println("before: get(t) = " + m.get(t));

        t.name = "final";

        System.out.println("after:  get(t)               = " + m.get(t));
        System.out.println("after:  get(new Tag(\"final\")) = " + m.get(new Tag("final")));
        System.out.println("after:  get(new Tag(\"draft\")) = " + m.get(new Tag("draft")));
        System.out.println("after:  remove(t)            = " + m.remove(t));
        System.out.println("after:  size                 = " + m.size());
        System.out.println("after:  map                  = " + m);
    }
}

before: get(t) = v1
after:  get(t)               = null
after:  get(new Tag("final")) = null
after:  get(new Tag("draft")) = null
after:  remove(t)            = null
after:  size                 = 1
after:  map                  = {Tag(final)=v1}

Entry đó không với tới được bằng bất kỳ key nào. Tag("final") hash sang bucket mới, nơi chẳng có gì được lưu. Tag("draft") hash đúng vào bucket mà entry đang nằm, nhưng object key của entry giờ khai là "final" nên equals nói không. remove thất bại vì cùng lý do đó, nên entry thậm chí không xóa được — chỉ có thể chạm tới nó bằng cách duyệt map, và đó là lý do toString vẫn in nó ra. Trong một map sống lâu thì đây là một memory leak.

Cách phòng vệ là một quy tắc không có ngoại lệ: key của map phải immutable, hoặc chí ít là không bao giờ được sửa ở những field nuôi hashCode và equals. String, các boxed primitive, LocalDate và record có component immutable đều an toàn. Một class mutable do bạn tự viết, hay một ArrayList, thì không.

Cái giá của một hashCode hằng số

hashCode trả về hằng số là một implementation hợp lệ. Khi đó mọi object nằm chung một bucket, và mọi lookup thoái hóa thành quét bucket đó bằng equals(). Để đo chuyện này mà không cần đồng hồ bấm giờ, hãy đếm số lần gọi equals bằng một static counter trên class key:

import java.util.*;

class Sku {
    static int equalsCalls = 0;
    final String code;

    Sku(String code) { this.code = code; }

    @Override
    public boolean equals(Object o) {
        equalsCalls++;
        return o instanceof Sku && code.equals(((Sku) o).code);
    }

    @Override
    public int hashCode() { return code.hashCode(); }   // or: return 42;
}

Mười nghìn entry, rồi một lần get cho mỗi entry:

Một lần gọi equals cho mỗi lookup, so với khoảng năm nghìn lần. Mọi key đều rơi vào cùng một bucket, nên mỗi lookup trung bình quét nửa bucket đó — map đã biến thành một phép tìm kiếm tuyến tính khoác áo HashMap. Lưu ý rằng đây vẫn là một map đúng: mọi kết quả nó trả về đều chính xác. Chỉ có hiệu năng sụp đổ, và đó là lý do không có gì trong type system hay trong bộ test bắt được lỗi này.

Duyệt một HashMap

Map không iterable, nên bạn duyệt một trong ba view của nó. Cả ba đều là cửa sổ sống nhìn vào cùng một map, không phải bản sao.

import java.util.*;

public class Iterate {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("bolt", 120);
        stock.put("nut", 340);
        stock.put("washer", 85);

        for (Map.Entry<String, Integer> e : stock.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }

        stock.forEach((key, value) -> System.out.println(key + " = " + value));
    }
}

washer -> 85
bolt -> 120
nut -> 340
washer = 85
bolt = 120
nut = 340

forEach nhận một BiConsumer và là cách viết ngắn nhất khi bạn chỉ cần đọc. entrySet là thứ cần dùng khi bạn cần một vòng lặp có break, continue hay return bên trong, những thứ mà lambda không làm được.

Vì sao entrySet là view đúng

Vòng lặp hấp dẫn nhất là duyệt keySet() rồi gọi get(key) bên trong. Cách đó chạy được, và nó hash lại từng key để lấy một value mà iterator đang đứng ngay trên đó. Đếm số lần gọi hashCode() bằng một class key có gắn counter, trên map 1.000 entry:

Entry vốn đã có sẵn ở đó — iterator đi dọc table và đưa cho bạn từng node, key và value đi cùng nhau. Vòng qua get là vứt bỏ điều đó và trả giá bằng một lần lookup thứ hai cho mỗi phần tử.

Chọn view theo thứ bạn cần: values() khi key không quan trọng (và lưu ý nó là Collection chứ không phải Set, vì value được phép trùng nhau), keySet() khi value không quan trọng, entrySet() khi cần cả hai. Bản thân entry cũng ghi được qua setValue, và thao tác đó cập nhật thẳng vào map mà không cần lookup lần nữa:

for (Map.Entry<String, Integer> e : stock.entrySet()) {
    if (e.getValue() < 100) {
        e.setValue(e.getValue() * 10);
    }
}
System.out.println(stock);

{washer=850, bolt=120, nut=340}

Xóa entry trong lúc đang duyệt

Thay đổi cấu trúc của map trong lúc đang for-each trên bất kỳ view nào của nó sẽ hỏng ngay lập tức:

for (String key : stock.keySet()) {
    if (stock.get(key) < 100) {
        stock.remove(key);
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1605)
	at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1628)
	at RemoveWhileIterating.main(RemoveWhileIterating.java:10)

Iterator ghi lại số lần map bị sửa tại thời điểm nó được tạo và kiểm tra lại con số đó ở mỗi lần next(). Chú ý tên của exception: ở đây chẳng có gì concurrent cả, chỉ một thread làm toàn bộ. Có hai cách làm đúng:

Iterator<Map.Entry<String, Integer>> it = stock.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getValue() < 100) {
        it.remove();
    }
}

stock.entrySet().removeIf(e -> e.getValue() < 100);

Cả hai đều đi qua iterator, và iterator tự cập nhật con số đếm mỗi lần nó xóa. removeIf là cách nên viết; iterator tường minh dành cho những trường hợp điều kiện cần nhiều hơn một biểu thức.

Vì các view là cửa sổ sống, xóa ở một view là xóa khỏi map. stock.keySet().remove("bolt") xóa nguyên cả entry. Ngược lại, thêm thì không thể — keySet().add("x") ném UnsupportedOperationException, vì sẽ chẳng có value nào để lưu.

HashMap không đảm bảo thứ tự

HashMap không hứa hẹn bất cứ điều gì về thứ tự duyệt, và thứ tự mà nó tạo ra không phải thứ tự thêm vào, cũng không phải thứ tự sắp xếp. Nó rơi ra từ việc mỗi key hash vào bucket nào và table đang lớn cỡ nào.

Nó cũng hoàn toàn xác định trên một JDK cụ thể với một tập key cụ thể — và chính điều đó mới nguy hiểm. Map đếm từ in ra cùng tám cặp theo cùng một thứ tự ở mọi lần chạy trên OpenJDK 21, nên một test khẳng định trên toString() hôm nay pass và sẽ vỡ vào ngày có thêm một key, hoặc map được dựng bằng merge thay vì put, hoặc JDK đổi phiên bản. Hai chuyện đầu đã xảy ra ngay trong bài này:

built with put/getOrDefault:  {the=3, over=1, quick=1, lazy=1, jumps=1, brown=1, dog=1, fox=2}
built with merge:             {over=1, the=3, quick=1, lazy=1, jumps=1, brown=1, dog=1, fox=2}

Hai map equals() với nhau nhưng in ra thứ tự khác nhau, vì merge móc một entry hoàn toàn mới vào bucket ở vị trí khác với put. Đó là một chi tiết implementation và nó được tự do thay đổi ở bất kỳ bản phát hành nào. Đừng bao giờ assert lên nó, đừng bao giờ dựa vào nó, và đừng để một danh sách hiển thị cho người dùng đi thẳng ra từ một HashMap thô.

Khi thứ tự có ý nghĩa, hãy nói điều đó ra ở type. LinkedHashMap giữ entry theo thứ tự thêm vào bằng cách duy trì một linked list song song với table. TreeMap giữ chúng sắp xếp theo key, dùng compareTo hoặc một Comparator thay cho hashing. Cả hai đều thay thẳng được cho Map, nên đổi sang chỉ tốn một từ ở dòng khai báo.

Những lỗi thường gặp với HashMap

Override equals mà không override hashCode. Lỗi đắt nhất trong cả bài: entry được lưu, được đếm, được in ra, và không bao giờ tìm lại được. Hãy sinh cả hai cùng lúc từ IDE, hoặc dùng record — nó tự viết cả hai từ các component.

Dùng một object mutable làm key rồi sửa nó. Entry trở thành không với tới được bằng mọi key, kể cả cái reference bạn vẫn đang cầm, và cũng không xóa được.

Coi get trả về null là "không tồn tại". Nó cũng có nghĩa "tồn tại, và được map tới null". Dùng containsKey khi sự khác biệt đó quan trọng, hoặc giữ null ở ngoài map.

Gọi containsKey rồi gọi get. Hai lần hash lookup cho việc mà một lần là đủ. getOrDefault, merge hay computeIfAbsent thường thay được cặp đó.

Gọi containsValue trong vòng lặp. Nó là một lần quét toàn bộ. Nếu bạn cần tra cứu theo value, bạn cần một map thứ hai.

Dựa vào thứ tự in ra. Nó đủ ổn định để viết một test pass được, và đủ bất ổn định để làm vỡ chính test đó về sau.

Dùng chung một HashMap giữa nhiều thread. Nó không thread-safe, và một lần resize xảy ra đồng thời có thể phá hỏng cấu trúc theo cách không throw ra gì cả. Hãy dùng ConcurrentHashMap khi có nhiều hơn một thread ghi.

Boxing trong vòng lặp nóng. Map<String, Integer> box mọi con số đếm. Thường thì chuyện đó không đáng kể, và nó đáng để biết khi map giữ hàng triệu value dạng số.

FAQ

Map và Collection trong Java khác nhau ở đâu?

Collection lưu từng phần tử đơn lẻ và extend Iterable, nên bạn lặp thẳng trên nó được. Map lưu cặp key/value, không extend Collection cũng không extend Iterable, và không đưa vào for-each được — for (String s : myMap) là lỗi compile. Thay vào đó nó cung cấp ba view đúng là collection: keySet(), values() và entrySet(). Tính duy nhất chỉ áp lên key; value được phép trùng nhau thoải mái.

Vì sao HashMap get trả về null dù tôi vừa put key đó vào?

Gần như luôn luôn là vì class key override equals mà không override hashCode. Hai object key bằng nhau nhưng khai hash code khác nhau, nên get tìm ở một bucket mà entry chưa từng được lưu vào. map.size() sẽ cho thấy entry thừa và System.out.println(map) sẽ in ra hai key giống hệt nhau. Nguyên nhân còn lại là một key mutable bị sửa sau khi đã lưu. Cả hai đều sửa được bằng cách giữ key immutable và tính hashCode từ đúng những field mà equals dùng.

put và putIfAbsent khác nhau chỗ nào?

put luôn lưu value và trả về value trước đó. putIfAbsent chỉ lưu khi key hiện chưa có value, và trả về thứ đã nằm sẵn ở đó — null nếu nó đã lưu value của bạn. Chú ý cách diễn đạt: một key được map thẳng tới null bị tính là chưa có, nên putIfAbsent sẽ ghi đè lên nó.

Khi nào nên dùng merge thay vì computeIfAbsent?

Dùng merge khi bạn đang kết hợp một value mới với value cũ — đếm, cộng dồn, nối chuỗi. Dùng computeIfAbsent khi bạn cần một container được tạo ở lần dùng đầu tiên rồi sửa nó, tức là idiom gom nhóm map.computeIfAbsent(k, x -> new ArrayList<>()).add(item). Một mẹo nhớ: merge thay thế value, còn computeIfAbsent trả về thứ mà bạn sẽ gọi method lên. merge còn xóa entry nếu function của nó trả về null.

Vì sao nên duyệt HashMap bằng entrySet thay vì keySet?

Vì keySet() chỉ đưa cho bạn key, nên bạn phải gọi get(key) để lấy value, và đó là một lần hash lookup thứ hai cho mỗi phần tử. Trên map 1.000 entry với một class key có gắn counter, vòng lặp keySet() cộng get() gọi hashCode() 1.000 lần còn vòng lặp entrySet() gọi 0 lần. Entry mà iterator đưa cho bạn vốn đã mang sẵn cả hai, và Entry.setValue còn cho bạn cập nhật thẳng vào map.

HashMap có cho phép key hoặc value là null không?

Cả hai đều được — một key null và bao nhiêu value null cũng được. TreeMap từ chối key null vì nó phải gọi compareTo lên key đó, còn các map immutable từ Map.of từ chối cả key lẫn value null bằng NullPointerException. Lưu null trong HashMap là hợp lệ nhưng nó làm get trở nên mơ hồ, nên thường đó là dấu hiệu thiết kế chưa ổn chứ không phải một tính năng.

HashMap có giữ thứ tự không?

Không. HashMap không ghi nhận bất kỳ đảm bảo nào về thứ tự, và thứ tự bạn quan sát được đến từ index của bucket và kích thước table hiện tại. Nó xác định với một tập key cụ thể trên một JDK cụ thể, và điều đó cám dỗ người ta dựa vào nó, nhưng thêm đúng một entry có thể kích hoạt resize và đảo lại toàn bộ. Hãy dùng LinkedHashMap cho thứ tự thêm vào hoặc TreeMap cho thứ tự theo key.

HashMap có thread-safe không?

Không. Nhiều thread cùng ghi có thể phá hỏng table bên trong mà không throw ra gì cả, và sau đó một lần đọc có thể nhìn thấy cấu trúc đã hỏng. Collections.synchronizedMap bọc mọi method trong một lock, cách đó đúng nhưng làm mọi truy cập nối đuôi nhau; ConcurrentHashMap mới là lựa chọn đúng cho một map có nhiều thread cùng ghi.

Kết luận

API của HashMap nhỏ, và phần lớn nó là một ý tưởng duy nhất được áp dụng nhất quán: put, get, containsKey và remove đều tốn một lần hash cộng một quãng đi ngắn, còn getOrDefault, putIfAbsent, merge và computeIfAbsent tồn tại để chu trình đọc - sửa - ghi lại chỉ còn một lần lookup thay vì hai. Hãy duyệt bằng entrySet vì iterator đã cầm sẵn thứ mà get phải đi lấy lại — 0 lần gọi hashCode() so với 1.000 lần trên một map 1.000 entry.

Phần thực sự cắn người là quy tắc nằm bên dưới. hashCode chọn bucket, equals tìm bên trong bucket đó, và hai thứ phải được tính từ cùng một tập field, nếu không một entry đã lưu sẽ trở thành không với tới được: size() nói 2, toString() in ra hai key giống hệt nhau, và get trả về null mãi mãi. Cùng một thất bại đó đến theo con đường khác khi một key bị sửa sau lúc đã lưu. Key nên immutable, và hashCode cùng equals nên luôn được viết — hoặc được sinh ra — cùng nhau. Một hashCode dở nhưng hợp lệ thì không phá hỏng dữ liệu; nó chỉ biến 10.000 lần gọi equals thành 50.014.999 lần.

Bài tiếp theo trong series: đọc và ghi file text — mở file để đọc và để ghi, chuyện gì xảy ra khi đường dẫn không tồn tại, và vì sao resource bắt buộc phải được đóng.