706. Design HashMap

Easy

Description

不使用任何內建 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#

核心思路：與 LC 705 Design HashSet 類似，但每個節點需要存 key-value pair。使用 Hash Function + Chaining。

和 HashSet 的差別在於需要存儲 value，且 put 時如果 key 已存在要更新 value
碰撞處理同樣使用 Chaining

Approaches#

1: Array 直接映射#

概念: 用大小 10^6+1 的陣列，以 key 為索引直接存取 value
時間複雜度: 所有操作 O(1)
空間複雜度: 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#

概念: 用 bucket 陣列 + 鏈結串列存 key-value pair，取模作為 hash function
時間複雜度: 平均 O(1)，最壞 O(n/k)
空間複雜度: 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 }
    }
}

補充：使用 LinkedHashMap 概念的節點實作

更接近真實 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 設計題，考驗對底層實作的理解
關鍵技巧: 與 HashSet 的差別在於需要處理 key-value pair 和 value 更新；put 時需要先搜尋 key 是否已存在；remove 在鏈結串列中使用 dummy head 可以簡化邊界處理