一、集合去重的核心场景与需求

在分布式系统开发中，集合去重是高频出现的业务需求。典型场景包括：用户行为日志的唯一性过滤、订单ID的幂等性校验、缓存数据的去重存储等。以电商系统为例，用户浏览商品时产生的行为日志需要去重后存储，避免重复计算用户兴趣偏好。

从技术实现角度看，去重操作需满足两个核心要求：时间效率（处理百万级数据需毫秒级响应）和空间效率（避免内存溢出）。不同数据规模下的技术选型差异显著，例如：

小规模数据（<1000条）：优先选择代码简洁的实现方式
中等规模数据（1000-100万条）：需权衡时间复杂度与空间复杂度
大规模数据（>100万条）：必须采用分布式去重方案

二、基础去重方案实现与原理

1. HashSet去重法（O(1)时间复杂度）

List<String> list = Arrays.asList("a", "b", "a", "c");
Set<String> set = new HashSet<>(list);
List<String> result = new ArrayList<>(set);

原理：HashSet基于哈希表实现，通过hashCode()和equals()方法判断元素唯一性。当两个对象的hashCode相同且equals返回true时，视为重复元素。

优化点：

重写自定义对象的hashCode()和equals()方法
预先设置HashSet初始容量（new HashSet<>(expectedSize)）
避免在循环中频繁创建HashSet对象

2. Stream API去重（Java 8+）

List<String> result = list.stream()
    .distinct()
    .collect(Collectors.toList());

底层实现：distinct()操作内部维护一个临时Set，通过Spliterator遍历元素时进行去重。对于自定义对象，需确保正确实现hashCode()和equals()。

性能对比：

小数据量时与HashSet方案性能相当
大数据量时（>10万条）比HashSet慢约30%
代码可读性显著提升

三、进阶去重方案与工程实践

3. 基于TreeSet的自然排序去重

Set<String> set = new TreeSet<>(list);
List<String> result = new ArrayList<>(set);

适用场景：需要同时保证元素唯一性和排序顺序时。时间复杂度为O(n log n)，空间复杂度O(n)。

工程优化：

自定义比较器实现复杂排序逻辑
避免在高频调用路径中使用（如RPC接口）

4. 双重循环去重（O(n²)时间复杂度）

List<String> result = new ArrayList<>();
for (String item : list) {
    if (!result.contains(item)) {
        result.add(item);
    }
}

典型误区：仅适用于教学演示，实际工程中禁止使用。在10万条数据测试中，耗时比HashSet方案多2个数量级。

5. 分布式环境下的布隆过滤器

当数据规模超过单机内存容量时，可采用布隆过滤器实现分布式去重：

初始化：创建位数组和多个哈希函数
插入元素：计算哈希值并设置对应位为1
查询元素：检查所有哈希位是否均为1

优势：

空间效率极高（1.8%误判率时仅需9.6bits/元素）
查询时间恒定O(k)，k为哈希函数数量

工程案例：某推荐系统使用布隆过滤器过滤已展示商品，使缓存命中率提升40%。

四、自定义对象去重实战

1. 重写hashCode与equals

class User {
    private String id;
    private String name;
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(id, user.id);
    }
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

关键原则：

相等对象必须具有相同hashCode
hashCode计算应尽可能均匀分布
避免使用可变字段参与计算

2. 使用Comparator去重

List<User> distinctUsers = users.stream()
    .filter(distinctByKey(User::getId))
    .collect(Collectors.toList());
public static <T> Predicate<T> distinctByKey(Function<? super T, ?> keyExtractor) {
    Set<Object> seen = ConcurrentHashMap.newKeySet();
    return t -> seen.add(keyExtractor.apply(t));
}

适用场景：需要基于对象部分属性去重时。该方法利用ConcurrentHashMap的原子性保证线程安全。

五、性能测试与选型建议

在100万条字符串数据的测试中，不同方案耗时对比：
| 方案 | 耗时(ms) | 内存占用(MB) |
|——————————|—————|———————|
| HashSet | 12 | 45 |
| Stream.distinct() | 18 | 45 |
| TreeSet | 150 | 48 |
| 双重循环 | 12000 | 35 |
| 布隆过滤器(1%误判) | 8 | 1.2 |

选型矩阵：
| 数据规模 | 单机/分布式 | 是否需要排序 | 推荐方案 |
|——————|——————|——————|——————————|
| <1000条 | 单机 | 否 | Stream.distinct() |
| 1000-10万条| 单机 | 否 | HashSet |
| >10万条 | 单机 | 是 | TreeSet |
| >100万条 | 分布式 | 否 | 布隆过滤器 |

六、常见面试问题解析

Q1：HashSet如何保证元素唯一性？
A：通过两步校验：1) 比较hashCode是否相同 2) 相同则调用equals方法确认。因此必须同时重写这两个方法。

Q2：Stream.distinct()的并行流性能如何？
A：并行流在大数据量时（>10万条）可提升30%性能，但需注意线程安全问题。自定义对象去重时建议使用Collectors.toConcurrentMap()替代。

Q3：如何实现内存高效的去重？
A：对于基本类型，可使用BitSet（每个元素仅占1bit）；对于字符串，可先计算MD5哈希值再存储。某日志系统通过此方案减少75%内存占用。

掌握这些核心方案后，开发者不仅能轻松应对面试中的去重问题，更能在实际项目中根据业务场景选择最优实现。建议结合具体业务需求进行性能测试，建立适合团队的技术选型基准。

集合去重问题全解析：面试高频考点与工程实践