Giới thiệu về Java HashMap
Java HashMap là một trong những cấu trúc dữ liệu phổ biến nhất trong ngôn ngữ lập trình Java. Nó cho phép lưu trữ cặp khóa-giá trị, giúp dễ dàng quản lý và truy xuất dữ liệu.
1. Cấu trúc bên trong của HashMap
HashMap được triển khai thông qua một mảng các bucket. Mỗi bucket là một danh sách liên kết (linked list) chứa các cặp key-value (Entry). Khi một cặp key-value được thêm vào HashMap, mã băm (hash code) của key sẽ được tính toán để xác định vị trí thích hợp trong mảng. Nếu có nhiều cặp có cùng mã băm, chúng sẽ được lưu trữ trong cùng một bucket dưới dạng danh sách liên kết.
HashMap sử dụng một mảng Entry<K, V> được gọi là table[] để lưu trữ các cặp khóa-giá trị. Khi bạn thêm một cặp khóa-giá trị vào HashMap, nó không chèn ngay lập tức mà sẽ tính toán mã băm của khóa để xác định chỉ mục.
2. Khái niệm về Hashing
Toàn bộ cấu trúc dữ liệu của HashMap dựa trên nguyên tắc Hashing. Hashing là một thuật toán cho phép chuyển đổi một biến hoặc đối tượng thành một giá trị số nguyên duy nhất, gọi là mã băm. Một hàm băm tốt cần phải trả về cùng một giá trị cho cùng một đối tượng và giảm thiểu khả năng xung đột giữa các giá trị khác nhau.
3. Mối quan hệ giữa phương thức hashCode() và equals()
HashMap sử dụng hai phương thức hashCode() và equals() để thêm và truy xuất phần tử. Phương thức hashCode() giúp xác định vị trí của phần tử trong mảng, trong khi equals() được sử dụng để kiểm tra xem hai đối tượng có giống nhau hay không. Việc cài đặt chính xác hai phương thức này là rất quan trọng để đảm bảo HashMap hoạt động hiệu quả và chính xác.
4. Các thành phần chính của HashMap
- Mảng bucket (table): Lưu trữ các Node, mỗi Node đại diện cho một bucket, chứa tham chiếu đến Entry đầu tiên.
- Entry: Lớp bên trong của HashMap biểu diễn cho cặp key-value. Mỗi Entry chứa khóa, giá trị, mã băm và tham chiếu đến Entry tiếp theo.
- Load factor: Hệ số biểu thị mức độ đầy của HashMap. Nếu số lượng Entry vượt quá load factor nhân với kích thước của mảng, HashMap sẽ tự động tăng kích thước mảng. Giá trị mặc định là 0.75.
- Threshold: Ngưỡng kích hoạt quá trình rehashing.
5. Các hoạt động chính của HashMap
Thêm phần tử (put)
- Tính toán mã băm của key.
- Xác định vị trí bucket dựa trên mã băm.
- Nếu bucket trống, tạo một Entry mới và thêm vào.
- Nếu bucket không trống, duyệt qua danh sách liên kết để kiểm tra key đã tồn tại chưa. Nếu đã tồn tại, cập nhật giá trị. Nếu chưa, thêm vào danh sách.
- Nếu số lượng Entry vượt ngưỡng, thực hiện rehashing.
Lấy giá trị (get)
- Tương tự như thêm, nhưng trả về giá trị đại diện cho key.
Xóa phần tử (remove)
- Tìm vị trí của key và xóa phương thức tương ứng.
Rehashing
- Khi số lượng phần tử vượt ngưỡng, tạo mảng mới gấp đôi kích thước cũ và phân phối lại các Entry.
6. Tối ưu hóa HashMap
Từ JDK 8, HashMap đã được cải tiến với việc sử dụng cây đỏ-đen để cải thiện hiệu suất trong trường hợp có nhiều va chạm hash. Khi số lượng Entry trong một bucket vượt quá ngưỡng 8, danh sách liên kết sẽ được chuyển đổi thành cây đỏ-đen.
7. An toàn trong môi trường đa luồng
HashMap không phải là thread-safe. Nếu bạn cần sử dụng trong môi trường đa luồng, hãy sử dụng ConcurrentHashMap. ConcurrentHashMap đảm bảo rằng nhiều luồng có thể truy cập và cập nhật mà không gặp phải tình trạng xung đột.
Kết luận
HashMap là một công cụ hữu ích và mạnh mẽ trong lập trình Java, cho phép quản lý dữ liệu hiệu quả với tốc độ nhanh. Nắm vững kiến thức về HashMap sẽ giúp lập trình viên tối ưu hóa ứng dụng của mình một cách tốt nhất.
