contains() 方法的效率完全取决于你调用的对象是什么，不同集合类的底层实现天差地别，导致其 contains() 方法的性能表现有云泥之别。

我们将从最好到最差的顺序，依次分析几种常见集合的 contains() 效率。

HashSet 和 HashMap 的 contains()

这是 Java 中最高效的 contains() 操作。

• 数据结构: 基于哈希表（Hash Table）实现。
• 时间复杂度: 平均 O(1)，最坏情况 O(n)。

工作原理

1. 计算哈希码: 当你调用 hashSet.contains(element) 时，Java 首先会调用该 element 对象的 hashCode() 方法,得到一个整数的哈希码。
2. 计算桶索引: 然后通过这个哈希码，通过一个内部算法（通常是 hash & (n-1)，n 是桶的数量）计算出这个元素应该存放在哪个“桶”（Bucket）中,桶可以看作是一个数组的索引位置。
3. 比较元素:
   • 最佳情况: 如果这个桶是空的，contains() 方法直接返回 false,非常快。
   • 一般情况: 如果这个桶不为空，Java 会遍历这个桶中的所有元素（因为不同的元素可能有相同的哈希码，这叫“哈希冲突”），并使用 equals() 方法逐个比较,看是否能找到完全匹配的元素。
   • 最坏情况: 如果所有元素的哈希码都一样（比如一个设计糟糕的 hashCode() 方法），那么所有的元素都会被放进同一个桶里，HashSet 就退化成了一个链表，contains() 的时间复杂度就变成了 O(n)。

性能关键点

• hashCode() 和 equals() 的实现质量: 这是 HashSet 性能的生命线。
  • hashCode() 必须高效：计算过程不能太耗时。
  • hashCode() 必须分布均匀：好的哈希码应该能让元素均匀地分布在各个桶中,最大限度地减少哈希冲突。
  • equals() 必须高效：比较逻辑要尽量简单快速。
  • 一致性: 如果两个对象通过 equals() 比较相等，那么它们的 hashCode() 必须相等，反之不成立（哈希码相等的对象不一定 equals）。

对于需要频繁进行 contains()、add()、remove() 操作的场景，HashSet 是首选,其性能是无与伦比的。

HashMap 的 containsKey()

HashMap 没有 contains() 方法，但有 containsKey(Object key) 和 containsValue(Object value),它们的效率不同。

• containsKey(Object key):

  • 时间复杂度: 平均 O(1)。
  • 原理: 与 HashSet.contains() 完全相同，都是通过 key 的哈希码找到对应的桶，然后在该桶里用 equals() 比较查找,这是哈希表的核心优势。

• containsValue(Object value):

  • 时间复杂度: O(n)。
  • 原理: 这是因为 HashMap 内部是通过 key 来组织数据的，而 value 只是存储在桶中的元素的一部分，要查找一个 value，没有捷径，只能遍历整个 HashMap 的所有桶，然后对每个桶里的元素检查其 value 是否匹配,这个过程无法利用哈希码来加速。

在 HashMap 中，使用 containsKey() 是高效的，但要避免在大型 HashMap 上频繁使用 containsValue()。

TreeSet 和 TreeMap 的 contains()

这类集合的 contains() 效率也很好,但略逊于哈希表。

• 数据结构: 基于红黑树（一种自平衡二叉搜索树）实现。
• 时间复杂度: O(log n)，n 是集合中的元素数量。

工作原理

红黑树是一种有序的数据结构。contains() 操作类似于在二叉搜索树中查找元素：

1. 从根节点开始比较。
2. 如果要查找的元素比当前节点小,就进入左子树。
3. 如果要查找的元素比当前节点大,就进入右子树。
4. 如果相等,就找到了。
5. 重复这个过程，直到找到元素或者到达叶子节点（未找到）。

由于树是平衡的，从根到任意节点的路径长度都控制在 log n 的量级,因此查找效率非常高。

性能关键点

• 元素必须可比较: 要使用 TreeSet 或 TreeMap，存入的元素必须实现 Comparable 接口，或者在构造时提供一个 Comparator,因为树需要根据元素的顺序来组织。
• 空间开销: 红黑树节点比哈希表的桶结构更复杂，所以内存占用通常比 HashMap 稍高。

当你不仅需要高效的查找，还需要保持元素有序时，TreeSet / TreeMap 是比 HashSet / HashMap 更好的选择。

ArrayList 和 LinkedList 的 contains()

这是效率最低的 contains() 操作,应该尽量避免在大型集合上使用。

• 数据结构: 都是线性表,但内部实现不同。
• 时间复杂度: O(n)。

ArrayList 的 contains()

ArrayList 底层是数组。contains() 方法必须：

1. 从数组的第一个元素开始,一个接一个地遍历。
2. 对遍历到的每一个元素，都调用 equals() 方法进行比较。
3. 直到找到匹配的元素,或者遍历完整个数组为止。

最坏情况下（元素不存在或在最后），需要比较 n 次。

LinkedList 的 contains()

LinkedList 底层是双向链表。contains() 方法也必须：

1. 从头节点（或尾节点）开始,沿着链表的指针一个接一个地遍历。
2. 对遍历到的每一个节点，都调用 equals() 方法进行比较。
3. 直到找到匹配的节点,或者遍历完整个链表为止。

同样，时间复杂度是 O(n)。

ArrayList vs. LinkedList 的 contains()

虽然两者都是 O(n)，但在实际应用中，ArrayList 的 contains() 通常比 LinkedList 更快一些,这是因为：

• 缓存局部性: ArrayList 的元素在内存中是连续存储的，CPU 在遍历时可以利用缓存预取机制，一次性加载多个连续的元素到高速缓存中,访问速度极快。
• 随机访问: ArrayList 的随机访问（通过索引）是 O(1) 的，虽然 contains() 不直接使用索引,但其底层数组的连续性带来了优势。
• LinkedList 的节点在内存中是分散的，每个节点都包含指向前后节点的指针,遍历时会产生更多的内存访问开销。

绝对不要将 ArrayList 或 LinkedList 用于需要频繁进行 contains() 检查的场景，如果必须使用，请优先选择 ArrayList。

总结与对比表

最佳实践建议

1. 首选 HashSet / HashMap: 如果你的核心需求是快速判断一个元素/键是否存在，并且没有排序要求，那么毫不犹豫地选择它们，这是 Java 集合框架为高性能查找场景提供的标准解决方案。

2. 需要排序则用 TreeSet / TreeMap: 当“有序”和“快速查找”同样重要时,选择基于树的集合。

3. 避免在 List 上做查找: 如果你发现你的代码中频繁地在 ArrayList 或 LinkedList 上调用 contains()，并且集合规模可能变得很大，请重构代码，改用 HashSet 来存储需要频繁查询的元素,一个常见的模式是：

   // 不好的做法
   List<String> users = ...; // 一个可能很大的列表
   if (users.contains("admin")) { ... } // O(n) 操作，很慢
   // 好的做法
   Set<String> userSet = new HashSet<>(users); // 一次性转换，O(n)
   if (userSet.contains("admin")) { ... } // O(1) 操作，极快

4. 自定义对象要重写 equals 和 hashCode: 如果你想在 HashSet 或 HashMap 中使用自定义类的对象，请务必正确地重写 equals() 和 hashCode() 方法,以保证其正确性和高性能。