集合操作的“快慢”取决于数据量翻倍后的耗时变化趋势，O表示法关注增长阶数而非绝对时间；ArrayList.contains()为O(n)，HashSet.contains()为O(1)；底层结构决定复杂度：数组→随机访问O(1)、增删O(n)；哈希表→增删查键O(1)、查值O(n)；红黑树→所有键操作O(log n)；Python中list in为O(n)，set in为O(1)，性能差可达千倍；需警惕哈希碰撞、扩容及可变键导致的退化。
集合操作的“快慢”不是看秒数，而是看数据量翻倍后耗时怎么变
大O表示法不是测你代码跑几毫秒，而是回答：“当元素从100个涨到100万，这个 contains() 操作会慢10倍、100倍，还是基本不变？” 它剥离机器差异、常数系数和低阶项，只盯住最主导的增长趋势。比如 ArrayList.contains() 是 O(n)，意味着查100万条要≈100万次比较；而 HashSet.contains() 是 O(1)，哪怕存1000万个元素，平均也只要常数次哈希+比对。
Java常见集合增删改查时间复杂度速查（底层决定一切）
别背表，记住三个关键底层结构，所有复杂度就顺下来了：
-
ArrayList：底层数组 → 随机访问快（get(i)是O(1)），但中间插入/删除要搬数据（add(index, e)/remove(index)是O(n)） -
HashMap（HashSet、LinkedHashMap都基于它）：哈希表 → 增删查键（put()、get()、containsKey()）全是O(1)；但查值（containsValue()）必须遍历，是O(n) -
TreeMap（TreeSet同理）：红黑树 → 所有基于键的操作（put()、get()、containsKey()）都是O(log n)，稳定但比哈希表慢一截
Python里 in 查 list 和 set，性能差1000倍真不夸张
写 if x in my_list: 看似简单，实际是隐式遍历——10万元素平均要5万次比对；换成 if x in my_set:，哈希一算地址就完事，几乎不随规模增长。实测：10万元素下，list in 耗时约 5ms，set in 约 0.005ms。
- 别用
list存需要频繁查找的 ID 列表，转成set或dict（哪怕 value 用None） -
tuple的in也是O(n)，不可变 ≠ 查询快 -
dict.keys()在 Python 3.7+ 是视图对象，in检查仍是O(1)；但list(dict.keys())再查就是O(n)了
最容易被忽略的“伪常数”陷阱：哈希碰撞和扩容
O(1) 不代表永远快，它依赖哈希函数质量与负载因子。当 HashMap 或 dict 元素太多、哈希冲突严重时，链表或红黑树退化，单次 get() 可能落到 O(n)；扩容时还要重建哈希表，瞬间卡顿。
- 初始化集合时预估大小，用带初始容量的构造器（如
new HashMap(1024)或set().union(large_list)改为set(large_list)） - 避免用可变对象（如
list、自定义未重写hashCode()的类）作HashMap键——哈希值可能变，导致查不到 - Java 中
ConcurrentHashMap的get()仍是O(1)，但size()是O(1)还是O(n)？其实是后者（需遍历分段计数），别误当常数用
真正影响性能的，往往不是理论复杂度标称值，而是你用的结构是否匹配场景，以及有没有踩中底层实现的边界条件。
