Hash(mã băm) là một khái niệm cơ bản trong khoa học máy tính. Trong Java các thuật toán hash được sử dụng trong các collection dạng key-value như HashMap, HashSet. Trong bài viết này chúng ta sẽ cùng nhau tìm hiểu cách hashCode() method hoạt động cũng như các ứng dụng của nó.
hashCode() trong HashMap
HashMap là một cấu trúc dữ liệu dạng key-value cho phép truy xuất nhanh các phần tử theo một key xác định. Mỗi khi HashMap lưu trữ dữ liệu nó sẽ tiến hành tính giá trị hash-value bởi key được chỉ định thông qua hashCode() method và sử dụng giá trị này trong nội bộ HashMap giúp các hoạt động truy xuất hiệu quả hơn.
Cách hashCode() method hoạt động
hashCode() trả về một giá trị kiểu integer được sinh ra bởi 1 thuật toán hash. Nếu equals() method trả về true khi so sánh 2 object thì chúng cũng phải có cùng giá trị hashCode().
Note: 2 object khác nhau có thể trả về cùng giá trị hashCode().
hashCode() có những quy chuẩn cần tuân thủ:
- Các lần gọi hashCode() method phải trả về giá trị giống nhau trên cùng một object trong quá trình thực thi chương trình. Giá trị này không nhất thiết phải giống nhau giữa các lần chạy chương trình.
- Nếu 2 object bằng nhau khi so sánh thông qua equals() method thì chúng cũng phải có giá trị hashCode() bằng nhau.
- Không bắt buộc 2 object không bằng nhau phải có giá trị hashCode() khác nhau. Tuy nhiên nếu chúng có giá trị hashCode() khác nhau sẽ tăng hiệu xuất cho các bảng băm.
Hash Collisions
Đối với những thuật toán hash hiệu quả nhất thì 2 hoặc nhiều object khác nhau đều có thể có cùng giá trị mã băm(hash) ngay cả khi chúng không bằng nhau. Vì vậy, mã băm của chúng sẽ cùng trỏ về 1 nhóm mặc dù chúng có key khác nhau đây gọi là Hash Collisions trong Java.
Khi 2 hoặc nhiều object có mã băm trỏ đến cùng một nhóm, chúng sẽ được lưu trữ trong một danh sách liên kết. Trong trường hợp này, bảng băm(hash table) là một mảng các phần tử mà mỗi phần tử là một danh sách liên kết. Những object có cùng mã băm sẽ được nối vào danh sách liên kết tại vị trí tương ứng trong mảng.
Trong trường hợp xấu nhất, các object đều có cùng mã băm, bảng băm lúc này chỉ là mảng chứa 1 phần tử là một danh sách liên kết lưu trữ tất cả các object. Việc truy xuất các object sẽ tốn khoảng thời gian tuyến tính thay vì O(1) như thông thường.
Oh la!!! thật là may mắn, kể từ Java 8, nếu một danh sách liên kết trong mảng vượt quá kích thước quy định nó sẽ được thay thế bằng tree map, cho phép giảm kết quả tìm kiếm xuống O(logn) thay vì O(n) khi tìm kiếm tuyến tính.
Tóm lược
Như vậy hashCode() và equals() method có mối tương quan đặc biệt mà chúng ta cần phải chú ý khi muốn override từ Object class. Các thuật toán hash càng hiệu quả sẽ cho kết quả thực thi của các hash table hiệu quả hơn (HashMap, HashSet etc).
Nguồn tham khảo
https://www.baeldung.com/java-hashcode