Cấu trúc dữ liệu hiệu quả: Set & Map

Tối ưu hóa mã trong Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Áp dụng độ phức tạp không gian/thời gian

Giờ bạn đã nắm độ phức tạp về không gian và thời gian!

Làm sao áp dụng hiểu biết này để viết mã hiệu quả hơn?

Bằng cách chọn đúng cấu trúc dữ liệu!

Hệ thống quản lý người dùng

Ta đang xây dựng hệ thống quản lý người dùng
Cần kiểm tra với một username cho trước, người dùng có tồn tại không
Dùng list: độ phức tạp $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Set

Tập hợp các phần tử duy nhất với thời gian tra cứu nhanh
Trung bình $O(1)$ cho thêm, xóa, và kiểm tra phần tử tồn tại

Giải pháp cải tiến cho quản lý người dùng:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}

Map

Giống từ điển, từ (key) -> định nghĩa (value)
HashMap: trung bình $O(1)$ cho các thao tác

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}

Phương thức hashcode

Điều làm chúng nhanh -> hashCode()
Trong ví dụ ArrayList, ta không biết chỉ số của username cần tìm
Dùng phương thức hashcode(), ta có thể chuyển một đối tượng thành chỉ số để tra cứu
Ví dụ pavlos.2020 -> 35189

pavlos.2020 được xử lý qua hashcode, cho ra 35189

Đánh chỉ mục phần tử

HashMap và HashSet dùng một mảng bên dưới
Khi thêm phần tử:
- Java gọi hashCode() trên phần tử để lấy một số nguyên
- Lấy modulo của số đó để có số bucket

Ví dụ:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- đó là bucket của ta!

Va chạm

Khi nhiều mục rơi vào cùng một bucket
- Gọi là va chạm (collision)
LinkedList cho bucket
Vì vậy ta nói $O(1)$ trung bình

Ghi nhớ

Chọn cấu trúc dữ liệu giống như chọn đúng dụng cụ cho công việc - búa (ArrayList) hợp với đóng đinh nhưng tệ với vít (nơi Set phù hợp hơn).

Một hộp dụng cụ mở chứa búa, tua vít, cờ lê và kìm cạnh nhau

Cùng luyện tập nào!

Tối ưu hóa mã trong Java