[leetcode-706] Design HashMap

LeetCode-706

Design HashMap : Design a HashMap without using any built-in hash table libraries.

note : At most 104 calls will be made to put, get, and remove.

Answer

        :::python

class ListNode:
    def init(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None
class MyHashMap:
    def init(self):
        self.size = 10**4
        self.table = collections.defaultdict(ListNode)
    def put(self, key: int, value: int) -> None:
        index = key % self.size
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return
        p = self.table[index]
        while p:
            if p.key == key :
                p.value = value
                return
            if p.next is None:
                break
            p = p.next
        p.next = ListNode(key, value)
    def get(self, key: int) -> int:
        index = key % self.size
        if self.table[index].value is None:
            return -1
        p = self.table[index]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1
    def remove(self, key: int) -> None:
        index = key % self.size
        if self.table[index].value is None:
            return
        p = self.table[index]
        if p.key == key:
            self.table[index] = ListNode() if p.next is None else p.next 
            return
        prev = p
        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev, p = p, p.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)

Result : 234ms Memory: 20.6mb

문제 설명

해시맵(HashMap)을 구현하는 문제입니다. 해시맵의 put, get, remove 메소드를 구현해야 합니다.

해시맵은 키(Key)와 값(Value)을 저장하는 자료구조입니다. 키는 중복되지 않으며, 값은 중복될 수 있습니다. put 메소드는 키와 값을 저장하는 메소드입니다. get 메소드는 키에 해당하는 값을 반환하는 메소드입니다. 만약 해당하는 값을 찾을 수 없으면 -1을 반환합니다. remove 메소드는 키에 해당하는 값을 제거하는 메소드입니다.

각각의 메소드마다 시간 복잡도는 O(1) 이하이어야 합니다.

해결 방법

해시맵을 구현하는 가장 간단한 방법은 해시 테이블(Hash Table)을 이용하는 것입니다. 보통은 배열과 연결 리스트로 구현됩니다. 배열을 통해 키를 해시값으로 바꾸어 인덱스로 사용하고, 연결 리스트를 사용하여 값들을 저장합니다.

put 메소드는 키를 해시값으로 바꾸어 인덱스를 구하고, 해당 인덱스의 연결 리스트에서 키를 찾아 값을 저장하거나, 연결 리스트가 비어있을 경우 새로운 노드를 추가합니다.

get 메소드는 키를 해시값으로 바꾸어 인덱스를 구하고, 해당 인덱스의 연결 리스트에서 키를 찾아 값을 반환합니다. 만약 해당하는 값이 없으면 -1을 반환합니다.

remove 메소드는 키를 해시값으로 바꾸어 인덱스를 구하고, 해당 인덱스의 연결 리스트에서 키를 찾아 노드를 제거합니다.

해시맵에 사용하는 해시함수는 해시값이 충돌할 가능성이 있기 때문에 중복되는 해시값을 처리할 수 있는 방법이 필요합니다. 이 문제에서는 chaining 방식을 사용하여 연결 리스트를 사용하는 것으로 충돌을 처리합니다.

사용자 코드

사용자 코드는 정상적으로 동작합니다. 적절한 자료구조와 메소드를 이용하여 각각의 메소드마다 O(1) 이하의 시간 복잡도를 가지도록 구현되어 있습니다. 사용자 코드는 개선할 여지가 있지만, 제공된 조건에서는 문제를 해결할 수 있는 코드입니다.

따라서, 사용자 코드에 대한 평가는 정상적으로 동작한다고 할 수 있습니다.