706. Design HashMap (Array, Hash Table, Linked List, Design, Hash Function)

링크 - https://leetcode.com/problems/design-hashmap/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Easy

Intuition

우리는 이 문제를 array와 그 각 원소에 LinkedList혹은 개별 클래스를 사용하여 문제를 풀 수 있다. 먼저 array의 길이를 정해야 하는데 hash map을 만들때 key space는 prime number로 만드므로 여기서는 2069를 사용하였다. 또한 앞에 숫자를 곱하면 hash key들을 분산시키는데 도움이 될 수 있다.

Code

class HashNode:

    def __init__(self, key, val, next=None):
        self.key = key
        self.val = val
        self.next = next


class MyHashMap:

    def __init__(self):
        self.arr_length = 2069
        self.mult = 12345678
        self.arr = [HashNode(-1, -1)] * self.arr_length

    def put(self, key: int, value: int) -> None:
        key_hash = self.hash(key)
        node = self.arr[key_hash]
        while node:
            if node.key == key:
                node.val = value
                return
            node = node.next

        new_node = HashNode(key, value)
        head = self.arr[key_hash]
        head_next = head.next
        head.next = new_node
        new_node.next = head_next


    def get(self, key: int) -> int:
        key_hash = self.hash(key)
        node = self.arr[key_hash]
        while node:
            if node.key == key:
                return node.val
            node = node.next

        return -1
        

    def remove(self, key: int) -> None:
        key_hash = self.hash(key)
        node = self.arr[key_hash]
        while node.next:
            if node.next.key == key:
                node.next = node.next.next
                return
            node = node.next

    
    def hash(self, key):
        return (key * self.mult) % self.arr_length
        


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

Complexity

Time Complexity: O(N/K)

Space Complexity: O(K + M)