파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다.
해시맵 디자인
다음의 기능을 제공하는 해시맵을 디자인하라.
- put(key, value): 키, 값을 해시맵에 삽입한다. 이미 존재하는 키라면 업데이트 한다.
- get(key): 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.
- remove(key): 키에 해당하는 키, 값을 해시맵에서 삭제한다.
개별 체이닝 방식을 이용한 해시 테이블 구현
파이썬 알고리즘 인터뷰
개별 체이닝은 충돌 발생 시 연결 리스트로 연결하는 방식이다. 위 그림과 같이 ‘윤아’와 ‘서현’이 충돌이 발생하여 연결 리스트로 연결되는 모습이다. 일반적인 해시 테이블은 개별 체이닝 방식으로 구성되어 있다.
개별 체이닝 방식의 해시 테이블의 동작은 다음과 같다.
- 키의 해시 값을 계산한다.
- 해시 값을 이용한 배열의 인덱스를 구한다.
- 같은 인덱스가 있으면 연결 리스트로 연결한다.
1
2
3
4
5
class ListNode:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.next = None
해시맵의 클래스에서 사용할 노드 객체는 위와 같다. key값, value값, 중복 되었을 때 연결해줄 next로 구성되어 있다.
해시맵에서 구현할 메소드는 __init__, put, get, remove이다.
클래스 초기화
1
2
3
def __init__(self):
self.size = 1000
self.table = collections.defaultdict(ListNode)
해시맵의 기본 사이즈를 1000으로 지정한다. 해시 테이블은 ListNode를 가지는 딕셔너리로 만든다.
put
1
2
3
4
5
6
class MyHashMap:
...
# 삽입
def put(self, key: int, value: int):
index = key % self.size
...
해시 테이블의 기본적인 해싱 방식을 사용한다. 모듈로 연산을 한 나머지를 해시값으로 정하는 방법이다. 해싱 결과는 해시 테이블의 인덱스가 된다.
1
2
3
4
5
6
7
8
9
10
11
class MyHashMap:
...
# 삽입
def put(self, key: int, value: int):
...
""" 인덱스에 노드가 없으면 삽입 후 종료 """
if self.table[index].value is None:
self.table[index] = ListNode(key, value)
return
추가하려는 인덱스에 아무것도 없으면 바로 키와 값을 삽입하고 종료하게 된다. 조건문에서 table[index].value로 비교하는 이유는 defaultdict는 값이 존재하지 않으면 바로 디폴트 객체를 생성해 빈 ListNode를 만들어 내기 때문이다. 값이 아닌 노드 객체로 비교하게 되면 조건문이 True를 반환하지 못하게 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyHashMap:
...
# 삽입
def put(self, key: int, value: int):
...
""" 인덱스에 노드가 존재하는 경우 연결 리스트 처리 """
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)
인덱스에 노드가 존재하는 경우 해시 충돌이 발생한다. 개별 체이닝 방식에서는 해시 충돌이 발생할 경우 연결 리스트로 만든다.
p는 인덱스의 첫 번째 값이며 계속 p.next를 탐색하게 된다. 종료 조건은 키가 이미 존재할 경우 값을 업데이트 하고, p.next가 None인 경우 종료한다.
get
1
2
3
4
5
6
7
class MyHashMap:
...
# 조회
def get(self, key: int):
index = key % self.size
if self.table[index].value is None:
return -1
해시 테이블에 키 값으로 조회하는 동작이다. 모듈로 연산으로 인덱스를 결정하고, 해당 인덱스에 아무것도 없으면 -1을 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
class MyHashMap:
...
# 조회
def get(self, key: int):
...
# 노드가 존재할 때 일치하는 키 검색
p = self.table[index]
while p:
if p.key == key:
return p.value
p = p.next
return -1
노드가 존재하는 경우 일치하는 키를 검색하는 과정이다. 노드가 존재한다면 하나 이상의 노드가 존재하므로 p.next로 탐색하며 일치하는 키를 찾는다. 키를 찾지 못한다면 -1을 반환한다.
remove
1
2
3
4
5
6
7
8
9
10
11
12
13
class MyHashMap:
...
# 삭제
def remove(self, key: int):
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
인덱스를 구한 다음 아무것도 없으면, 잘못된 키를 삭제 시도한 경우이므로 리턴한다. 값이 있는 경우 인덱스의 첫 번째 노드 p의 키 값이 삭제할 키 값과 같은 경우 p.next를 확인한 후 존재하지 않으면 빈 ListNode를, 존재하면 인덱스의 첫 번째 노드를 p.next로 저장한다.
1
2
3
4
5
6
7
8
9
10
11
12
class MyHashMap:
...
# 삭제
def remove(self, key: int):
...
# 연결 리스트 노드 삭제
prev = p
while p:
if p.key == key:
prev.next = p.next
return
prev, p = p, p.next
연결 리스트를 삭제하는 경우는 p.next로 탐색하다가 일치하는 노드를 찾으면 이전 노드와 다음 노드를 연결하고 현재 노드의 연결 관계를 끊는다.