這篇文章會用 TDD 手刻 myDistinct 和 myDistinctBy，搞懂 HashSet 在去除重複裡扮演的角色，順便複習 hashCode 和 equals 的配合

Kotlin ↔ C# 對照表

集合運算篇的共同底牌：HashSet

從這篇開始進入第七部分，兩篇處理的都是「重複」和「成員關係」。前面 20 篇手刻的函式，容器幾乎清一色是 ArrayList 或 LinkedHashMap，這部分換成 HashSet 當主角

去除重複問的是「這個元素我是不是看過了」，集合運算問的是「這個元素在不在另一邊」，兩個都是成員查詢。用 List 查是 O(n)，套進迴圈就變 O(n²)，換成 HashSet 才降得下來

day 09 的 myContains 其實碰過一次，只是那裡的做法是「有 Collection 的實作就委派過去，讓 HashSet 拿自己的 O(1)」。這篇要自己動手把 HashSet 用起來，代價是正確性整個押在 hashCode 和 equals 上

TDD 實作 myDistinct

Red：先寫測試

@Test
fun `distinct integers`() {
    val numbers = listOf(1, 2, 3, 2, 1, 4, 3)
    val result = numbers.myDistinct()
    assertEquals(listOf(1, 2, 3, 4), result)
}

@Test
fun `distinct preserves first occurrence order`() {
    val numbers = listOf(3, 1, 2, 1, 3)
    val result = numbers.myDistinct()
    assertEquals(listOf(3, 1, 2), result)
}

@Test
fun `distinct empty list`() {
    val empty = emptyList<Int>()
    val result = empty.myDistinct()
    assertEquals(emptyList<Int>(), result)
}

@Test
fun `distinct handles null elements`() {
    val numbers = listOf(1, null, 1, null, 2)
    val result = numbers.myDistinct()
    assertEquals(listOf(1, null, 2), result)
}

第二個測試驗證順序：distinct 保留每個值第一次出現的位置。3 先出現，所以 3 在結果裡排第一

最後一個測試是 null 行為：HashSet 允許放一個 null，所以 null 也會被當成一個值處理，重複的 null 只留第一個

Green：最小實作

fun <T> Iterable<T>.myDistinct(): List<T> {
    val seen = HashSet<T>()
    val result = ArrayList<T>()
    for (element in this) {
        if (seen.add(element)) {
            result.add(element)
        }
    }
    return result
}

HashSet.add() 回傳 boolean：如果元素原本不在 Set 裡就加進去回傳 true，已經在了就回傳 false。利用這個回傳值，一行搞定「是否見過」的判斷和記錄

這個寫法比先 contains() 再 add() 好，省一次查詢

為什麼用 HashSet 而不是 LinkedHashSet？因為我們不需要 Set 保留插入順序(順序靠 result 的 ArrayList 維護)，HashSet 的 overhead 比 LinkedHashSet 小一點

Refactor：往 stdlib 的寫法靠近

我們的版本已經很直白，一個 Set 追蹤看過的元素，一個 List 收集第一次出現的元素。stdlib 其實有更精簡的寫法，把這兩件事交給 LinkedHashSet 一次做完，這裡先留個伏筆，本篇後面的「與 stdlib 原始碼比較」會拿出來對照

從複雜度角度看為什麼用 hash 而不用 sort 去除重複

HashSet 在 hash 分布良好時是 O(1) 查詢，遍歷一次集合就完成去除重複，總體 O(n)。Sort 去除重複則要先 O(n log n) 排序，還會破壞原順序

實務上 99% 的 distinct 都是用 hash，除非元素無法 hash(沒有合理的 hashCode)，或記憶體極度吃緊到 O(n) 額外空間都不能接受

C# Distinct()、Java 8 Stream.distinct()、Kotlin distinct() 都用 hash，選擇是一致的

TDD 實作 myDistinctBy

Red：先寫測試

@Test
fun `distinctBy department`() {
    val result = employees.myDistinctBy { it.department }
    assertEquals(3, result.size)
    assertEquals("Alice", result[0].name)     // first Engineering
    assertEquals("Charlie", result[1].name)    // first Marketing
    assertEquals("Eve", result[2].name)        // first HR
}

@Test
fun `distinctBy string length`() {
    val words = listOf("apple", "fig", "banana", "kiwi", "pear")
    val result = words.myDistinctBy { it.length }
    assertEquals(listOf("apple", "fig", "banana", "kiwi"), result)
}

@Test
fun `distinctBy modulo`() {
    val numbers = listOf(1, 2, 3, 4, 5, 6)
    val result = numbers.myDistinctBy { it % 3 }
    assertEquals(listOf(1, 2, 3), result)
}

@Test
fun `distinctBy empty list`() {
    val empty = emptyList<String>()
    val result = empty.myDistinctBy { it.length }
    assertEquals(emptyList<String>(), result)
}

@Test
fun `distinctBy handles null key`() {
    val words = listOf("apple", "", "banana", "")
    // selector 對空字串回傳 null，當成一個 key 來去除重複
    val result = words.myDistinctBy { it.ifEmpty { null } }
    assertEquals(listOf("apple", "", "banana"), result)
}

distinctBy { it.department } 把每個部門只留第一個人。Alice 是第一個 Engineering，Charlie 是第一個 Marketing，Eve 是第一個 HR

字串長度的測試，key 是字串長度。apple(5)、fig(3)、banana(6)、kiwi(4) 長度各不相同，全部留下。輪到 pear(4) 時，長度 4 已經被 kiwi 佔走，kiwi 先出現，所以 pear 被丟掉

空集合直接回傳空集合。null key 的測試則確認 selector 回傳 null 時也能正常運作：null 被當成一個 key，重複的 null key 一樣會被去掉

Green：最小實作

inline fun <T, K> Iterable<T>.myDistinctBy(selector: (T) -> K): List<T> {
    val seen = HashSet<K>()
    val result = ArrayList<T>()
    for (element in this) {
        val key = selector(element)
        if (seen.add(key)) {
            result.add(element)
        }
    }
    return result
}

跟 myDistinct 幾乎一樣，差別在 HashSet 存的是 selector 的回傳值(K)而不是元素本身(T)。seen 追蹤的是 key，result 收集的是元素

其實 distinct() 等於 distinctBy { it }。key 就是元素本身的時候，兩者行為完全一樣

Refactor：往 stdlib 的寫法靠近

myDistinctBy 的結構已經和 stdlib 幾乎一模一樣，沒有多餘的步驟可以拿掉。唯一要加的是 inline，selector 是傳進來的 lambda，標上 inline 可以省掉每次呼叫產生的函式物件，我們在 Green 階段已經寫上去了。後面的「與 stdlib 原始碼比較」會看到 stdlib 也是這樣做

hashCode 和 equals 的角色

HashSet 靠 hashCode() 和 equals() 判斷兩個物件是否「相同」。如果這兩個方法沒有正確實作，去除重複就會出問題

// data class 自動產生 hashCode 和 equals
data class Employee(val id: Int, val name: String, val department: String, val salary: Int, val age: Int)

val a = Employee(1, "Alice", "Engineering", 85000, 30)
val b = Employee(1, "Alice", "Engineering", 85000, 30)
a == b           // true (data class 的 equals 比較所有主建構子屬性)
a.hashCode() == b.hashCode()  // true

data class 自動根據所有建構子屬性產生 equals 和 hashCode。兩個內容相同的 Employee 會被視為相等，distinct 會正確去除重複

如果 Employee 不是 data class 呢？

class Employee(val id: Int, val name: String)

val a = Employee(1, "Alice")
val b = Employee(1, "Alice")
a == b           // false！不同物件
a.hashCode() == b.hashCode()  // 幾乎一定 false

普通 class 的 equals 繼承自 Any，比較的是參考(reference)，不是內容。兩個「內容相同」的 Employee 被視為不同物件，distinct 去不掉。這是常見的陷阱

解法有兩個：改成 data class，或自己 override equals 和 hashCode。大部分情況用 data class 就好

與 stdlib 原始碼比較

原始碼位置：kotlin.collections 的 _Collections.kt

stdlib 的 distinct 底層呼叫 toMutableSet().toList()

public fun <T> Iterable<T>.distinct(): List<T> {
    return this.toMutableSet().toList()
}

toMutableSet() 回傳 LinkedHashSet，自動去除重複且保留插入順序。再 toList() 轉成 List。比我們的寫法簡潔，但效果一樣

distinctBy 跟我們幾乎完全一樣

public inline fun <T, K> Iterable<T>.distinctBy(selector: (T) -> K): List<T> {
    val set = HashSet<K>()
    val list = ArrayList<T>()
    for (e in this) {
        val key = selector(e)
        if (set.add(key))
            list.add(e)
    }
    return list
}

stdlib 用 set 和 list 當變數名，我們用 seen 和 result，只是命名風格不同

小結

去除重複的核心是 HashSet。distinct 存元素本身，distinctBy 存 selector 的結果。能不能正確去除重複取決於 hashCode 和 equals 的實作，data class 是最簡單的保證

下一篇是集合運算，union / intersect / subtract 加上 plus / minus。聯集、交集、差集，聽起來像離散數學，但底層還是 HashSet

參考資料

• Kotlin API：distinct
• Kotlin API：distinctBy
• Kotlin API：contains
• Kotlin API：toMutableSet
• Kotlin API：LinkedHashSet
• Kotlin API：Any.equals
• Kotlin API：Any.hashCode
• Kotlin 官方文件：Equality
• Kotlin stdlib 原始碼：_Collections.kt
• .NET API：Enumerable.Distinct
• .NET API：Enumerable.DistinctBy(.NET 6+)
• .NET API：IEquatable 介面

同步刊登於 Blog

圖片來源：AI 產生