[파이썬 알고리즘 인터뷰][해시테이블] 해시맵 디자인

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

해시맵 구현

 

책에서 구현된 코드

# 생략

 

기억해야할 기법

• doubling시 고려할 점
  
  • 기존 배열을 살린 상태에서 복사하기
  • put을 진행하면서 load factor가 기준치를 넘으면 doubling을 하는데, 만약 doubling으로 copy를 put으로 진행하면서 load factor가 다시 기준치를 넘는다면?
• while로 다음 포인터 이동시 current = current.next를 자주 망각함

 

내가 구현한 코드

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

class MyHashMap:

    def __init__(self):
        self.size = 31
        self.table = [None] * self.size
        self.loadfactor = 0

    def doubling_table(self) -> None:
        if self.loadfactor > 0.5:
            old_size, self.size = self.size, self.size ** 2
            old_table, self.table = self.table, [None] * self.size
            self.loadfactor = 0

            for node in old_table:
                while node:
                    self.put(node.key, node.val)
                    node = node.next

    def put(self, key: int, value: int) -> None:
        idx = key % self.size
        crnt_node = self.table[idx]
        cnt = 1
        if not crnt_node:
            self.table[idx] = ListNode(key, value)
        else:
            if crnt_node.key == key:
                crnt_node.val = value
                return
            while crnt_node.next:
                if crnt_node.next.key == key:
                    crnt_node.next.val = value
                    return
                cnt += 1
                crnt_node = crnt_node.next
            crnt_node.next = ListNode(key, value)
            self.loadfactor = max(self.loadfactor, cnt / self.size)

        self.doubling_table()

    def get(self, key: int) -> int:
        idx = key % self.size
        crnt_node = self.table[idx]

        while crnt_node:
            if crnt_node.key == key:
                return crnt_node.val
            crnt_node = crnt_node.next
        return -1

    def remove(self, key: int) -> None:
        idx = key % self.size
        crnt_node = self.table[idx]

        if crnt_node and crnt_node.key == key:
            self.table[idx] = crnt_node.next
        elif crnt_node and crnt_node.next:
            while crnt_node.next:
                if crnt_node.next.key == key:
                    crnt_node.next = crnt_node.next.next
                    return
                crnt_node = crnt_node.next

• 책에서는 dict로 구현했는데, 배열+링크드 리스트로 구현해봄
• doubling이 실제로 잘 일어나고 정상 동작하는지 local에서 확인
• del로 old table을 삭제해줄 걸 그랬다