해시 테이블은 키-값 쌍을 빠르게 저장하고 조회할 수 있는 자료구조입니다. 이번 글에서는 파이썬의 내장 해시 테이블 라이브러리(예: dict)를 사용하지 않고 해시맵(HashMap)을 처음부터 직접 설계하는 방법을 알아보겠습니다.
구현해야 할 기능
우리가 만들 해시맵은 다음 세 가지 메서드를 제공해야 합니다.
- put(key, value) – 키에 해당하는 값을 해시맵에 삽입합니다. 이미 같은 키가 존재하면 값을 새로 갱신(update)합니다.
- get(key) – 지정한 키에 매핑된 값을 반환합니다. 해당 키가 존재하지 않으면 -1을 반환합니다.
- remove(key) – 해시맵에 해당 키의 매핑이 존재하면 그 매핑을 삭제합니다.
동작 예시
해시맵을 초기화한 후 아래 순서대로 메서드를 호출한다고 가정해 보겠습니다.
put(1, 1);put(2, 2);get(1);→ 1get(3);→ -1 (존재하지 않음)put(2, 1);(키 2의 값을 1로 갱신)get(2);→ 1remove(2);get(2);→ -1 (삭제됨)
즉, 출력 결과는 차례대로 1, -1, 1, -1이 됩니다.
해결 접근 방식
이 문제는 연결 리스트(Linked List) + 해싱(Hashing)을 조합한 체이닝(chaining) 기법으로 해결할 수 있습니다. 전체적인 설계 단계는 다음과 같습니다.
1단계: 노드(Node) 클래스 정의
key,val,next세 개의 필드를 가지는 노드 구조체를 만듭니다.next는 초기에 null(None)입니다.
2단계: 연결 리스트(LinkedList) 클래스 정의
- 생성자(__init__): 더미 헤드 역할을 하는
prehead노드(key = None, val = None)를 생성합니다. - search(key):
p := prehead.next부터 시작해 리스트를 순회하며,p.key == key인 노드를 찾으면 반환하고, 끝까지 없으면 None을 반환합니다. - add(key, val): 먼저
search(key)로 키를 찾습니다.- 노드가 존재하면
p.val = val로 값을 갱신합니다. - 없다면 새 노드를 생성해 리스트 맨 앞에 삽입합니다 (
prehead.next = node, node.next = 기존 prehead.next).
- 노드가 존재하면
- get(key):
search(key)결과가 있으면 해당 노드의 값을, 없으면 null을 반환합니다. - remove(key):
prev = prehead,cur = prev.next로 두 포인터를 유지하며 순회합니다.cur.key == key면 반복을 중단합니다.- 그렇지 않으면
prev, cur = cur, cur.next로 한 칸씩 이동합니다. cur가 존재하면prev.next = cur.next로 노드를 연결 리스트에서 제거합니다.
- serialize(): 리스트 전체를 순회하며
[key, val]쌍들을 배열에 담아 반환합니다. 디버깅용으로 유용합니다.
3단계: 커스텀 해시맵(MyHashMap) 정의
- 생성자: 버킷 크기를
size = 1033(소수)으로 설정하고, 길이가 size와 같은 LinkedList 객체 배열arr을 만듭니다. - _hash(key):
return key % self.size– 키를 버킷 인덱스로 변환하는 해시 함수입니다. - put(key, value):
h = _hash(key)를 계산한 뒤arr[h].add(key, value)를 호출합니다. - get(key):
h = _hash(key)후ret = arr[h].get(key)를 호출하고, 결과가 있으면 그 값을, 없으면 -1을 반환합니다. - remove(key):
h = _hash(key)후arr[h].remove(key)를 호출합니다.
전체 파이썬 구현 코드
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.prehead = Node(None, None)
def search(self, key):
p = self.prehead.next
while p:
if p.key == key:
return p
p = p.next
return None
def add(self, key, val):
p = self.search(key)
if p:
p.val = val
else:
node = Node(key, val)
self.prehead.next, node.next = node, self.prehead.next
def get(self, key):
p = self.search(key)
if p:
return p.val
else:
return None
def remove(self, key):
prev = self.prehead
cur = prev.next
while cur:
if cur.key == key:
break
prev, cur = cur, cur.next
if cur:
prev.next = cur.next
def serialize(self):
p = self.prehead.next
ret = []
while p:
ret.append([p.key, p.val])
p = p.next
return ret
class MyHashMap:
def __init__(self):
self.size = 1033
self.arr = [LinkedList() for _ in range(self.size)]
def _hash(self, key):
return key % self.size
def put(self, key, value):
h = self._hash(key)
self.arr[h].add(key, value)
def get(self, key):
h = self._hash(key)
ret = self.arr[h].get(key)
if ret is not None:
return ret
else:
return -1
def remove(self, key):
h = self._hash(key)
self.arr[h].remove(key)
ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))입력 예시
ob = MyHashMap() ob.put(1, 1) ob.put(2, 2) print(ob.get(1)) print(ob.get(3)) ob.put(2, 1) print(ob.get(2)) ob.remove(2) print(ob.get(2))
출력 결과
1 -1 1 -1
정리 및 시간 복잡도
이 구현은 분리 연결법(Separate Chaining)을 활용한 대표적인 해시맵 구조입니다. 버킷 수를 소수인 1033으로 설정하면 키가 버킷에 고르게 분포되어 충돌(collisions)을 줄일 수 있습니다.
- 평균 시간 복잡도: put / get / remove 모두 O(1)
- 최악의 경우: 모든 키가 하나의 버킷에 몰릴 때 O(n)
실무에서는 파이썬의 dict를 사용하는 것이 가장 효율적이지만, 해시 테이블의 내부 동작 원리를 이해하는 데 이런 직접 구현 경험이 큰 도움이 됩니다. 면코딩 테스트나 자료구조 학습에서도 자주 등장하는 주제이니 꼭 직접 코드를 타이핑해 보며 익혀보시길 추천합니다.