# 哈希表 Hash Map (Leetcode 706. Design HashMap)

## 介紹

HashMap可以高效儲存和索引儲存的數值，通常使用 key , value 鍵值對配對，用戶儲存的時候使用 key + value 的組合儲存，查詢資料的時候直接使用 key 來尋找資料

## 哈希碰撞問題

哈希表示使用雜湊算法來處理 key 值的，所以會產生碰撞 (Collision)，為了解決這個問題，在發生碰撞的時候，使用 Linked List 來處理，如果有相同的數值，就把新的數值接在 Linked List 的後面，索引的時候，直接遍歷一遍 Linked List 即可

## 複雜度

Time Complexity: O(1)
Space Complexity: O(n)

有關於碰撞問題，因為實際使用中，碰撞問題鮮少發生，所以 Avg. Time complexity 會是 O(1)，此問題可以使用數學證明

## 代碼

### Mod + Array + Linked List

class ListNode:
    def __init__(self,key: int = -1, val: int = -1, next = None):
        self.key = key
        self.val = val
        self.next = next

class MyHashMap:
    def __init__(self):
        self.mod = 1000
        self.map = [ListNode() for i in range(self.mod)]

    def put(self, key: int, value: int) -> None:
        mod = key % self.mod
        cur = self.map[mod]
        while cur and cur.next:
            if cur.next.key == key:
                cur.next.val = value
                return
            cur = cur.next
        node = ListNode(key,value)       
        cur.next = node

    def get(self, key: int) -> int:
        mod = key % self.mod
        cur = self.map[mod].next
        while cur:
            if cur.key == key:
                return cur.val
            cur = cur.next
        return -1

    def remove(self, key: int) -> None:
        mod = key % self.mod
        cur = self.map[mod]
        while cur and cur.next:
            if cur.next.key == key:
                cur.next = cur.next.next
                return
            cur = cur.next

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)