contains() 方法的效率高度依赖于其所在的集合（Collection）的具体实现类型，笼统地谈论 contains() 的效率是没有意义的，因为它在不同数据结构中的底层实现和性能表现天差地别。

下面我们将从最坏、最好和平均情况三个维度，分析几种常见集合中 contains() 的效率。

核心结论先行

ArrayList 和 LinkedList (O(n) - 线性时间)

这两种列表的实现决定了它们的 contains() 方法效率较低。

ArrayList

• 底层结构: 一个动态数组，元素在内存中是连续存储的。
• contains() 实现: 遍历底层数组，从第一个元素开始，使用 equals() 方法逐个与目标元素进行比较，直到找到匹配的元素或遍历完整个数组。
• 时间复杂度: O(n) (大O符号)。
  • 最坏情况: 目标元素是最后一个，或者不存在，需要比较 n 次。
  • 最好情况: 目标元素是第一个，只需要比较 1 次。
  • 平均情况: 需要比较大约 n/2 次，时间复杂度仍为 O(n)。
• 示例代码:

  List<String> names = new ArrayList<>(Arrays.asList("Alice", "Bob", "Charlie", "David"));
  boolean containsAlice = names.contains("Alice"); // 快，O(1) 在最佳情况下
  boolean containsZoe = names.contains("Zoe");     // 慢，O(n) 在最坏情况下

LinkedList

• 底层结构: 一个双向链表，每个节点（Node）包含数据、指向前一个节点的指针和指向后一个节点的指针。
• contains() 实现: 同样需要遍历，但它不像 ArrayList 可以通过索引随机访问，它必须从头节点（或尾节点）开始，沿着指针逐个节点进行 equals() 比较。
• 时间复杂度: O(n)。
  • 性能和 ArrayList 一样，都随着元素数量 n 的增加而线性下降。
  • LinkedList 在随机访问上（get(i)）比 ArrayList 慢很多，但在头部和尾部插入/删除元素时更快，不过对于 contains() 这种操作，两者性能相近且都不理想。

HashSet (平均 O(1) - 常数时间)

HashSet 是为了解决 ArrayList 和 LinkedList 在 contains() 效率低下的问题而设计的。

• 底层结构: HashSet 内部使用一个 HashMap 来存储元素，它将元素作为 HashMap 的 key，一个固定的 Object 作为 value。
• contains() 实现:
  1. 计算哈希码: 对要查找的元素调用 hashCode() 方法，得到一个哈希码。
  2. 定位桶: 根据这个哈希码，通过一个哈希函数计算出该元素在 HashMap 数组（也叫“桶”或 bucket）中的存储位置（索引）。
  3. 比较元素:
     • 如果该位置是空的,说明元素不存在。
     • 如果该位置有元素,会先比较哈希码，如果哈希码相同，再调用 equals() 方法进行深度比较。
     • 哈希冲突: 如果多个元素的哈希码相同（哈希冲突），它们会以链表或红黑树的形式存储在同一个桶中，这时就需要在冲突的链表/树中遍历查找。
• 时间复杂度:
  • 平均情况: O(1)，理想情况下，哈希函数分布均匀，每个元素都能直接定位到自己的桶，无需比较或只需比较一次。
  • 最坏情况: O(n)，当所有元素的哈希码都相同时（一个糟糕的 hashCode() 实现），所有元素都会被存入同一个桶中，contains() 就退化成了在一个链表或数组中查找，效率变为 O(n)。
• 关键点: HashSet 的高效性依赖于两个因素：
  1. 一个好的 hashCode() 实现: 能让哈希码尽可能均匀分布。
  2. 正确的 equals() 和 hashCode() 协约: 如果两个对象通过 equals() 比较返回 true，那么它们的 hashCode() 必须相等，这能保证查找的正确性。

TreeSet (O(log n) - 对数时间)

TreeSet 提供的是一种有序的集合，它的效率介于 ArrayList 和 HashSet 之间。

• 底层结构: 红黑树，一种自平衡的二叉搜索树。
• contains() 实现: 利用二叉搜索树的特性进行查找，每次比较后，都能排除掉一半的子树。
  1. 从根节点开始比较。
  2. 如果目标元素小于当前节点,则在其左子树中继续查找。
  3. 如果目标元素大于当前节点,则在其右子树中继续查找。
  4. 如果相等,则找到。
  5. 如果到达叶子节点还没找到,则元素不存在。
• 时间复杂度: O(log n)。
  • 查找次数与树的高度成正比,由于红黑树是平衡的，其高度始终保持在 log n 级别。
  • 性能非常稳定,不受元素插入顺序的影响。
• 示例代码:

  Set<String> sortedNames = new TreeSet<>(Arrays.asList("David", "Alice", "Charlie", "Bob"));
  boolean containsBob = sortedNames.contains("Bob"); // 效率 O(log n)

性能对比总结与选择建议

如何验证？一个简单的基准测试

我们可以用 JMH (Java Microbenchmark Harness) 来进行一个简单的性能对比。

import org.openjdk.jmh.annotations.*;
import java.util.*;
import java.util.concurrent.TimeUnit;
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
public class ContainsPerformance {
    private List<String> arrayList;
    private List<String> linkedList;
    private Set<String> hashSet;
    private Set<String> treeSet;
    private int size = 10000;
    private String searchItem = "item_9999"; // 存在于集合中
    private String nonExistentItem = "item_999999"; // 不存在于集合中
    @Setup
    public void setup() {
        // 初始化集合
        arrayList = new ArrayList<>(size);
        linkedList = new LinkedList<>(arrayList);
        hashSet = new HashSet<>(arrayList);
        treeSet = new TreeSet<>(arrayList);
        // 填充数据
        for (int i = 0; i < size; i++) {
            String item = "item_" + i;
            arrayList.add(item);
            linkedList.add(item);
            hashSet.add(item);
            treeSet.add(item);
        }
    }
    @Benchmark
    public boolean testArrayListContains() {
        return arrayList.contains(searchItem);
    }
    @Benchmark
    public boolean testLinkedListContains() {
        return linkedList.contains(searchItem);
    }
    @Benchmark
    public boolean testHashSetContains() {
        return hashSet.contains(searchItem);
    }
    @Benchmark
    public boolean testTreeSetContains() {
        return treeSet.contains(searchItem);
    }
    // 测试不存在的元素
    @Benchmark
    public boolean testHashSetContainsNonExistent() {
        return hashSet.contains(nonExistentItem);
    }
}

预期结果分析:

• testArrayListContains 和 testLinkedListContains 的耗时会是微秒级别，并且会随着 size 增加而线性增长。
• testHashSetContains 和 testTreeSetContains 的耗时会是纳秒级别。
• testHashSetContains 的耗时将远低于 testTreeSetContains。
• testHashSetContainsNonExistent 的耗时会和 testHashSetContains 差不多，因为哈希查找的成本主要在于定位桶，而不在于 equals() 的调用次数。

1. 没有银弹: contains() 的效率完全取决于你选择的集合实现。
2. HashSet 是王者: 如果你需要频繁地、快速地判断一个元素是否存在，并且不关心元素的顺序，HashSet 是不二之选，其基于哈希表的 contains() 方法提供了近乎常数时间的平均性能。
3. TreeSet 是平衡者: 如果你需要在保证元素有序的前提下进行高效的查找，TreeSet 是最佳选择，其 O(log n) 的性能非常可靠。
4. 避免在 List 中频繁使用 contains(): 除非数据量非常小，否则尽量避免在 ArrayList 或 LinkedList 中频繁调用 contains()，因为它会导致 O(n) 的性能开销，在数据量大时会成为性能瓶颈。
5. 牢记 equals() 和 hashCode() 协约: 当你使用自定义对象作为 HashSet 或 HashMap 的键时，必须正确实现这两个方法，否则 contains() 可能会返回错误的结果或性能急剧下降。