Mở HashMap ra xem: bảng lớn lên lúc nào, và khi nào ngăn thành cây

HashMap là lớp bạn dùng nhiều nhất sau String và ArrayList. Bài này mở nó ra xem bên trong — bằng phản chiếu, trên JDK 21 thật, không dựa vào bài viết nào khác.

Trước hết, một trở ngại nho nhỏ nhưng đáng nhắc:

InaccessibleObjectException: Unable to make field java.util.HashMap.table accessible:
module java.base does not "opens java.util" to unnamed module

Hệ thống module chặn phản chiếu vào ruột JDK — đúng thứ đã nói ở bài về classpath và module-path. Muốn xem thì phải xin phép tường minh:

java --add-opens java.base/java.util=ALL-UNNAMED SoiHashMap.java

Bảng lớn lên khi nào

HashMap giữ một mảng gọi là bảng, mỗi ô là một ngăn. Theo dõi kích thước bảng khi thêm dần phần tử:

  mới tạo         bảng chưa cấp phát, size=0
  sau khi put 1   bảng=16 ngăn,  1 ngăn có dữ liệu, size=1
  sau khi put 12  bảng=16 ngăn, 12 ngăn có dữ liệu, size=12
  sau khi put 13  bảng=32 ngăn, 13 ngăn có dữ liệu, size=13
  sau khi put 24  bảng=32 ngăn, 24 ngăn có dữ liệu, size=24
  sau khi put 25  bảng=64 ngăn, 25 ngăn có dữ liệu, size=25
  sau khi put 48  bảng=64 ngăn, 48 ngăn có dữ liệu, size=48
  sau khi put 49  bảng=128 ngăn, size=49

Ba điều hiện ra ngay:

Bảng chưa được cấp phát khi mới tạo. new HashMap<>() không chiếm bộ nhớ cho bảng; mảng 16 ô chỉ ra đời ở lần put đầu tiên. Nên tạo sẵn hàng nghìn map rỗng không tốn kém như bạn tưởng.

Mỗi lần đầy thì bảng gấp đôi. 16 → 32 → 64 → 128.

Ngưỡng là 0,75. Bảng 16 ô nở ra ở phần tử thứ 13 — vì 16 × 0,75 = 12. Bảng 32 nở ở phần tử 25, bảng 64 nở ở phần tử 49. Con số 0,75 này gọi là hệ số tải, và nó là điểm cân bằng giữa lãng phí bộ nhớ (hệ số thấp) và va chạm nhiều (hệ số cao).

Hệ quả thực dụng: khai sẵn dung lượng nếu biết trước số phần tử. Nạp 1000 phần tử vào một map mặc định sẽ trải qua 7 lần cấp phát lại và rehash toàn bộ. Muốn chứa n phần tử mà không phải nở, khai new HashMap<>((int)(n / 0.75) + 1).

Một lần rehash

Khi bảng gấp đôi, mỗi phần tử phải được xếp lại ngăn — vì chỉ số ngăn tính từ mã băm chia lấy dư cho kích thước bảng.

Từ Java 8, việc này được làm rất khéo. Vì kích thước luôn là luỹ thừa của 2, phần tử trong một ngăn chỉ có thể đi về một trong hai chỗ: ở lại chỗ cũ, hoặc sang chỗ cũ cộng kích thước bảng cũ. Và để biết đi đâu, chỉ cần xem đúng một bit của mã băm — không phải tính lại băm, không phải chia.

Nhờ đó rehash chỉ là một lượt duyệt tách đôi từng ngăn, chứ không phải chèn lại từ đầu.

Va chạm: khi mọi khoá cùng một ngăn

Giờ tôi cố tình phá: một record mà hashCode() luôn trả về 42, nên mọi khoá rơi vào cùng một ngăn.

record KhoaXau(int id) {
    @Override public int hashCode() { return 42; }
}

  sau khi put 7   bảng=16 ngăn, 1 ngăn có dữ liệu, ngăn dài nhất=7 (Node)
  sau khi put 8   bảng=16 ngăn, 1 ngăn có dữ liệu, ngăn dài nhất=8 (Node)
  sau khi put 9   bảng=32 ngăn, 1 ngăn có dữ liệu, ngăn dài nhất=9 (Node)
  sau khi put 12  bảng=64 ngăn, 1 ngăn có dữ liệu, kiểu nút = TreeNode

Đọc bốn dòng này kỹ, vì chúng cho thấy một luật mà rất nhiều bài viết nói sai.

HashMap xử lý va chạm bằng cách nối các phần tử thành chuỗi trong cùng một ngăn. Tra cứu trong ngăn phải đi hết chuỗi, so equals từng cái — nên chuỗi dài là O(n).

Để chống chuyện đó, từ Java 8 HashMap chuyển ngăn quá dài sang cây đỏ đen, đưa tra cứu về O(log n). Nhưng điều kiện không chỉ là "chuỗi dài 8".

Luật hai điều kiện

Tôi tách riêng ra để kiểm cho chắc — một map dùng bảng mặc định, một map khai sẵn 128 ngăn:

--- bảng nhỏ (mặc định 16) ---
   7 phần tử -> 16 ngăn, kiểu nút = Node
   8 phần tử -> 16 ngăn, kiểu nút = Node
   9 phần tử -> 32 ngăn, kiểu nút = Node      <- MỞ RỘNG, không thành cây

--- bảng đủ lớn (khai sẵn 128) ---
   7 phần tử -> 128 ngăn, kiểu nút = Node
   8 phần tử -> 128 ngăn, kiểu nút = Node
   9 phần tử -> 128 ngăn, kiểu nút = TreeNode  <- THÀNH CÂY

Cùng dữ liệu, cùng số phần tử, hai kết quả khác nhau.

Luật thật là: ngăn chuyển sang cây khi chuỗi đạt 8 phần tử VÀ bảng có ít nhất 64 ngăn. Bảng chưa đủ 64 thì HashMap mở rộng bảng trước — vì với bảng nhỏ, chuỗi dài thường là do bảng chật chứ không phải do hàm băm tồi, và mở rộng rẻ hơn dựng cây.

Đây là chi tiết mà tôi thấy nhiều tài liệu bỏ qua, và nó giải thích vì sao thử nghiệm "tạo 8 khoá trùng băm để xem cây" thường không ra kết quả như mong đợi.

Cây cũng chuyển ngược về chuỗi khi ngăn co lại còn 6 phần tử. Hai ngưỡng khác nhau (8 lên, 6 xuống) để tránh chuyển qua chuyển lại liên tục quanh một điểm.

Và dù va chạm tối đa, tra cứu vẫn cho kết quả đúng:

  get(KhoaXau(5)) = v
  size = 12

Chậm, nhưng đúng — vì equals mới là thứ quyết định, còn hashCode chỉ chọn ngăn. Đúng như bài về equals đã nói.

Băm lại mã băm

Một chi tiết nhỏ mà tinh tế. HashMap không dùng thẳng hashCode() của bạn; nó trộn thêm một bước:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Vì chỉ số ngăn được lấy bằng hash & (n - 1) — tức là chỉ dùng các bit thấp. Nếu hàm băm của bạn chỉ khác nhau ở bit cao, mọi khoá sẽ rơi vào cùng ngăn. Phép ^ (h >>> 16) trộn bit cao xuống bit thấp, giảm hẳn nguy cơ đó.

Nên một hashCode tồi vẫn có cơ hội được cứu. Nhưng đừng dựa vào: một hashCode luôn trả cùng một giá trị — như ví dụ trên — thì không cứu được.

Ba điều rút ra cho mã hằng ngày

Khoá phải bất biến và có hashCode tử tế. Đây là bài học của bài equals, và giờ bạn thấy tận mắt lý do: mã băm quyết định ngăn, ngăn quyết định tìm thấy hay không.

Khai sẵn dung lượng khi biết trước số phần tử. Bảy lần rehash cho 1000 phần tử là bảy lần duyệt lại toàn bộ.

Đừng lo về va chạm nếu dùng khoá thường. String, Integer, record đều có hashCode phân bố tốt. Cây đỏ đen là lưới an toàn cho trường hợp xấu, không phải thứ bạn gặp hằng ngày.

Thử ba mươi giây

Chạy đoạn soi bảng ở đầu bài với HashMap<String,String> và khoá là chuỗi ngẫu nhiên. Xem phân bố ngăn — bạn sẽ thấy hầu hết ngăn có 1–2 phần tử, hiếm khi tới 3.

Rồi đổi khoá thành một lớp có hashCode() trả về hằng số và chạy lại. Cùng số phần tử, HashMap biến thành một danh sách liên kết, và mọi lần get phải quét cả danh sách.

Đó là toàn bộ giá trị của một hashCode tốt, nhìn thấy được.

Ngày mai: LinkedHashMap — thứ tự chèn hay thứ tự truy cập, và viết một bộ nhớ đệm LRU trong hai mươi dòng.