解題說明
Design HashSet
題目描述：不使用任何內建的雜湊集合庫，設計一個 HashSet。需要支援 add、remove 和 contains 三個操作。值的範圍為 0 到 10^6。
解題思路：使用拉鏈法（Separate Chaining）實作。選擇一個質數大小的桶陣列（如 1009），每個桶是一個鏈結串列（用 list<int> 實現）：
- 雜湊函數：
key % bucketSize決定放入哪個桶。 - add：先檢查是否已存在，不存在則加入對應桶的串列。
- remove：在對應桶中搜尋並移除。
- contains：在對應桶中搜尋。
選用質數作為桶的大小可以減少雜湊衝突。
C++ 解法
複雜度分析
時間複雜度：平均 O(n/k) — n 為元素數量，k 為桶的數量。假設雜湊均勻分布，每個操作平均為 O(1)。
空間複雜度：O(k + n) — k 個桶加上 n 個元素。
虛擬碼
1. Create array of k linked lists (buckets) 2. hash(key) = key % k 3. add(key): a. bucket = buckets[hash(key)] b. If key not in bucket, append key 4. remove(key): a. bucket = buckets[hash(key)] b. Remove key from bucket if present 5. contains(key): a. bucket = buckets[hash(key)] b. Return whether key is in bucket
其他解法
直接定址法（布林陣列）：由於值域為 0 到 10^6，可以用一個大小為 10^6+1 的布林陣列。所有操作 O(1)，但空間複雜度為 O(10^6)，不適合值域很大的情況。
開放定址法：衝突時探測下一個空桶（線性探測或二次探測）。不需要鏈結串列，但刪除操作需要標記墓碑（lazy delete），實作較複雜。
延伸思考
- 如果值域不限於 0 到 10^6（可能有負數或非常大的值），設計需要做什麼調整？
- 如何實作動態擴容（rehashing）來維持 O(1) 的平均操作時間？
- 拉鏈法和開放定址法各自的優缺點是什麼？在什麼場景下選擇哪種？