โครงสร้างข้อมูลที่มีประสิทธิภาพ: Sets & Maps

การปรับแต่งโค้ดใน Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

การประยุกต์ใช้ space/time complexity

ตอนนี้เรารู้จัก space และ time complexity แล้ว!

จะนำความรู้นี้ไปเขียนโค้ดที่มีประสิทธิภาพมากขึ้นได้อย่างไร?

ด้วยการเลือกโครงสร้างข้อมูลให้เหมาะสม!

ระบบจัดการผู้ใช้งาน

กำลังสร้างระบบจัดการผู้ใช้งาน
ต้องการตรวจสอบว่า username ที่กำหนดนั้นมีอยู่ในระบบหรือไม่
ใช้ list: complexity $O(n)$

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

Sets

กลุ่มของสมาชิกที่ไม่ซ้ำกัน พร้อม lookup ที่รวดเร็ว
time complexity เฉลี่ย $O(1)$ สำหรับการเพิ่ม ลบ และตรวจสอบสมาชิก

โซลูชันระบบจัดการผู้ใช้งานที่ปรับปรุงแล้ว:

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

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

Maps

คล้ายพจนานุกรม คำ (key) -> ความหมาย (value)
HashMap: time complexity เฉลี่ย $O(1)$ สำหรับทุก operation

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

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

เมธอด Hashcode

สิ่งที่ทำให้รวดเร็ว -> hashCode()
ในตัวอย่าง ArrayList เราไม่รู้ index ของ username ที่ต้องการค้นหา
ด้วย hashcode() เราแปลง object ให้เป็น index ที่ใช้ค้นหาได้
เช่น pavlos.2020 -> 35189

pavlos.2020 ถูกประมวลผลด้วย hashcode ได้ผลลัพธ์เป็น 35189

การ index สมาชิก

HashMap และ HashSet มี array เป็นโครงสร้างภายใน
เมื่อเพิ่มสมาชิก:
- Java เรียก hashCode() บน element เพื่อรับค่า integer
- จากนั้นนำค่านั้นหาร modulo เพื่อหาหมายเลข bucket

ตัวอย่าง:

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

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- that's our bucket!

Collisions

เมื่อสมาชิกมากกว่าหนึ่งรายการอยู่ใน bucket เดียวกัน
- เรียกว่า collision
ใช้ LinkedList สำหรับ bucket
นั่นคือเหตุผลที่เราบอกว่า $O(1)$ โดยเฉลี่ย

สิ่งที่ควรจำ

การเลือกโครงสร้างข้อมูลเปรียบเหมือนการเลือกเครื่องมือให้เหมาะกับงาน - ค้อน (ArrayList) เหมาะกับตะปู แต่ไม่เหมาะกับสกรู (ซึ่ง Set อาจเป็นตัวเลือกที่ดีกว่า).

เครื่องมือช่าง

มาฝึกกันเถอะ!

การปรับแต่งโค้ดใน Java