705. Design HashSet

Easy

Description

不使用任何內建 Hash Table 函式庫，設計一個 HashSet。實作 add(key)、remove(key)、contains(key) 方法。值的範圍為 [0, 10^6]。

Example:

Input: [“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”] > [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output: [null, null, null, true, false, null, true, null, false]

Intuition#

核心思路：使用 Bucket + Linked List（Chaining）處理碰撞，或在值域有限時直接用 Boolean 陣列。

最簡單的做法是用大小 10^6+1 的布林陣列，但浪費空間
更通用的做法是用 Hash Function + Chaining（鏈結串列處理碰撞）

Approaches#

1: Boolean Array（直接映射）#

概念: 建立大小為 10^6+1 的布林陣列，直接以 key 為索引
時間複雜度: 所有操作 O(1)
空間複雜度: O(10^6) - 固定大小

class MyHashSet() {
    private val set = BooleanArray(1000001)

    fun add(key: Int) {
        set[key] = true
    }

    fun remove(key: Int) {
        set[key] = false
    }

    fun contains(key: Int): Boolean {
        return set[key]
    }
}

⭐2: Hash Function + Chaining#

概念: 用固定大小的 bucket 陣列，每個 bucket 是一個 LinkedList。用取模作為 Hash Function，碰撞時在同一 bucket 的鏈結串列中查找。
時間複雜度: 平均 O(1)，最壞 O(n/k)（k 為 bucket 數）
空間複雜度: O(n + k) - n 為元素數，k 為 bucket 數

class MyHashSet() {
    private val size = 1000
    private val buckets = Array(size) { mutableListOf<Int>() }

    private fun hash(key: Int): Int = key % size

    fun add(key: Int) {
        val bucket = buckets[hash(key)]
        if (key !in bucket) {
            bucket.add(key)
        }
    }

    fun remove(key: Int) {
        buckets[hash(key)].remove(key)
    }

    fun contains(key: Int): Boolean {
        return key in buckets[hash(key)]
    }
}

補充：BST Bucket

用 TreeSet（BST）代替 LinkedList 作為 bucket，可以將最壞情況從 O(n/k) 改善到 O(log(n/k))。

class MyHashSet() {
    private val size = 1000
    private val buckets = Array(size) { java.util.TreeSet<Int>() }

    private fun hash(key: Int): Int = key % size

    fun add(key: Int) {
        buckets[hash(key)].add(key)
    }

    fun remove(key: Int) {
        buckets[hash(key)].remove(key)
    }

    fun contains(key: Int): Boolean {
        return buckets[hash(key)].contains(key)
    }
}

🔑 Takeaways#

Pattern: Hash Table 的底層實作——Hash Function + 碰撞處理
關鍵技巧: Chaining（鏈結串列）是最常見的碰撞處理方式；bucket 數量選質數可以減少碰撞；面試中展示 Chaining 比直接陣列映射更能體現資料結構設計能力