解題說明
Design HashMap
題目描述：不使用任何內建的雜湊表庫，設計一個 HashMap。需要支援 put（插入或更新）、get（查詢）和 remove（刪除）三個操作。鍵的範圍為 0 到 10^6。
解題思路：使用拉鏈法（Separate Chaining）實作，與 HashSet 類似，但每個桶存放的是 (key, value) 配對：
- 雜湊函數：
key % bucketSize決定桶的索引。 - put：在對應桶中搜尋 key，若已存在則更新 value，否則插入新的
(key, value)配對。 - get：在對應桶中搜尋 key，找到回傳 value，否則回傳 -1。
- remove：在對應桶中搜尋並移除 key 對應的配對。
C++ 解法
複雜度分析
時間複雜度：平均 O(n/k) — n 為元素數量，k 為桶的數量。假設雜湊均勻分布，每個操作平均為 O(1)。
空間複雜度：O(k + n) — k 個桶加上 n 個鍵值對。
虛擬碼
1. Create array of k linked lists (buckets), each storing (key, value) pairs 2. hash(key) = key % k 3. put(key, value): a. bucket = buckets[hash(key)] b. Search for key in bucket; if found, update value c. If not found, append (key, value) 4. get(key): a. Search for key in buckets[hash(key)] b. Return value if found, else -1 5. remove(key): a. Remove (key, *) from buckets[hash(key)]
其他解法
直接定址法（陣列）：用大小為 10^6+1 的陣列，每個位置存 value（用 -1 表示未使用）。所有操作 O(1)，空間 O(10^6)。簡單暴力但浪費空間。
開放定址法（線性探測）：衝突時往後探測。需要處理 lazy delete 和負載因子控制。實作較複雜但快取友好（cache-friendly），在低負載率下效能優於拉鏈法。
延伸思考
- 如果要支援動態擴容（當負載因子超過閾值時），該如何實作 rehash？
- 拉鏈法中的鏈結串列若改為平衡二元搜尋樹（如 Java 8 的 HashMap），有什麼好處？
- 如何設計一個執行緒安全的 HashMap（如 ConcurrentHashMap）？