不使用任何內建 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
TIP
核心思路：使用 Bucket + Linked List（Chaining）處理碰撞，或在值域有限時直接用 Boolean 陣列。
- 最簡單的做法是用大小 10^6+1 的布林陣列，但浪費空間
- 更通用的做法是用 Hash Function + Chaining（鏈結串列處理碰撞）
Approaches
1. Boolean Array (direct mapping) — O(1) / O(10^6)
- Idea: 建立大小為 10^6+1 的布林陣列，直接以 key 為索引
- Time: 所有操作
O(1) - Space:
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 — Avg O(1), Worst O(n/k) / O(n+k)
- Idea: 用固定大小的 bucket 陣列，每個 bucket 是一個 LinkedList。用取模作為 Hash Function，碰撞時在同一 bucket 的鏈結串列中查找。
- Time: 平均
O(1)，最壞O(n/k)（k 為 bucket 數） - Space:
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)]
}
}Note: 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 + 碰撞處理
- Key trick: Chaining（鏈結串列）是最常見的碰撞處理方式；bucket 數量選質數可以減少碰撞；面試中展示 Chaining 比直接陣列映射更能體現資料結構設計能力