高效数据结构：Set 与 Map

Java 代码优化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

应用空间/时间复杂度

我们已了解空间与时间复杂度！

如何运用它来写更高效的代码？

选择合适的数据结构！

用户管理系统示例

我们在构建用户管理系统
需要检查给定用户名的用户是否存在
使用列表：复杂度为 $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（映射）

类似字典，词（键）-> 释义（值）
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!

碰撞

当多个项落入同一桶
- 称为碰撞
桶内使用 LinkedList
因此我们说平均为 $O(1)$

提示

选择数据结构就像为任务选对工具——锤子（ArrayList）适合钉子，但拧螺丝时也许用 Set 更好。

让我们来练习！

Java 代码优化