Java 數組去重算法優化：從 O(n²) 到 O(n) 的最佳實踐與 HashSet 原理解析

問題背景：大數組去重性能瓶頸

面對 10 萬級甚至百萬級數組去重，雙重循環 O(n²) 算法將導致嚴重性能下降。本文對比三種方案，推薦基於 HashSet 的 O(n) 線性方案。

方案對比與代碼實現

1. 暴力雙重循環 O(n²) —— 不推薦

public static int[] distinctBruteForce(int[] arr) {
    int[] result = new int[arr.length];
    int idx = 0;
    for (int i = 0; i < arr.length; i++) {
        boolean exists = false;
        for (int j = 0; j < idx; j++) {
            if (arr[i] == result[j]) { exists = true; break; }
        }
        if (!exists) result[idx++] = arr[i];
    }
    return Arrays.copyOf(result, idx);
}

2. HashSet 去重 O(n) —— 標準推薦

public static int[] distinctHashSet(int[] arr) {
    Set set = new LinkedHashSet<>(); // 保留順序
    for (int num : arr) set.add(num);
    return set.stream().mapToInt(Integer::intValue).toArray();
}

3. 排序後相鄰比較 O(n log n) —— 內存受限場景

public static int[] distinctSort(int[] arr) {
    int[] copy = Arrays.copyOf(arr, arr.length);
    Arrays.sort(copy);
    int idx = 0;
    for (int i = 0; i < copy.length; i++) {
        if (i == 0 || copy[i] != copy[i-1]) {
            copy[idx++] = copy[i];
        }
    }
    return Arrays.copyOf(copy, idx);
}

HashSet 去重核心原理深度解析

// HashSet.add 內部委託 HashMap.put
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

// HashMap.putVal 關鍵判斷邏輯
Node e; 
if ((e = tab[i]) != null) {
    // 遍歷鏈表/紅黑樹
    for (int binCount = 0; ; ++binCount) {
        if (e.hash == hash && (e.key == k || k.equals(e.key))) {
            // 找到重複 key
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
        // ... 擴容/樹化邏輯
    }
}
// 新增節點
tab[i] = newNode(hash, key, value, null);

關鍵點：

1. hashCode() 定位桶位置（高位參與擾動運算）
2. equals() 精確比較解決哈希碰撞
3. 負載因子 0.75 觸發擴容，保持 O(1) 平均查找
4. JDK 8+ 鏈表長度 > 8 且數組長度 > 64 樹化為紅黑樹，最差 O(log n)

自定義對象去重：equals/hashCode 正確實現

public class Employee {
    private Long id;
    private String department;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Employee)) return false;
        Employee that = (Employee) o;
        return Objects.equals(id, that.id) && 
               Objects.equals(department, that.department);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id, department);
    }
}

常見錯誤：

• 僅重寫 equals 不重寫 hashCode → 進入 HashSet 仍視為不同元素
• hashCode 依賴可變字段 → 對象修改後無法在 Set/Map 中找到
• equals 未檢查 null/類型 → 拋 ClassCastException

性能測試數據（10000 隨機對象）

流式 API 一行式去重 (JDK 8+)

// 基本類型
int[] distinct = Arrays.stream(arr).distinct().toArray();

// 對象流（需正確 equals/hashCode）
List unique = employees.stream()
    .distinct()
    .collect(Collectors.toList());

// 按屬性去重（保留首次出現）
List byId = employees.stream()
    .collect(Collectors.collectingAndThen(
        Collectors.toCollection(() -> new TreeSet<>(Comparator.comparing(Employee::getId))),
        ArrayList::new
    ));