99클럽 코테 스터디 11일차 TIL

오늘의 문제

706. Design HashMap

---

문제 요약

• 직접 해시맵 구현하기 (내장 hashmap 라이브러리 사용X)
• key 범위: 0 <= key <= 10^6
• 최대 10^4번의 호출

---

풀이 전략

튜플 사용

• 고정 크기 버킷 배열 사용: self.map = [...]
• 충돌 해결 방식 → 각 버킷에 (key, value) 튜플을 리스트로 저장

class MyHashMap:

    def __init__(self):
        self.size = 10000 # 10^4 operation 대비? 
        self.map = [[] for _ in range(self.size)]

    def put(self, key: int, value: int) -> None:
        index = hash(key) % self.size
        for i , (k,v) in enumerate(self.map[index]):
            if k == key:
                self.map[index][i] = (key, value)
                return
        self.map[index].append((key, value))

    def get(self, key: int) -> int:
        index = hash(key) % self.size
        for i , (k,v) in enumerate(self.map[index]):
            if k == key: 
                return v
        return -1

    def remove(self, key: int) -> None:
        index = hash(key) % self.size
        self.map[index] = [(k,v) for (k,v) in self.map[index] if k != key]

LinkedList, Node 구현

• 배열 index당 LinkedList가 생성되는 구조 (Java의 Hashmap구조와 비슷..?)
• 단점: 구현해야하는 것이...조금 귀찮다

class MyHashMap:

    def __init__(self, size=10000):
        self.map = [LinkedList() for _ in range(size)]       

    def put(self, key: int, value: int) -> None:
        index = hash(key) % len(self.map)
        self.map[index].insert(key, value)        

    def get(self, key: int) -> int:
        index = hash(key) % len(self.map)
        ret = self.map[index].get(key)        
        if ret == None: 
            return -1
        else: 
            return ret

    def remove(self, key: int) -> None:
        index = hash(key) % len(self.map)
        self.map[index].remove(key)

class LinkedList:
    def __init__(self): 
        self.head = None 

    def insert(self, key, value): 
        node = self.head
        while node: 
            if node.key == key:
                node.value = value
                return 
            node = node.next
        new_node = Node(key, value, self.head)
        self.head = new_node

    def get(self, key): 
        node = self.head
        while node: 
            if node.key == key:
                return node.value 
            node = node.next 
        return None

    def remove(self, key): 
        prev = None
        node = self.head
        while node: 
            if node.key == key:
                if prev: 
                    prev.next = node.next
                else: 
                    self.head = node.next
                return 
            prev = node
            node = node.next 

class Node: 
    def __init__(self, key, value, next=None):
        self.key = key
        self.value = value
        self.next = next

---

Python: 배운 문법 & 구조

리스트 컴프리헨션

• [...] 바깥이 최종 리스트
• 안에 for문 돌면서 채우는 방식
• 조건 필터링도 가능

튜플

• (key, value) 형태
• (1,) ← 하나만 있을 땐 쉼표 필요
• 리스트 안에 튜플 넣어서 사용

remove() 구현 이유

• list.remove()는 전체 튜플을 알아야 동작함 → value 모르면 불가능
• 그래서 조건 필터링으로 새 리스트 생성하는 방식이 현실적

---

성능 관련 고찰

문제점:

• get() / put() / remove() 전부 충돌 시 리스트 선형 탐색 → O(n)
• 버킷 수가 작으면 충돌 많아서 느려짐

해결 전략:

• 버킷 수 늘리기: 10007, 20011 같은 소수 추천
• 튜플 대신 Node 클래스 쓸 수도 있지만, 느림
• Open Addressing 방식은 구현 복잡하지만 더 빠름 -> dict가 이런 방식으로 구현되어있다고 함