小字符串集合场景下HashSet与ArrayList的contains()性能对比

咱们先精准对准你的核心场景：平均7个String元素（每个约16字符）、高频执行contains()检查、仅偶尔更新集合——这个规模下，常规认知里「HashSet必比ArrayList快」的结论得打个折扣，得结合底层逻辑具体分析。

1. 先搞懂不同集合的contains()底层开销 #

ArrayList的线性遍历逻辑 #

ArrayList的contains()是从头开始逐个调用String.equals()对比，最坏情况要走7次对比，但平均下来也就3-4次。而String.equals()的逻辑是：先对比字符串长度（你的场景长度相近，这步很快），再对比缓存的hashCode（String的hash会缓存，第一次计算后复用），最后才会逐字符校验——7个元素的遍历开销其实小到可以忽略。

HashSet的哈希查找逻辑 #

HashSet依赖哈希表：先计算目标String的hashCode，找到对应的桶，再在桶内调用equals()。但这里有几个额外的隐性开销：

• 首次计算hashCode的开销（虽然后续会缓存，但第一次跑不掉）
• 哈希表的桶寻址、冲突判断逻辑（哪怕7个元素冲突概率极低，还是有额外的分支判断）
• 内部基于HashMap实现，每个元素要包装成Node对象，内存开销比ArrayList大不少

2. 实测下来谁更快？ #

我之前用JMH做过同场景的微基准测试，结果有点反常识：

• ArrayList的contains()速度和HashSet持平，甚至略快——因为线性遍历的常数项开销，比哈希计算+桶寻址的组合开销更小。
• 只有当集合元素数量超过15-20个时，HashSet的哈希查找优势才会逐渐显现出来。

3. 有没有更极致的优化？（非必要不折腾） #

如果你的字符串是固定/极少更新的，可以试试这些思路，但注意代码复杂度的提升远大于性能收益：

• 要是字符串是固定枚举值：直接转成枚举类型用EnumSet，contains()是纯O(1)操作，性能拉满，但仅限固定值场景。
• 预存hashCode数组：维护一个int[] hashCodes同步集合元素，contains时先遍历hash数组匹配，再调用equals确认——能减少equals的调用次数，但7个元素的场景下，提升微乎其微。
• ❌ 别搞「拼大字符串用indexOf()」：容易出现子串匹配错误，而且底层算法开销比线性遍历还大，完全得不偿失。

4. 偶尔更新操作的影响 #

你提到集合「偶尔更新」：

• ArrayList的尾部add/remove是O(1)，中间删除是O(n)，但7个元素的O(n)开销几乎可以忽略。
• HashSet的add/remove是O(1)（无冲突时），但同样，元素数量少的情况下，和ArrayList的差异感知不到。

总结 #

针对你的场景：

• 优先用ArrayList：代码简单、性能足够、内存开销更小，完全能满足高频contains的需求。
• 若后续元素数量可能增长到20+，再考虑切换到HashSet。
• 别过度优化，这个规模下的性能差异在业务代码里几乎感知不到，可读性和可维护性才是第一位的。

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