Java中Set与List性能对比及两段循环代码的最优性判定

Great question—let’s break this down into two clear parts to make it easy to understand.

The key performance gaps between Set and List boil down to their underlying data structures and design goals:

• 底层数据结构与核心操作效率

  • List（典型实现：ArrayList/LinkedList）：
    • ArrayList基于动态数组，add()（尾部插入）是分摊O(1)，但contains()、remove(Object)需要全量遍历元素，时间复杂度为O(n)；随机访问（get(index)）是O(1)。
    • LinkedList基于双向链表，add()（尾部插入）是O(1)，但contains()、remove(Object)和随机访问都是O(n)。
  • Set（典型实现：HashSet/TreeSet）：
    • HashSet基于哈希表（封装HashMap），add()、contains()、remove()的平均时间复杂度为O(1)，最坏情况O(n)（哈希冲突极端严重时，概率极低）。
    • TreeSet基于红黑树，上述操作的时间复杂度为O(log n)，同时支持有序遍历。

• 场景化性能对比

  • 频繁做存在性检查（如去重、判断元素是否存在）：Set的性能碾压List，因为List的线性扫描会随数据量增大急剧变慢。
  • 需要随机访问元素：List（尤其是ArrayList）远优于Set，因为Set不支持按索引定位元素。
  • 需要有序存储/遍历：TreeSet（自然排序）或LinkedHashSet（保持插入顺序）可直接满足；ArrayList本身是插入有序的，但如果需要排序需额外调用Collections.sort()（O(n log n)时间）。

先明确代码场景：

List<Integer> l = new ArrayList(); 
Set<Integer> s = new HashSet();

// 循环1
for(Integer i: someArray) { 
    if(!l.contains(i)) l.add(i); 
}

// 循环2
for(Integer i : someArray) { 
    s.add(i); 
}

毫无疑问，循环2的性能远优于循环1，具体原因：

1. 时间复杂度的量级差异

   • 循环1：每次迭代都要执行l.contains(i)，而ArrayList的contains()是O(n)的线性扫描。假设输入数组长度为m，整个循环的时间复杂度是O(m²)——随着数组规模增大，开销会呈平方级增长，性能暴跌。
   • 循环2：HashSet的add()内部通过哈希值快速定位元素，平均时间复杂度是O(1)，整个循环的时间复杂度为O(m)，线性增长，效率极高。

2. 逻辑简洁性与可靠性

   • 循环1需要手动判断元素是否存在，而HashSet的add()本身就会自动忽略重复元素（返回false表示添加失败），不需要额外条件判断，代码更简洁，也减少了人为出错的可能。

3. 实际运行表现

   • 小数据量（几十上百个元素）时，两者差异可能不明显；但当数组规模达到数千甚至上万时，循环1的执行时间会是循环2的几倍甚至几十倍。即使数组存在大量重复元素，循环1依然要每次遍历整个List做检查，而循环2的哈希查找几乎不受重复元素影响。

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