Tìm hiểu HashMap trong Java: Cấu trúc, Hoạt động và Lưu ý

HashMap là một trong những lớp triển khai phổ biến nhất của giao diện Map trong Java. Nó dựa trên bảng băm (hash table) để lưu trữ dữ liệu dưới dạng cặp key-value. Bài viết này sẽ đi sâu vào cấu trúc, cách thức hoạt động và những điểm cần lưu ý khi sử dụng HashMap.

1. Tổng quan về HashMap

HashMap cho phép lưu trữ null cả ở key và value. Nó không đảm bảo thứ tự của các phần tử theo thời gian. Hiệu suất cơ bản của các thao tác get và put là hằng số (O(1)) nếu hàm băm phân tán đều các phần tử vào các bucket.

HashMap có hai tham số ảnh hưởng đến hiệu suất: dung lượng ban đầu (initial capacity) và hệ số tải (load factor). Hệ số tải mặc định là 0.75, đây là sự cân bằng tốt giữa chi phí thời gian và không gian. Khi số lượng phần tử vượt quá tích của dung lượng hiện tại và hệ số tải, HashMap sẽ tự động tăng gấp đôi kích thước (thao tác gọi là rehash).

HashMap không đồng bộ (not synchronized). Nếu có nhiều luồng truy cập đồng thời và có ít nhất một luồng thực hiện thay đổi cấu trúc (thêm/xóa phần tử), cần phải đồng bộ hóa từ bên ngoài, ví dụ:

Map m = Collections.synchronizedMap(new HashMap(...));

2. Cấu trúc dữ liệu của HashMap

2.1. Nền tảng: Mảng + Danh sách liên kết + Cây đỏ-đen

HashMap lưu trữ dữ liệu trong một mảng các Node (gọi là bucket). Mỗi Node là một nút của danh sách liên kết. Khi xảy ra xung đột băm (hash collision), các phần tử có cùng chỉ mục sẽ được nối tiếp nhau thành một danh sách liên kết tại bucket đó.

Từ Java 8, HashMap được tối ưu hóa bằng cách chuyển danh sách liên kết thành cây đỏ-đen (red-black tree) khi đáp ứng hai điều kiện:

  • Số lượng phần tử trong một bucket vượt quá TREEIFY_THRESHOLD (mặc định là 8).
  • Tổng số phần tử trong HashMap ít nhất là MIN_TREEIFY_CAPACITY (mặc định là 64).

Ngược lại, khi số lượng phần tử giảm xuống dưới 6, cây sẽ được chuyển lại thành danh sách liên kết. Các ngưỡng này (8 và 6) được chọn để cân bằng giữa hiệu suất tìm kiếm (O(log n) của cây so với O(n) của danh sách) và tránh việc chuyển đổi qua lại thường xuyên.

3. Các constructor của HashMap

  • HashMap(int initialCapacity, float loadFactor): Tạo HashMap với dung lượng và hệ số tải chỉ định.
  • HashMap(int initialCapacity): Tạo HashMap với dung lượng chỉ định và hệ số tải mặc định (0.75).
  • HashMap(): Tạo HashMap với dung lượng mặc định (16) và hệ số tải mặc định (0.75).
  • HashMap(Map<? extends K, ? extends V> m): Tạo HashMap từ một Map có sẵn.

Lưu ý rằng dung lượng ban đầu luôn được làm tròn thành lũy thừa của 2 (thông qua phương thức tableSizeFor). Điều này rất quan trọng cho hiệu suất của các thao tác băm.

4. Thao tác Put

Quy trình thêm một cặp key-value vào HashMap gồm các bước sau:

  1. Tính mã băm (hash code): Sử dụng phương thức hash(key). Phương thức này lấy mã băm 32-bit từ key, sau đó XOR với 16 bit cao của chính nó để tăng tính ngẫu nhiên.
  2. Tính chỉ mục bucket: Sử dụng công thức (n - 1) & hash, trong đó n là độ dài mảng buckets. Vì n luôn là lũy thừa của 2, phép & này tương đương với phép chia lấy dư, nhưng nhanh hơn nhiều.
  3. Thêm Node:
    • Nếu bucket trống, tạo Node mới và đặt vào vị trí đó.
    • Nếu bucket đã có Node, kiểm tra xem key có trùng với Node đầu tiên không. Nếu trùng, ghi đè giá trị cũ.
    • Nếu không, kiểm tra xem Node đó có phải là nút của cây đỏ-đen không. Nếu đúng, thêm vào cây.
    • Nếu là danh sách liên kết, duyệt đến cuối danh sách. Nếu tìm thấy key trùng, ghi đè; nếu không, thêm Node mới vào cuối. Nếu độ dài danh sách vượt quá 8, chuyển danh sách thành cây.

Đoạn mã minh họa logic chính:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // ... kiểm tra và thêm vào bucket ...
    }
}

5. Thao tác Get

Tương tự, thao tác get(key) cũng tính toán mã băm và chỉ mục, sau đó tìm kiếm key trong bucket tương ứng:

final Node<K,V> getNode(int hash, Object key) {
    // ... kiểm tra bucket, sau đó tìm trong danh sách hoặc cây ...
}

Điều quan trọng là nếu bạn ghi đè phương thức equals() của một lớp, bạn cũng phải ghi đè phương thức hashCode(). Nếu không, hai đối tượng có cùng nội dung (theo equals()) nhưng mã băm khác nhau sẽ được HashMap coi là hai key riêng biệt, dẫn đến lỗi logic.

6. Cơ chế mở rộng (Resize) và tối ưu trong Java 8

Khi số lượng phần tử vượt quá ngưỡng (threshold = capacity * loadFactor), HashMap sẽ tăng gấp đôi dung lượng (gọi là resize). Quá trình này liên quan đến việc tạo một mảng mới có kích thước gấp đôi và di chuyển tất cả các phần tử từ mảng cũ sang mảng mới.

Tối ưu trong Java 8: Thay vì phải tính toán lại chỉ mục cho từng phần tử (rehash), Java 8 sử dụng một kỹ thuật thông minh dựa trên tính chất của lũy thừa 2. Khi nhân đôi kích thước, bit cao nhất của (n-1) tăng thêm 1. Do đó, chỉ mục mới của một phần tử có thể được tính bằng cách kiểm tra bit thứ log2(oldCap) của mã băm:

  • Nếu bit đó là 0, phần tử giữ nguyên chỉ mục cũ.
  • Nếu bit đó là 1, phần tử được chuyển đến chỉ mục cũ + dung lượng cũ.

Điều này giúp phân tán lại các phần tử một cách hiệu quả mà không cần tính toán lại mã băm.

7. Vấn đề an toàn luồng (Thread Safety)

HashMap không an toàn trong môi trường đa luồng. Các vấn đề thường gặp:

  • Java 7: Trong quá trình resize, phương thức transfer sử dụng phép chèn đầu (head insertion), có thể gây ra vòng lặp vô hạn (infinite loop) khi nhiều luồng cùng thao tác, do danh sách liên kết bị đảo ngược và tạo thành chu trình.
  • Java 8: Vấn đề vòng lặp vô hạn đã được khắc phục nhờ sử dụng phép chèn cuối (tail insertion). Tuy nhiên, vẫn có thể xảy ra ghi đè dữ liệu (data overwrite) do các luồng không đồng bộ khi thao tác put.

Giải pháp: Sử dụng ConcurrentHashMap cho các tình huống cần đồng bộ.

Thẻ: HashMap Java Collection Framework Java 8 hash table Red-Black Tree

Đăng vào ngày 7 tháng 7 lúc 09:11

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn