Java: Tại sao khi ghi đè phương thức equals cần phải đồng thời ghi đè phương thức hashCode? - nohu52 đăng nhập

| Feb 12, 2025 min read
Java: Tại sao khi ghi đè phương thức equals cần phải đồng thời ghi đè phương thức hashCode? - nohu52 đăng nhập

Ngày 12 tháng 3 năm 2024
Lĩnh vực: Công nghệ thông tin

Bài viết này được khơi nguồn từ một câu hỏi phỏng vấn phổ biến trong Java: “Tại sao khi ghi đè phương thức equals chúng ta cần phải đồng thời ghi đè phương thức hashCode?” Bài viết sẽ lần lượt giải đáp ba câu hỏi chính về phương thức hashCode: Vai trò của hashCode, mối liên hệ giữa hashCode và equals, lý do tại sao cần ghi đè cả hai phương thức cùng lúc, cũng như cách ghi đè hashCode.

Chúng ta đều biết rằng lớp Object là cha của tất cả các lớp trong Java, và hashCode là một phương 365 com ca cuoc thức được định nghĩa sẵn trong lớp Object. Do đó, mọi lớp đều tự động thừa hưởng phương thức hashCode.

Dưới đây là định nghĩa của phương thức hashCode trong lớp Object:

package java.lang;

public class Object {
    /**
     * Trả về giá trị băm cho đối tượng. Phương thức này hỗ trợ các bảng băm,
     * chẳng hạn như những cái được cung cấp bởi `java.util.HashMap`.
     *
     * Điều khoản chung của `hashCode` là:
     *
     * a) Mỗi khi nó được gọi trên cùng một đối tượng nhiều lần trong quá trình
     * thực thi ứng dụng Java, phương thức `hashCode` phải trả về cùng một số nguyên,
     * miễn là không có thông tin nào được sử dụng trong so sánh `equals` bị thay đổi.
     * Số nguyên này không bắt buộc phải nhất quán giữa các lần chạy khác nhau của ứng dụng.
     *
     * b) Nếu hai đối tượng bằng nhau theo phương thức `equals(Object)`,
     * thì việc gọi phương thức `hashCode` trên mỗi trong hai đối tượng đó phải
     * trả về cùng một kết quả số nguyên.
     *
     * c) Không bắt buộc nếu hai đối tượng khác nhau theo phương thức `equals(Object)`,
     * thì việc gọi phương thức `hashCode` trên mỗi trong hai đối tượng đó phải
     * tạo ra các kết quả số nguyên khác nhau. Tuy nhiên, lập trình viên nên lưu ý rằng
     * việc tạo ra các kết quả số nguyên khác nhau cho các đối tượng khác nhau có thể cải thiện hiệu suất của bảng băm.
     */
    @IntrinsicCandidate
    public native int hashCode();

    /**
     * Chỉ ra liệu một đối tượng khác có "bằng" đối tượng này hay không.
     *
     * Lưu ý API:
     * Thông thường, cần phải ghi đè phương thức `hashCode` mỗi khi phương thức này bị ghi đè,
     * để duy trì điều khoản chung cho phương thức `hashCode`, mà yêu cầu các đối tượng bằng nhau phải có mã băm giống nhau.
     */
    public boolean equals(Object obj) {
        return (this == obj);
    }
}

Phương thức hashCode được sử dụng để sinh ra một số nguyên, là phương thức gốc (native) và được đánh dấu bằng chú thích @IntrinsicCandidate, tức là việc triển khai hoàn toàn phụ thuộc vào JVM. Các phiên bản JVM khác nhau có thể có cách triển khai khác nhau, chẳng hạn như sử dụng các số ngẫu nhiên giả.

Vậy tại sao lớp Object lại định nghĩa phương thức hashCode? Ngoài ra, chúng ta còn nhận thấy rằng phương thức equals cũng được định nghĩa trong lớp Object. Vậy mối liên hệ giữa hai phương thức này là gì?

1. Vai trò của phương thức hashCode và mối quan hệ với equals

Trong Java, phương thức hashCode chủ yếu được thiết kế để phối hợp với cấu trúc dữ liệu bảng băm (hash table). Bảng băm là một kiểu dữ liệu dùng để lưu trữ cặp giá trị khóa-giá trị (key-value). Nó truy cập dữ liệu thông qua việc ánh xạ khóa đến một vị trí cụ thể trong bảng, giúp tăng tốc độ tìm kiếm. Hàm ánh xạ này được gọi là hàm băm (hash function). Một số ví dụ về bảng băm trong Java bao gồm HashSet, Hashtable và HashMap.

Giả sử chúng ta muốn tạo một Set mà không cho phép chứa các phần tử trùng lặp. Nếu không sử dụng bảng băm, làm thế nào để thực hiện điều này?

Một cách đơn giản là: Khi thêm một đối tượng vào Set, chúng ta sẽ gọi phương thức equals để so sánh từng phần tử hiện có trong Set. Chỉ khi đối tượng không bằng bất kỳ phần tử nào trong Set thì mới cho phép thêm. Tuy nhiên, cách tiếp cận này rất kém hiệu quả khi Set chứa một lượng lớn phần tử vì phương thức equals thường đòi hỏi sự so sánh chi tiết giữa các trường quan trọng của đối tượng.

Nếu sử dụng bảng băm thì sao? Chúng ta biết rằng HashSet trong Java thực chất dựa trên HashMap. Vậy HashMap hoạt động như thế nào để tối ưu hóa quá trình thêm phần tử?

Cấu trúc lưu trữ của HashMap là bảng băm. Khi thêm một cặp khóa-giá trị, các bước sau được thực hiện:

  • Bước 1: Gọi phương thức hashCode của khóa để lấy giá trị băm.
  • Bước 2: So sánh giá trị băm với các giá trị băm đã tồn tại. Nếu không trùng khớp, đối tượng sẽ được thêm trực tiếp vào bảng băm.
  • Bước 3: Nếu có giá trị băm trùng khớp, phương thức equals sẽ được gọi để kiểm tra tính bằng nhau. Nếu không bằng nhau, đối tượng sẽ được thêm vào danh sách liên kết (linked list) để xử lý xung đột băm. Nếu bằng nhau, đối tượng sẽ không được thêm.

Như vậy, nhờ vào việc sử dụng bảng băm, việc kiểm tra trùng lặp sẽ nhanh hơn đáng kể. Nếu thuật toán băm đủ tốt, hầu hết các trường hợp sẽ không cần gọi phương thức equals. Hơn nữa, nếu chọn được một hàm băm phù hợp (lý tưởng là phân bố đều các giá trị băm trên toàn bộ khoảng giá trị của kiểu int), hiệu suất tìm kiếm của bảng băm sẽ cực kỳ cao, đạt mức độ phức tạp thời gian O(1) trong trường hợp không có xung đột băm. Ngược lại, trong trường hợp xấu nhất (tất cả các giá trị băm đều trùng nhau), cấu trúc dữ liệu trở thành một danh sách liên kết, dẫn đến độ phức tạp thời gian là O(N).

Tóm lại, hashCode thường được sử dụng cùng với equals. Hai phương thức này phải tuân thủ một số ràng buộc nhất định để đảm bảo tính đúng đắn khi so sánh hai đối tượng. Chú thích của phương thức hashCode đã liệt kê ba điều khoản chung:

  • Cùng một đối tượng gọi phương thức hashCode nhiều lần phải trả về cùng một giá trị số nguyên.
  • Nếu hai đối tượng a và b thỏa mãn a.equals(b), thì a.hashCode() và b.hashCode() phải bằng nhau.
  • Nếu hai đối tượng a và b không thỏa mãn a.equals(b), thì a.hashCode() không bắt buộc phải khác b.hashCode(). Tuy nhiên, việc tạo ra các giá trị băm khác nhau cho các đối tượng khác nhau có thể cải thiện hiệu suất của bảng băm.

Sau khi hiểu rõ vai trò của hashCode và mối liên hệ giữa hashCode và equals, chúng ta sẽ tìm hiểu lý do tại sao khi ghi đè equals cần phải đồng thời ghi đè hashCode.

2. Tại sao khi ghi đè equals cần phải đồng thời ghi đè hashCode?

Chú thích của phương thức hashCode đã liệt kê ba điều khoản chung, và chú thích của phương thức equals cũng nhắc đến một điều quan trọng: “Khi ghi đè phương thức equals, cần phải ghi đè phương thức hashCode để không phá vỡ các điều khoản chung của hashCode. Cụ thể, nếu hai đối tượng bằng nhau (kết quả gọi equals là true), thì hai đối tượng đó phải có cùng giá trị băm.”

Do đó, nếu chỉ ghi đè equals mà không ghi đè hashCode, có thể xảy ra tình huống hai đối tượng gọi equals trả về true nhưng giá trị băm lại khác nhau. Điều này có thể dẫn đến hành vi bất thường, chẳng hạn như trong HashMap.

Cuối cùng, chúng ta sẽ thảo luận về cách ghi đè phương thức hashCode.

3. Cách ghi đè phương thức hashCode

Dưới đây là định nghĩa của lớp User:

// src/test/java/com/example/demo/model/User.java
package com.example.demo.model;

public class User {
    private final String name;
    private final Integer age;
    private final Gender gender;

    public User(String name, Integer age, Gender gender) {
        this.name = name;
        this.age = age;
        this.gender = gender;
    }

    public enum Gender { MALE, FEMALE }
}

Lớp này có ba thuộc tính: name, age và gender. Nếu không ghi đè hashCode và equals, các phương thức mặc định của lớp Object sẽ được sử dụng. Điều này có nghĩa là hashCode sẽ là một số ngẫu nhiên do JVM tạo ra, và equals sẽ so sánh địa chỉ tham chiếu của hai đối tượng.

Khi thử nghiệm với hai đối tượng User logic “bằng nhau” (user1 và user2), chúng ta nhận thấy rằng user1.equals(user2) và user1.hashCode() == user2.hashCode() đều trả về false. Khi thêm hai đối tượng này vào HashMap, kích thước của HashMap là 2, chứng tỏ cả nhà cái 888b hai đối tượng đều được thêm vào. Đây là hành vi bất thường xảy ra khi không ghi đè hashCode và equals.

// Không ghi đè hashCode và equals của lớp User
User user1 = new User("Larry", 18, User.Gender.MALE);
User user2 = new User("Larry", 18, User.Gender.MALE);

System.out.println(user1.equals(user2)); // false
System.out.println(user1.hashCode() == user2.hashCode()); // false

Map<User, Boolean> map = new HashMap<>();
map.put(user1, true);
map.put(user2, true);

System.out.println(map.size()); // 2

Tiếp theo, chúng ta sẽ ghi đè hashCode và equals trong lớp User:

// src/test/java/com/example/demo/model/User.java
package com.example.demo.model;

import java.util.Objects;

public class User {
    // ...

    @Override
    public int hashCode() {
        int result = name.hashCode();
        result = 31 * result + Integer.hashCode(age);
        result = 31 * result + gender.toString().hashCode();
        return result;
        
        // Cách khác: Sử dụng Objects.hash()
        // return Objects.hash(name, age, gender);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (obj == this) return true;
        if (!(obj instanceof User user)) return false;

        return Objects.equals(user.name, name)
            && Objects.equals(user.age, age)
            && Objects.equals(user.gender, gender);
    }
}

Thuật toán ghi đè hashCode được áp dụng như sau: [ \text{hash} = val[0] \times 31^{(n-1)} + val[1] \times 31^{(n-2)} + … + val[n-1] ]

Thuật toán này dựa trên cách thức triển khai của String.hashCode() trong JDK. Giá trị băm của mỗi thuộc tính được tính bằng cách nhân giá trị băm trước đó với 31 và cộng thêm giá trị băm của thuộc tính hiện tại. Lý do lựa chọn số 31 là vì nó là một số nguyên tố lẻ, giúp giữ lại thông tin tốt hơn so với các số chẵn. Ngoài ra, phép nhân với 31 có thể được tối ưu hóa bởi máy ảo hiện đại thành phép dịch chuyển bit và trừ đi (31 * i == (i << 5) - i).

Phương thức equals được ghi đè rất đơn giản: Kiểm tra đối tượng có phải là kiểu User và tất cả các trường có bằng nhau hay không.

Sau khi ghi đè, chúng ta thử nghiệm lại và nhận thấy rằng user1.equals(user2) và user1.hashCode() == user2.hashCode() đều trả về true. Khi thêm cả hai đối tượng vào HashMap, kích thước của HashMap là 1, phù hợp với mong đợi.

// Sau khi ghi đè hashCode và equals của lớp User
User user1 = new User("Larry", 18, User.Gender.MALE);
User user2 = new User("Larry", 18, User.Gender.MALE);

System.out.println(user1.equals(user2)); // true
System.out.println(user1.hashCode() == user2.hashCode()); // true

Map<User, Boolean> map = new HashMap<>();
map.put(user1, true);
map.put(user2, true);

System.out.println(map.size()); // 1

Tóm lại, bài viết đã giải thích lý do tại sao khi ghi đè equals cần phải đồng thời ghi đè hashCode, cũng như cung cấp ví dụ minh họa. Mã nguồn đầy đủ đã được tải lên GitHub cá nhân của tác giả, mời bạn đọc quan tâm hoặc fork.