在Java开发中，比较两个列表的元素差异是常见需求，比如判断两个列表是否有相同元素、找出两个列表的交集或差集。传统的嵌套循环实现方式在数据量较大时性能较差，而利用HashSet的特性可以将时间复杂度从O(N²)优化到O(N)。
传统嵌套循环的实现方式
最直观的列表比较方式是使用两层for循环，遍历第一个列表的每个元素，再遍历第二个列表检查是否存在相同元素。这种方式的时间复杂度是O(N²)，当列表长度分别为M和N时，总操作次数是M*N。
以下是嵌套循环比较两个列表是否有相同元素的示例代码：
import java.util.ArrayList;
import java.util.List;
public class ListCompareDemo {
public static boolean hasSameElementByLoop(List<String> list1, List<String> list2) {
// 遍历第一个列表的每个元素
for (String item1 : list1) {
// 遍历第二个列表检查是否存在相同元素
for (String item2 : list2) {
if (item1.equals(item2)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("a");
list1.add("b");
list1.add("c");
List<String> list2 = new ArrayList<>();
list2.add("d");
list2.add("b");
list2.add("e");
System.out.println("嵌套循环比较结果：" + hasSameElementByLoop(list1, list2));
}
}
HashSet优化的实现原理
HashSet底层是基于哈希表实现的，它的contains方法的时间复杂度是O(1)，也就是无论集合中有多少元素，判断某个元素是否存在的时间基本是固定的。我们可以把其中一个列表转换成HashSet，再遍历另一个列表的元素到HashSet中查询，这样总操作次数就是两个列表的长度之和，时间复杂度降为O(N)。
需要注意的前提是列表中的元素必须正确实现了hashCode和equals方法，否则HashSet无法正确判断元素是否相等。如果是自定义对象，需要重写这两个方法。
HashSet优化的实现代码
以下是用HashSet优化后的列表比较代码，同样实现判断两个列表是否有相同元素的功能：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ListCompareDemo {
public static boolean hasSameElementByHashSet(List<String> list1, List<String> list2) {
// 将第二个列表转换为HashSet，时间复杂度O(N)
Set<String> set = new HashSet<>(list2);
// 遍历第一个列表，到HashSet中查询，时间复杂度O(M)
for (String item1 : list1) {
if (set.contains(item1)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("a");
list1.add("b");
list1.add("c");
List<String> list2 = new ArrayList<>();
list2.add("d");
list2.add("b");
list2.add("e");
System.out.println("HashSet优化比较结果：" + hasSameElementByHashSet(list1, list2));
}
}
两种方式的性能对比
我们可以通过一个简单的测试对比两种方式的性能差异，假设两个列表的长度都是10000：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class PerformanceTest {
// 嵌套循环实现
public static boolean hasSameElementByLoop(List<String> list1, List<String> list2) {
for (String item1 : list1) {
for (String item2 : list2) {
if (item1.equals(item2)) {
return true;
}
}
}
return false;
}
// HashSet优化实现
public static boolean hasSameElementByHashSet(List<String> list1, List<String> list2) {
Set<String> set = new HashSet<>(list2);
for (String item1 : list1) {
if (set.contains(item1)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
// 初始化两个长度为10000的列表
List<String> list1 = new ArrayList<>();
List<String> list2 = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
list1.add("item_" + i);
list2.add("item_" + (i + 5000));
}
// 测试嵌套循环性能
long start1 = System.currentTimeMillis();
hasSameElementByLoop(list1, list2);
long end1 = System.currentTimeMillis();
System.out.println("嵌套循环耗时：" + (end1 - start1) + "毫秒");
// 测试HashSet优化性能
long start2 = System.currentTimeMillis();
hasSameElementByHashSet(list1, list2);
long end2 = System.currentTimeMillis();
System.out.println("HashSet优化耗时：" + (end2 - start2) + "毫秒");
}
}
实际运行后可以看到，嵌套循环的耗时通常是HashSet优化实现的几十甚至上百倍，数据量越大差距越明显。
适用场景说明
HashSet优化方案适合以下场景：
- 需要比较两个列表的元素差异，且列表数据量较大
- 列表中的元素没有重复值，或者重复值不影响比较逻辑
- 列表中的元素正确实现了
hashCode和equals方法
如果列表数据量很小，比如长度不超过100，两种方式性能差异可以忽略，选择嵌套循环的可读性更好。如果列表中有大量重复元素，且需要保留重复元素的比较逻辑，那么需要先处理重复值再使用HashSet优化，或者选择其他方案。