Java List 去重的兩種實現方式與性能對比

場景

List 允許重複元素，去重常見需求。本文對比 HashSet 方案 與 雙層循環方案 的實現原理、代碼示例與時間複雜度。

方案一：利用 HashSet 去重（推薦）

核心原理

HashSet 底層基於 HashMap，add() 時通過 hashCode() 定位桶，再用 equals() 判斷是否重複。因此 元素類必須正確重寫 hashCode() 和 equals()。

代碼示例

class Student {
    private String id, name;
    // 構造器、getter/setter、toString 省略
    @Override public int hashCode() {
        int result = 1;
        result = 31 * result + (id == null ? 0 : id.hashCode());
        result = 31 * result + (name == null ? 0 : name.hashCode());
        return result;
    }
    @Override public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student other = (Student) obj;
        return Objects.equals(id, other.id) && Objects.equals(name, other.name);
    }
}

public static void removeListDuplicateObject() {
    List<Student> list = new ArrayList<>();
    for (int i = 0; i < 10; i++) list.add(new Student("id", "name")); // 10個相同對象
    System.out.println("去重前: " + list.size()); // 10

    Set<Student> set = new HashSet<>(list); // 一鍵去重
    System.out.println("去重後: " + set.size()); // 1
}

源碼追蹤

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

// HashMap.put 關鍵判斷
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    // 視為重複，覆蓋值，返回舊值
}

即：hashCode 相等 且 equals 為 true 視為同一元素。

時間複雜度

單次遍歷插入 Set，平均 O(n)。

方案二：雙層循環 + contains 去重（不推薦）

代碼示例

public static void removeListDuplicateObjectByList() {
    List<Student> list = ...; // 同上
    List<Student> listUniq = new ArrayList<>();
    for (Student s : list) {
        if (!listUniq.contains(s)) { // contains 內部遍歷 listUniq
            listUniq.add(s);
        }
    }
}

源碼分析

// ArrayList.contains -> indexOf
public boolean contains(Object o) { return indexOf(o) >= 0; }
public int indexOf(Object o) {
    for (int i = 0; i < size; i++)
        if (o.equals(elementData[i])) return i;
    return -1;
}

時間複雜度

外層 n 次，內層平均 n/2 次，總體 O(n²)。數據量大時性能急劇下降。

結論與建議

生產環境強烈建議使用 HashSet（或 LinkedHashSet 保持插入順序）。若元素為不可變類（String、Integer 等）無需額外操作；自定義類務必重寫 hashCode/equals。