不使用任何內建 Hash Table 函式庫，設計一個 HashMap。實作
put(key, value)、get(key)、remove(key)方法。key 和 value 範圍為[0, 10^6]。
Example:
Input: [“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”] > [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] Output: [null, null, null, 1, -1, null, 1, null, -1]
Intuition
TIP
核心思路：與 LC 705 Design HashSet 類似，但每個節點需要存 key-value pair。使用 Hash Function + Chaining。
- 和 HashSet 的差別在於需要存儲 value，且 put 時如果 key 已存在要更新 value
- 碰撞處理同樣使用 Chaining
Approaches
1. Array Direct Mapping — O(1) / O(10^6)
- Idea: 用大小 10^6+1 的陣列，以 key 為索引直接存取 value
- Time: 所有操作
O(1) - Space:
O(10^6)
class MyHashMap() {
private val map = IntArray(1000001) { -1 }
fun put(key: Int, value: Int) {
map[key] = value
}
fun get(key: Int): Int {
return map[key]
}
fun remove(key: Int) {
map[key] = -1
}
}⭐ 2. Hash Function + Chaining — Avg O(1), Worst O(n/k) / O(n+k)
- Idea: 用 bucket 陣列 + 鏈結串列存 key-value pair，取模作為 hash function
- Time: 平均
O(1)，最壞O(n/k) - Space:
O(n + k)
class MyHashMap() {
private val size = 1000
private val buckets = Array(size) { mutableListOf<IntArray>() }
private fun hash(key: Int): Int = key % size
fun put(key: Int, value: Int) {
val bucket = buckets[hash(key)]
for (pair in bucket) {
if (pair[0] == key) {
pair[1] = value
return
}
}
bucket.add(intArrayOf(key, value))
}
fun get(key: Int): Int {
val bucket = buckets[hash(key)]
for (pair in bucket) {
if (pair[0] == key) return pair[1]
}
return -1
}
fun remove(key: Int) {
val bucket = buckets[hash(key)]
bucket.removeAll { it[0] == key }
}
}Note: Node Impl (LinkedHashMap idea)
更接近真實 HashMap 實作，使用自訂的 ListNode。
class MyHashMap() {
private class ListNode(var key: Int, var value: Int, var next: ListNode? = null)
private val size = 1000
private val buckets = arrayOfNulls<ListNode>(size)
private fun hash(key: Int): Int = key % size
fun put(key: Int, value: Int) {
val idx = hash(key)
var node = buckets[idx]
// 搜尋是否已存在
while (node != null) {
if (node.key == key) {
node.value = value
return
}
node = node.next
}
// 頭插法
val newNode = ListNode(key, value, buckets[idx])
buckets[idx] = newNode
}
fun get(key: Int): Int {
var node = buckets[hash(key)]
while (node != null) {
if (node.key == key) return node.value
node = node.next
}
return -1
}
fun remove(key: Int) {
val idx = hash(key)
val dummy = ListNode(0, 0, buckets[idx])
var prev = dummy
while (prev.next != null) {
if (prev.next!!.key == key) {
prev.next = prev.next!!.next
break
}
prev = prev.next!!
}
buckets[idx] = dummy.next
}
}🔑 Takeaways
- Pattern: Hash Table 設計題，考驗對底層實作的理解
- Key trick: 與 HashSet 的差別在於需要處理 key-value pair 和 value 更新；put 時需要先搜尋 key 是否已存在；remove 在鏈結串列中使用 dummy head 可以簡化邊界處理