0

Bóc tách hàm băm (hashing) trong Java: Khám phá Hashmap, Hashset và phương thức Hashcode()

Băm hay Hashing trong Java là một khái niệm nâng cao cho phép lưu trữ và truy xuất dữ liệu một cách hiệu quả nhất. Cho dù bạn là lập trình viên dày dặn kinh nghiệm hay là người mới bắt đầu, việc hiểu cách thức hoạt động của Hashing sẽ giúp nâng cao kỹ năng lập trình của bạn, cho phép mã của bạn chạy nhanh hơn rất nhiều.

Trong bài viết này, chúng ta sẽ phân tích mọi thứ về Hashing với ba trụ cột: HashMap, HashSet và phương thức hashCode(); các ví dụ mã đơn giản được bao gồm để bạn có thể bắt đầu ngay lập tức!

Hashing là gì?

Nói một cách đơn giản, hashing hay băm là một thủ tục chuyển đổi dữ liệu thành các giá trị số có kích thước cố định, thường được gọi là mã Hashing. Mã Hashing là duy nhất cho dữ liệu và cho phép các cấu trúc dữ liệu dựa trên Hashing tìm thấy dữ liệu nhanh chóng. Mục đích của Hasing là để tìm kiếm, chèn và xóa hiệu quả.

Tại sao nó lại quan trọng?

  • Tốc độ: Hashing có thể cung cấp khả năng truy xuất dữ liệu gần như ngay lập tức.
  • Loại bỏ trùng lặp: Hashing cho phép thêm các mục nhập duy nhất vào các cấu trúc dữ liệu như HashSet.

Bây giờ, chúng ta hãy cùng tìm hiểu cách Java sử dụng Hashing thông qua HashMap, HashSet và phương thức hashCode()!

HashMap trong Java: Lưu trữ dữ liệu theo cặp Key - Value

Một HashMap lưu trữ dữ liệu theo các cặp key - value, sử dụng Hashing để nhanh chóng tìm thấy giá trị được liên kết với một khóa cụ thể. Mỗi khóa được chuyển đổi thành một mã Hashing, xác định nơi cặp key - value sẽ được lưu trữ.

Vậy tại sao nên sử dụng HashMap?

  • Tra cứu nhanh: Bạn có thể tìm hoặc cập nhật giá trị bằng khóa trong thời gian không đổi.
  • Linh hoạt: Nó cho phép các giá trị null và các giá trị trùng lặp nhưng thực thi các khóa duy nhất.

Ví dụ minh họa về HashMap:

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<Integer, String> userMap = new HashMap<>();

        userMap.put(101, "Alice");
        userMap.put(102, "Bob");
        userMap.put(103, "Charlie");

        System.out.println("User with ID 101: " + userMap.get(101));

        userMap.remove(102);
        System.out.println("After removing ID 102: " + userMap);
    }
}

Trong ví dụ này, chúng ta lưu trữ ID của người dùng làm khóa và tên của họ làm giá trị. HashMap sử dụng mã băm của khóa để định vị giá trị một cách nhanh chóng, giúp việc truy xuất diễn ra nhanh chóng.

HashSet trong Java: Đảm bảo tính duy nhất của dữ liệu

Một HashSet được sử dụng để lưu trữ các phần tử duy nhất. Nó dựa vào phương thức hashCode() để đảm bảo không có hai phần tử nào giống hệt nhau. Nếu bạn cần một bộ sưu tập đảm bảo không có bản sao, HashSet là cấu trúc dữ liệu phù hợp với bạn!

Tại sao nên sử dụng HashSet?

  • Ngăn chặn trùng lặp: Nó tự động lọc ra các mục nhập trùng lặp.
  • Các thao tác nhanh chóng: Chèn, xóa và tra cứu nhanh chóng bằng cách sử dụng Hashing.

Ví dụ về HashSet:

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> userSet = new HashSet<>();

        userSet.add("Alice");
        userSet.add("Bob");
        userSet.add("Charlie");
        userSet.add("Alice"); 
        System.out.println("Is Bob in the set? " + userSet.contains("Bob"));

        userSet.remove("Charlie");

        System.out.println("Users in the set: " + userSet);
    }
}

Trong ví dụ này, "Alice" được thêm vào hai lần, nhưng HashSet chỉ lưu trữ nó một lần, đảm bảo không có bản sao. Đó chính là sự kỳ diệu của Hashing!

Phương thức hashCode()

Mọi đối tượng trong Java đều có một phương thức hashCode() được kế thừa từ lớp Object. Phương thức hashCode() tạo ra một mã Hashing số đại diện duy nhất cho dữ liệu của đối tượng. Tuy nhiên, nếu bạn đang làm việc với các đối tượng tùy chỉnh trong các bộ sưu tập như HashMap hoặc HashSet, điều cần thiết là ghi đè hashCode() và các phương thức equals().

Tại sao phải ghi đè hashCode()?

  • Để đảm bảo các đối tượng tùy chỉnh có thể được Hashing và so sánh đúng cách.
  • Để ngăn chặn các sự cố với việc lưu trữ hoặc tra cứu các đối tượng trong các cấu trúc dựa trên Hashing.

Ví dụ: Đối tượng tùy chỉnh với hashCode() và equals():

import java.util.Objects;

class User {
    private int id;
    private String name;

    public User(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        User user = (User) obj;
        return id == user.id && name.equals(user.name);
    }

    @Override
    public String toString() {
        return name + " (ID: " + id + ")";
    }
}

public class CustomObjectExample {
    public static void main(String[] args) {
        HashSet<User> users = new HashSet<>();

        users.add(new User(101, "Alice"));
        users.add(new User(102, "Bob"));
        users.add(new User(101, "Alice")); 

        System.out.println("Users in the set: " + users);
    }
}

Trong ví dụ này, chúng tôi đảm bảo rằng hai đối tượng User có cùng ID và tên được coi là bằng nhau, do đó HashSet có thể tránh thêm bản sao.

Cách thức hashCode() và equals() hoạt động cùng nhau

Khi một đối tượng được thêm vào HashMap hoặc HashSet, Java trước tiên sẽ kiểm tra hashCode() để xác định vị trí của đối tượng. Sau đó, phương thức equals() đảm bảo rằng các đối tượng được so sánh đúng cách để xác định sự bằng nhau.

Best pratices tốt nhất:

Luôn ghi đè hashCode() và equals() cùng nhau. Nếu equals() chỉ ra rằng hai đối tượng là bằng nhau, chúng phải có cùng hashCode().

Lời khuyên khi sử dụng Hash trong Java dành cho mọi cấp độ lập trình

  • Người mới bắt đầu: Hãy bắt đầu bằng cách nắm bắt cách HashMap và HashSet sử dụng mã Hashing để lưu trữ dữ liệu. Tập trung vào ứng dụng thực tế hơn là các chi tiết phức tạp.
  • Lập trình viên trung cấp: Ghi đè hashCode() và equals() trong các lớp của bạn để quan sát tác động của chúng đối với các bộ sưu tập dựa trên Hashing.
  • Lập trình viên cao cấp: Khám phá xung đột Hashing và tối ưu hóa hiệu suất trong các ứng dụng quy mô lớn, nơi hiệu quả Hashing chính là chìa khóa.

Cảm ơn các bạn đã theo dõi.


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.