LeetCode - 706. Design HashMap [Python]

https://leetcode.com/problems/design-hashmap/

Design HashMap - LeetCode

---

풀이 과정

built-in hash table libraries를 사용하여 HashMap을 구현하는 문제이다.

 

해시 테이블의 구현시, 서로 다른 값이 같은 해시값을 가지는 해시 충돌이 발생할 수 있다. 해시 충돌을 처리하는 방법은 크게 2가지가 있는데, 개별 체이닝(Separate Chaining) 방식과 오픈 어드레싱(Open Addressing) 방식이다.

1. 개별 체이닝

해시 값의 충돌이 발생하면 기존 해시 값에 배정되어 있는 노드의 뒤로 링크드 리스트 처럼 연결하는 방식이다.

 

2. 오픈 어드레싱

해시 값의 충돌이 발생하면 데이터가 저장되어 있지 않은 주소값을 찾아 해시 값 근처의 주소를 탐색해 배정하는 방식이다.

 

파이썬의 딕셔너리는 오픈 어드레싱 방식으로 구현되어 있다. 이 문제에서 HashMap을 구현할 때에는 개별 체이닝 방식을 사용하였다.

 

개별 체이닝시 노드의 연결을 위해 key, value, next 값을 갖는 노드를 설정해주었고, 해쉬 함수는 해쉬 맵 사이즈의 모듈러 연산을 사용하였다.

---

소스 코드

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 = 1000
        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
        node = self.table[index]
        while node:
            if node.key == key:
                node.value = value
                return
            if node.next is None:
                break
            node = node.next
        node.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.size
        if self.table[index].value is None:
            return -1
        node = self.table[index]
        while node:
            if node.key == key:
                return node.value
            node = node.next
        return -1

    def remove(self, key: int) -> None:
        index = key % self.size
        if self.table[index].value is None:
            return
        node = self.table[index]
        if node.key == key:
            self.table[index] = ListNode() if node.next is None else node.next
            return
        prev = node
        while node:
            if node.key == key:
                prev.next = node.next
                return
            prev, node = node, node.next