Map和Set通过树形（如TreeMap，O(log n)）或哈希（如HashMap，平均O(1)）实现，将查找、插入、删除从O(n)优化为稳定高效，适用于动态频繁操作场景。
直接用遍历或排序+二分来查数据，在动态场景下容易卡住——尤其当插入、删除频繁，或数据无序、规模变大时。Map 和 Set 的价值，就在于把查找、插入、删除这些操作从 O(n) 或 O(log n)（需预排序）拉到稳定高效的水平，关键看你怎么选实现方式。
先分清两类底层实现：树形 vs 哈希
Map 和 Set 不是单一结构，而是接口或抽象容器，具体效率取决于你用的是哪种子类：
- TreeMap / TreeSet：基于红黑树，元素自动有序，所有操作（增删查）时间复杂度都是 O(log n)；适合需要范围查询（比如“查学号在1000–2000之间的学生”）、或结果必须保持顺序的场景。
-
HashMap / HashSet（或 C++ 的
unordered_map/unordered_set）：基于哈希表，平均情况下增删查都是 O(1)，最坏退化为 O(n)（极少见，通常因哈希冲突严重或负载因子过高）；适合纯键值匹配、不关心顺序、追求极致响应速度的场景，比如用户登录态校验、缓存命中判断。
用 Map 替代“遍历找值”的典型重构
比如原逻辑是：维护一个学生列表 List<student></student>，每次按学号查姓名都要 for 循环——O(n) 查找，n=10万时可能耗几十毫秒。换成 Map 后：
- 以学号为 key（如
String id），姓名或完整 Student 对象为 value； - 初始化时一次性构建
Map<string student></string>，耗时 O(n)； - map.get("2025001")，平均只要一次哈希+寻址，稳在 O(1)；
- 退学删人？
map.remove("2025001")，同样 O(1) 平均；转专业改信息？直接map.put("2025001", newStudent)覆盖，无需遍历定位。
用 Set 替代“手动去重+存在性判断”
常见低效写法：每次加新用户名前，遍历已有列表确认是否重复；或用 List 存所有访问 IP，再统计“是否首次访问”。这类“查存在 + 保唯一”正是 Set 的本职工作：
- 声明
Set<string> visitedIps = new HashSet();</string> - 判断是否首次访问：
if (visitedIps.add(ip)) { /* 是第一次 */ }——add()方法自带返回值：true 表示新增成功（即原来没有），false 表示已存在；一行代码同时完成“查+插”，且平均 O(1)； - 不用再写 if (!list.contains(ip)) { list.add(ip); } 这种两趟遍历（contains 一次，add 可能再一次），避免了 O(n) × 2 的开销。
注意边界：别让哈希拖慢你
HashMap/HashSet 的 O(1) 是期望值，不是绝对保障。实际中要注意：
- 自定义对象作 key 时，必须正确重写
hashCode()和equals()，否则同一逻辑 key 可能散列到不同桶，导致查不到； - 初始容量设太小（如默认16），大量 put 会触发多次扩容重哈希，影响吞吐；高频写场景建议预估 size，构造时指定初始容量；
- 如果业务强依赖有序性（比如按插入顺序遍历），别硬套 HashMap——可选
LinkedHashMap（保持插入序）或TreeMap（保持自然序/定制序）。
