解題說明
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)?