Cách custom Key cho HashMap trong Java

Mục lục

1 Quản lý key trong HashMap
- 1.1 Cấu trúc bên trong HashMap
- 1.2 Quá trình thêm và tìm kiếm cặp key-value trong Map
2 Custom key trong HashMap
3 Tóm lược

Trong bài viết này chúng ta sẽ cùng nhau tìm hiểu nội bộ bên trong HashMap của Java hoạt động như thế nào và từ đó chúng ta có thể custom một key-class phù hợp với mục đích riêng của mình.

Quản lý key trong HashMap

Cấu trúc bên trong HashMap

Map được sử dụng để lưu trữ các giá trị-value thuộc về một khóa-key xác định. Key được dùng để định danh duy nhất trong một Map.

HashMap được xây dựng dựa trên cấu trúc hash-based có thể giải thích đơn giản như sơ đồ sau

Trong một Map không tồn tại một cặp key trùng nhau nên người ta đã kết hợp sử dụng Object#hashCode() để tính ra mã hash tương ứng với một địa chỉ nơi mà cặp key-value sẽ được lưu trữ. Tuy nhiên có khả năng có nhiều cặp key khác nhau nhưng là cùng mã hash đồng nghĩa với việc chúng sẽ được lưu trữ cùng một địa chỉ, để giải quyết vấn đề này người ta sử dụng thêm Object#equals() để kiểm tra xem các key có cùng mã hash có trùng lặp hay không.

Nếu quá trình kiểm tra bằng Object#equals() phát hiện key mới thêm vào đã tồn tại trước đó thì giá trị cuối cùng sẽ thay thế cho giá trị cũ
Ngược lại cặp key-value mới này sẽ nối đôi sau các cặp key-value có cùng mã hash khác được thêm vào trước đó.

Như hình trên các bạn có thể thấy với mã hash = 10 chúng ta có 2 cặp key-value, hash = 10 chỉ có một cặp key-value duy nhất và hash = 367 có đến 3 cặp key-value cùng tồn tại.

Quá trình thêm và tìm kiếm cặp key-value trong Map

Giả sử dụng chúng ta có một HashMap với key là String và value là một số nguyên Integer.

Map<String, Integer> items = new HashMap<>();
// insert
items.put("158-865-A", 56);
// find
Integer count = items.get("158-865-A");

Quá trình thêm một cặp key-value vào HashMap sẽ diễn ra như sau:

Gọi “158-865-A”.hashCode() để lấy mã hash
Lấy ra danh sách các key có cùng mã hash đã được thêm vào trước đó
Duyệt và so sánh với từng key trong danh sách vừa lấy được bằng cách “158-865-A”.equals(key)
1. Nếu equals() trả về true thì giá trị mới thêm vào sẽ thay thế giá trị cũ
2. Nếu đi đến hết danh sách các key trên mà vẫn không tìm thấy key nào thỏa equals() bằng true thì thêm một cặp key-value mới vào

Quá trình tìm kiếm cũng làm tương tự

Gọi “158-865-A”.hashCode() để lấy mã hash
Lấy ra danh sách các key có cùng mã hash đã được thêm vào trước đó
Duyệt và so sánh với từng key trong danh sách vừa lấy được bằng cách “158-865-A”.equals(key)
- Nếu equals() trả về true trả về value tương ứng
- Nếu đã đi hết danh sách mà vẫn chưa có key nào thỏa thì trả về null.

Custom key trong HashMap

Dựa vào kiến thức ở phần trên chúng ta có thể thấy rằng để custom key cho HashMap chúng ta cần triển khai 2 hàm equals() và hashCode() sao cho chúng hoạt động chính xác.

Các bạn đừng quá lo lắng phải làm sao để triển khai 2 method này cho đúng vì hiện tại hầu hết các IDE đều đã hỗ trợ tự sinh code cho 2 method này. Ngoài ra chúng ta cũng có thể sử dụng Lombok một thư viện cho phép tự sinh code thông qua các annotation.

Có điều chúng ta cần lưu ý rằng:

Không thay đổi mã hash của một object khi nó đang được sử dụng làm key trong HashMap
Key class nên được thiết kế immutable – không thể chỉnh sửa sau khi khởi tạo

Cuối cùng chúng ta sẽ thử triển khai một custom key dùng trong HashMap

public class Coordinate {
    private final int x;
    private final int y;
    private int hashCode;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
        this.hashCode = Objects.hash(x, y);
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Coordinate that = (Coordinate) o;
        return x == that.x && y == that.y;
    }

    @Override
    public int hashCode() {
        return this.hashCode;
    }
}

Class Coordinate sẽ được dùng làm key cho HashMap do đó chúng ta cần override equals() và hashCode() bên trong class này. Và sau đó sử dụng như thông thường

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2);
pixels.put(coord, Color.CYAN);
// read the color
Color color = pixels.get(new Coordinate(1, 2));

Tuy việc triển khai trên hoạt động ổn nhưng với việc chúng ta tự triển khai hashCode() có thể gây ảnh hưởng đến hiệu suất của HashMap. Hãy thử tưởng tượng nếu hàm hashCode() này trả về cùng một giá trị cho rất nhiều key khác nhau, điều này sẽ dẫn đến nhiều cặp key-value sẽ được lưu trữ cùng một địa chỉ sẽ khiến việc truy xuất trở nên kém hiệu quả hơn.

Một hashCode() hoạt động tốt là làm sao cố gắng tạo ra các mã hash khác nhau càng nhiều càng tốt trên các cặp key khác nhau. Lombok là một thư viện giúp chúng ta làm tốt điều này, và hơn nữa là việc sử dụng nó rất dễ dàng.

@RequiredArgsConstructor
@Getter
@EqualsAndHashCode(cacheStrategy = CacheStrategy.LAZY)
public class Coordinate {
    private final int x;
    private final int y;
}

Cấu trúc của một HashMap hoạt động tốt sẽ trông như thế này.

Bây giờ để làm rõ, mình sẽ cho các bạn thấy việc một hàm hashCode() hoạt động kém hiệu quả sẽ gặp vấn đề gì

public class Coordinate {

    ...

    @Override
    public int hashCode() {
        return 1;
    }
}

Chúng ta có thể thấy rằng hashCode() trong Coordinate luôn trả về 1 cho mọi key, khi chúng ta thêm phần tử vào nó sẽ có cấu trúc trông như thế này

Việc tìm kiếm giờ đây sẽ tốn một chi phí O(n) thay vì O(1) như những gì mà chúng ta mong muốn khi sử dụng HashMap.

Một vấn đề nghiêm trọng khác chúng ta cần lưu ý đến đó là thay đổi giá trị key trong HashMap. Nếu chúng ta làm việc thì giá trị hash sẽ thay đổi và hệ quả là chúng ta sẽ vĩnh viễn không thể truy xuất được giá trị đã lưu trước đó.

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2); // x=1, y=2
pixels.put(coord, Color.CYAN);
coord.setX(3); // x=3, y=2

Color color = pixels.get(coord); ==> null

Vì giá trị được lưu dựa trên mã hash cũ của key, sau đó chúng ta thay đổi giá trị của một thuộc tính trong Coordinate dẫn đến mã hash thay đổi và như vậy chúng ta sẽ vĩnh viễn mất đi giá trị đã lưu trước đó.

Tóm lược

Qua bài viết này chúng ta đã biết cách custom key cho HashMap bằng việc override lại equals() và hashCode() method. Bên cạnh đó chúng cũng hết sức lưu ý đảm bảo tính immutable class key class, đơn giản chỉ cần chúng ta không cung cấp setter method là có thể đạt được tính chất này.

Nguồn: Baeldung