[Leetcode]706. Design HashMap

Design HashMap - LeetCode

Design HashMap - LeetCode

해쉬맵을 디자인 하는 방법은 총 2가지 방법이 있다.

• 개별 체이닝 - 충돌 발생시 연결리스트로 연결
• 오픈 어드레싱 - 충돌발생시 테이블 공간내 빈공간을 찾아 해결

아래 풀이는 개별체이닝을 이용해 해결한 방법이다.

import collections

class ListNode(object):
    def __init__(self,key = None,value=None):
        self.value = value
        self.key = key
        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
        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