高效資料結構：Set 與 Map

Java 程式碼最佳化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

應用空間／時間複雜度

你現在已經了解空間與時間複雜度了！

要如何運用這些觀念來寫更高效的程式碼？

選對資料結構就對了！

使用者管理系統

我們正在打造使用者管理系統
需要檢查給定的使用者名稱是否存在
若用 list：複雜度為 $O(n)$

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

Set

由不重複元素組成，查找速度快
新增、移除、檢查是否存在的平均時間複雜度為 $O(1)$

改良版使用者管理系統：

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

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

Map

類似字典：單字（key）→ 定義（value）
HashMap：操作的平均時間複雜度為 $O(1)$

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 範例中，我們不知道要找的使用者名稱索引
用 hashcode() 方法可把物件轉成可查找的索引
例如 pavlos.2020 -> 35189

pavlos.2020 經過 hashcode 處理後得到 35189

元素索引化

HashMap 與 HashSet 內部以陣列儲存
當加入元素時：
- Java 會呼叫元素的 hashCode() 以取得整數
- 對該整數取模以取得桶位編號

範例：

[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!

碰撞

當多個項目落在同一個桶位
- 稱為碰撞（collision）
桶位內用 LinkedList 連結
因此我們說平均為 $O(1)$

重點提示

選資料結構就像選工具——錘子（ArrayList）敲釘子很好用，但鎖螺絲就很差（這時 Set 可能更適合）。

一個打開的工具箱，內有錘子、螺絲起子、扳手與鉗子並排放置

一起來練習吧！

Java 程式碼最佳化