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 thời gian/không gian

Giờ ta đã biết độ phức tạp thời gian và không gian!

Áp dụng hiểu biết này để viết mã hiệu quả hơn như thế nào?

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 xây dựng hệ thống quản lý người dùng
Cần kiểm tra với một tên người dùng 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 phần tử duy nhất với tra cứu nhanh
$O(1)$ thời gian trung bình cho thêm, xóa, kiểm tra 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

Như từ điển, từ (khóa) -> định nghĩa (giá trị)
HashMap: $O(1)$ thời gian trung bình 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()
Ở ví dụ ArrayList, ta không biết chỉ mục của username cần tìm
Dùng hashcode() để chuyển đối tượng thành chỉ mục có thể tra
Ví dụ pavlos.2020 -> 35189

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

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

HashMap và HashSet dùng một mảng nền tảng
Khi thêm phần tử:
- Java gọi hashCode() trên phần tử để lấy số nguyên
- Lấy số đó modulo để ra 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!

Va chạm

Khi nhiều mục rơi vào cùng một bucket
- Gọi là va chạm (collision)
Dùng 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 như chọn đúng dụng cụ cho công việc — búa (ArrayList) hợp với đinh nhưng tệ với vít (lúc này Set hợp hơn).

Dụng cụ

Ayo berlatih!

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