为何用Set进行过滤比用Vector过滤性能更优异？

核心原因：存在性检查的时间复杂度差异 #

你看到的性能提升，本质是Vector和Set的存在性查找效率天差地别：

• Vector是线性查找，时间复杂度为O(n)（n为集合元素数量）
• Clojure的HashSet（`#{}）是哈希查找，平均时间复杂度为O(1)

拆解初始代码的性能瓶颈 #

初始代码中，每次过滤maps-to-search-through里的元素时，都会执行(some #(= (:id i) %) target-ids)：

(filter (fn [i] (some #(= (:id i) %) target-ids)) maps-to-search-through)

• 对每个待检查的map，some会遍历整个target-ids Vector，直到找到匹配的ID或者遍历完所有元素
• 假设target-ids有N个元素，maps-to-search-through有M个元素（M≥5N），总运算量是O(M*N)。当N和M都是数千级时，总运算量会达到百万级，性能自然低下。

优化后代码的高效逻辑 #

把target-ids改成HashSet后，代码变成：

(filter (comp target-ids :id) maps-to-search-through)

这里的关键是：Clojure的Set实现了IFn接口，所以可以直接把Set当作函数来调用——传入一个元素，它会返回该元素是否存在于Set中。

• 哈希查找的原理是：通过元素的哈希值直接定位到存储位置，不需要遍历整个集合。即使有哈希冲突，冲突的元素数量也极少，平均下来只需要常数时间就能完成检查
• 总运算量降到O(M)，数千级的M只需要几千次运算，和之前的百万级运算量比，性能提升非常明显。

补充细节 #

• Clojure的Vector是基于数组的有序集合，查找元素必须从头开始逐个比对，元素越多，查找耗时越长
• Clojure的HashSet基于哈希表实现，每个元素的存储位置由哈希值决定，查找时跳过了大部分无关元素，这是它能实现O(1)平均查找时间的核心原因

内容的提问来源于stack exchange，提问作者mbake