題目說明

設計一個 hashMap 資料結構，並且不仰賴程式碼原生的 object or dict

解題思路

從 constraints 的範圍可以大致推估需要的 array size 要多大
最簡單的方式可以用一個相同大小的 array 來放置內容

或是宣告一個較小的 array ，每個元素都是一個 ListNode ，這樣的做法會提高 put, get, delete 的 TC 但是節省了 SC
底下的程式碼就是用這個方式做的
這個做法會多一個 function 用來計算 key 的 hash 值為何，這邊使用的 hash function 為直接將 key 除 size 的餘數
當遇到 hash key 碰撞的時候，就將值塞在當前 ListNode 的 next

程式碼

TC: O(N)
SC: O(logN)

class ListNode:
    def __init__(self, key, value):
        self.pair = (key, value)
        self.next = None

class MyHashMap:

    def __init__(self):
        self.size = 1000
        self.hash_array = [None] * self.size
    
    def hash(self, key: int) -> int:
        return key % self.size
        
    def put(self, key: int, value: int) -> None:
        index = self.hash(key)

        if not self.hash_array[index]:
            self.hash_array[index] = ListNode(key, value)
        else:
            curr = self.hash_array[index]
            while True:
                if curr.pair[0] == key:
                    curr.pair = (key, value) #update
                    return
                if not curr.next:
                    break
                curr = curr.next
            curr.next = ListNode(key, value)
            
        

    def get(self, key: int) -> int:
        index = self.hash(key)

        if not self.hash_array[index]:
            return -1
        curr = self.hash_array[index]
        while curr:
            if curr.pair[0] == key:
                return curr.pair[1]
            curr = curr.next
        return -1
        

    def remove(self, key: int) -> None:
        index = self.hash(key)

        if not self.hash_array[index]:
            return
        prev = curr = self.hash_array[index] #shallow copy
        if curr.pair[0] == key:
            self.hash_array[index] = curr.next
            return
        else:
            curr = curr.next
            while curr:
                if curr.pair[0] == key:
                    prev.next = curr.next
                    return
                else:
                    prev, curr = curr, curr.next

其他討論

在 SC 的部分以及 hash function的建立，還有很多方式可以操作

參考資料

1. douzigege(2018-10-25)。
   Hash with Chaining [Python]。摘自 Leetcode Discussion (2023-01-09)