高效求集合交集需依数据有序性、内存、规模等条件选方法：无序且内存宽裕用哈希表法；已有序用双指针法；整数范围集中用分桶+Bitmap；动态更新高频查询用跳表或平衡树。
高效求集合交集，关键不在“怎么做”，而在“根据什么条件选方法”。数据是否有序、内存是否充足、规模有多大、是否允许额外空间——这些决定了最优解。没有银弹，只有适配。
数据无序且内存宽松：哈希表法最实用
把一个集合全塞进哈希表（如HashSet），再遍历另一个集合查是否存在。时间复杂度稳定在 O(m + n)，查找操作平均 O(1)。适合大多数日常场景，比如 Java 中用 set1.retainAll(set2)，或 Python 直接用 set(list1) & set(list2)。
- 优点：实现简单、速度快、对原始顺序无要求
- 注意：结果自动去重且无序；若需保持原顺序，可用
LinkedHashSet或先记录索引 - 适用场景：中小规模数据（几万到百万级）、内存充裕、不强调元素顺序
数据已有序或可排序：双指针拉链法更省空间
两个升序数组/链表，用两个指针从头开始比：相等就加入结果，小的指针前移。全程只遍历一遍，时间 O(m + n)，空间 O(1)（不含结果存储）。
- 优点：零哈希开销、空间友好、天然支持流式处理（如数据库游标、日志文件逐行读）
- 注意：需提前排序时，总代价是 O(m log m + n log n + m + n)，仅当数据本就有序才真正高效
- 适用场景：归并日志、索引合并、数据库多路归并、内存受限嵌入式环境
超大规模+范围集中：分桶 + Bitmap 加速
当所有元素落在较窄整数区间内（如用户ID在 [1, 10⁶]），可按值域分桶（如每桶 10⁴ 个数），每桶内用 bitmap 表示存在性。两集合同桶 bitmap 做按位与，结果中为 1 的位即交集元素。
- 优点：单桶内交集是 O(1) 位运算，整体接近线性；极适合批处理、离线计算
- 缺点：内存占用随值域上限线性增长；非整数或稀疏分布时不适用
- 典型应用：广告定向中的用户 ID 交集、风控系统设备指纹匹配
高频查询+动态更新：跳表或平衡树优化
若集合持续增删，且频繁求交（如推荐系统实时协同过滤），用跳表（skiplist）或红黑树维护有序结构。交集可借助“跳跃”能力跳过大量无关元素，理论复杂度接近 O(log n)，远优于朴素拉链法。
- 优势：支持插入/删除/交集三合一操作；适合在线服务场景
- 代价：实现复杂；常用于底层中间件（如 Redis Sorted Set、LevelDB 迭代器）
- 替代方案：部分场景可用布隆过滤器预筛，再用精确结构验证
