706. Design HashMap

해시맵 디자인 하는 문제 (파이썬은 Dict가 해시맵으로 볼 수 있다.)

 

해시맵 이론들...

 

해시맵에서 충돌했을때 해결 방법은 개별체이닝과 오픈어드레싱 방법이 있다.

 

개별 체이닝 - LinkedList로 데이터를 이어나가는 방법(O(n)도 걸릴수 있다.)

오픈어드레싱 - 충돌이 났을때, 그 주변을 선형으로 탐색해 적절한 위치에다 넣는것, (모든 원소가 반드시 자신의 해쉬값과 일치한다는 보장이 없음)

 

파이썬은 오픈어드레싱을 사용하고 있다.

 

해시맵 로드팩터 - 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈것

파이썬의 로드팩터는 0.66이고, 자바는 0.75이다.

이 비율을 넘어가면 각 언어에서 해시 테이블 공간을 재할당 한한다.

 

import sys
from itertools import combinations
import collections
import heapq

input = sys.stdin.readline

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
        #collection.detauldict는 조회시에 존재하지않을 경우 에러를 발생시키지 않고, default 객체를 만들어준다.
        #default 객체가 ListNode
        self.table = collections.defaultdict(ListNode)
    def put(self, key:int, value:int)->None:
        # 해싱 함수
        index = key % self.size

        # value에 접근했는데, self.table[index]가 없을 경우에는 default객체가 만들어진다.
        # default 객체의 value가 None이라는 것은 결국 값이 없다는것과 같다.
        if self.table[index].value is None:
            #값이 없는것
            self.table[index] = ListNode(key, value)
            return
        # 값이 있다면, 개별체이닝을 통해서 끝값으로 가서 넣자
        head = self.table[index]

        while head:
            #같은 key일 경우 value update
            if head.key == key:
                head.value = value
                return
            if head.next is None:
                # 이 부분이 없으면 head가 None일때 빠져나가버리므로, 뒤에서 head.next에 뭘 넣을수가 없다.
                # 따라서 head.next를 검사해서 None이면 while문을 빠져나가도록 해야한다.
                break
            head = head.next
        head.next = ListNode(key, value)


    def get(self, key:int)->int:
        index = key % self.size

        #접근했고, default로 만들어져서 None이네..그럼 값이 없는것이야
        if self.table[index].value is None:
            return -1
        #돌면서 key를 찾아서 value를 보내자

        head = self.table[index]

        while head:
            if head.key == key:
                return head.value
            head = head.next
        return -1

    def remove(self, key:int)->None:
        index = key % self.size

        # 접근했고, default로 만들어져서 None이네..그럼 값이 없는것이야
        if self.table[index].value is None:
            return

        head = self.table[index]

        #첫번째 값일때 next가 None이면 ListNode를 넣고, 뒤에 값이 있으면 뒤에껄로 변경하자
        if head.key == key:
            self.table[index] = ListNode() if head.next is None else head.next
            return

        #첫번째 값이 아니면 prev와 head를 넣고 찾아야한다.

        prev = head
        while head:
            if head.key == key:
                prev.next = head.next
                return
            prev, head = head, head.next