HashMap hoạt động như thế nào trong Java?

Java HashMap là một cấu trúc dữ liệu thuộc thư viện Java Collection Framework, cho phép lưu trữ và truy xuất các cặp giá trị theo kiểu “key-value” (khóa và giá trị). Nó sử dụng cơ chế băm (hashing) để lưu trữ và truy cập các phần tử một cách nhanh chóng, với thời gian trung bình cho các thao tác như thêm, xóa và truy cập là O(1).

Nguyên lý hoạt động của HashMap

HashMap lưu trữ dữ liệu trong một mảng các bucket. Mỗi bucket trong HashMap lưu trữ một danh sách các mục (entry) được ánh xạ từ khóa (key) sang giá trị (value). Khóa được sử dụng để tính toán một giá trị băm (hash code), từ đó xác định vị trí bucket chứa mục tương ứng. Khi một mục được thêm vào hoặc truy xuất từ HashMap, Java sẽ tính toán hash code của khóa để xác định vị trí trong mảng bucket.

Các bước hoạt động cơ bản của HashMap

1. Tạo giá trị băm (hash code): Khi bạn thêm một cặp key-value vào HashMap, khóa (key) sẽ được băm thành một giá trị số nguyên (hash code) bằng cách sử dụng phương thức hashCode() của đối tượng. Sau đó, HashMap sử dụng giá trị băm này để xác định vị trí bucket trong mảng để lưu trữ cặp key-value.
2. Chỉ mục bucket: Giá trị băm sau khi tính toán sẽ được dùng để xác định chỉ mục của mảng bucket. Ví dụ, giả sử mảng có kích thước là n, chỉ mục sẽ được tính bằng cách sử dụng phép toán hashCode % n để đảm bảo rằng chỉ mục luôn nằm trong phạm vi của mảng.
3. Xử lý xung đột (collision): Khi hai hoặc nhiều khóa khác nhau có cùng giá trị băm và ánh xạ tới cùng một bucket, xung đột xảy ra. HashMap xử lý các xung đột này bằng cách lưu trữ các phần tử có cùng chỉ mục trong một danh sách liên kết (linked list). Kể từ Java 8, khi số lượng phần tử trong danh sách liên kết vượt quá ngưỡng nhất định, danh sách này được chuyển đổi thành cây nhị phân (binary tree) để cải thiện hiệu suất tìm kiếm.
4. Truy xuất phần tử: Để truy xuất giá trị từ HashMap, Java sử dụng khóa để tính giá trị băm và tìm bucket tương ứng. Sau đó, nó duyệt qua danh sách liên kết (hoặc cây nhị phân nếu có) trong bucket đó để tìm kiếm phần tử có khóa phù hợp và trả về giá trị.
5. Tăng kích thước HashMap (rehashing): Khi số lượng phần tử trong HashMap vượt quá một ngưỡng nhất định (thường gọi là load factor), kích thước của mảng bucket sẽ được tăng lên để giảm thiểu các xung đột. Quá trình này được gọi là rehashing, và sau khi mảng bucket được mở rộng, tất cả các phần tử sẽ được ánh xạ lại (rehash) để xác định vị trí mới trong mảng.

Ví dụ về hoạt động của HashMap

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // Tạo một HashMap
        HashMap<String, Integer> map = new HashMap<>();

        // Thêm các cặp key-value vào HashMap
        map.put("John", 25);
        map.put("Alice", 30);
        map.put("Bob", 35);

        // Truy xuất giá trị dựa trên key
        System.out.println("Tuổi của John: " + map.get("John"));  // Output: 25

        // Kiểm tra sự tồn tại của một key
        if (map.containsKey("Alice")) {
            System.out.println("Alice có trong HashMap");
        }

        // Xóa một phần tử khỏi HashMap
        map.remove("Bob");
        System.out.println("HashMap sau khi xóa Bob: " + map);
    }
}

Trong ví dụ này:

• map.put("John", 25) thêm cặp khóa “John” và giá trị 25 vào HashMap. Java sẽ tính toán giá trị băm cho khóa “John” để xác định vị trí lưu trữ trong mảng bucket.
• map.get("John") truy xuất giá trị tương ứng với khóa “John”, tức là 25.
• map.remove("Bob") sẽ xóa mục có khóa là “Bob” khỏi HashMap.

Các thuộc tính quan trọng của HashMap

1. Hashing: Quá trình băm là cơ sở của HashMap. Phương thức hashCode() của các khóa được sử dụng để tính toán vị trí trong mảng bucket. Một hàm băm tốt giúp phân phối khóa đều trên các bucket, giảm khả năng xung đột và cải thiện hiệu suất.
2. Load Factor: Load factor là tỷ lệ giữa số lượng phần tử và kích thước của mảng bucket. Mặc định, load factor là 0.75, nghĩa là khi HashMap đạt 75% công suất, nó sẽ tự động tăng kích thước và thực hiện rehashing. Điều này giúp giảm xung đột, nhưng cũng tốn tài nguyên tính toán.
3. Xử lý xung đột: HashMap xử lý xung đột bằng cách sử dụng danh sách liên kết để lưu trữ các phần tử có cùng giá trị băm. Kể từ Java 8, nếu danh sách liên kết trở nên quá dài, nó sẽ được chuyển thành cây nhị phân để tăng tốc độ tìm kiếm.
4. Rehashing: Khi HashMap tăng kích thước, quá trình rehashing sẽ xảy ra, tức là tất cả các mục hiện có trong HashMap sẽ được ánh xạ lại (do kích thước của mảng bucket thay đổi). Quá trình này có thể tốn tài nguyên và có thể làm giảm hiệu suất nếu xảy ra thường xuyên.

Tóm lại

HashMap trong Java là một cấu trúc dữ liệu mạnh mẽ, cung cấp hiệu suất nhanh chóng cho các thao tác lưu trữ và truy xuất dữ liệu bằng cách sử dụng cơ chế băm. Tuy nhiên, điều quan trọng là phải hiểu các khái niệm như hashing, load factor, và cách xử lý xung đột để sử dụng HashMap một cách hiệu quả.