1. 정의
키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형을 구현한 자료구조이다.
가장 큰 특징은 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계없이 빠른 성능을 기대할 수 있다.
해시 테이블의 핵심은 해시 함수이다. 해시 함수는 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라 한다. 성능 좋은 해시 함수들의 특징은 아래와 같다.
- 해시 함수 값 충돌 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용해 해싱
- 해시 테이블 사용 효율이 높을 것
2. 충돌
해시 테이블에 충돌은 얼마나 많이 발생할까? 생각보다 쉽게 일어난다. 예시로 생일 문제를 들 수 있다.
위의 그림처럼 23명만 모여도 50%를 넘고, 57명이 모이면 99%를 넘어선다.
이처럼 해시 테이블의 충돌은 생각보다 쉽게 일어나므로 충돌을 최소화하는 일이 무엇보다 중요하다.
그렇다면 이런 충돌은 왜 일어날까? 비둘기집 원리가 이를 잘 설명하였다. 비둘기집 원리란, n개 아이템을 m개 컨테이너에 넣을 때, n>m이라면 적어도 하나의 컨테이너에 반드시 2개 이상의 아이템이 들어 있다는 원리를 말한다. 비둘기집 원리에 따라 9개 공간이 있는 곳에 10개의 아이템이 들어온다면 반드시 1번 이상의 충돌이 발생한다. 좋은 해시 함수면 충돌을 최소화하여 1번의 충돌이 일어나지만, 안 좋은 해시 함수의 경우 심할 때 9번 모두 충돌한다.
3. 로드 팩터
load Factor = n/k로드 팩터는 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다. 로드 팩터 비율에 따라 해시 함수를 재작성할지 아니면 해시 테이블 크기를 조정해야 할지 결정한다. 이 값은 해시 함수가 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용된다.
일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소하며, 자바 10의 경우 0.75를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당한다.
4. 해시 함수
위 그림은 해시 함수를 통해 키가 해시 값으로 변경되는 과정을 도식화했다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라고 한다. 해싱에는 다양한 알고리즘이 있고, 최상의 분포를 제공하는 방법은 데이터에 따라 다르다.
해싱 알고리즘을 일일이 말하는 것은 범위가 너무 넓기에 가장 단순하면서도 널리 쓰이는 정수형 해싱 기법인 모듈로 연상을 이용한 나눗셈 방식 하나를 살펴본다. 수식은 아래와 같다.
h(x) = x mod mh(x)는 입력값 x의 해시 함수를 통해 생성된 결과이다. m은 해시 테이블의 크기로 2의 멱수에 가깝지 않는 소수를 택하는 게 좋다. 매우 단순한 방법이지만 실무에서는 많은 키 세트가 충분히 랜덤한 상태이고, 키 세트가 큰 소수에 의해 순환 구조가 될 확률은 낮기에 실제로 잘 동작한다. x는 간단한 규칙을 통해 만든 랜덤한 키의 값이다.
조슈아 블로크는 여러 해시 함수 성능을 조사했고 31이란 숫자를 찾아냈다. 실제로 31은 메르센 소수로 수학적으로 나쁘지 않은 선택이다. 아래는 실제 자바 JDK에 포함된 해시 코드 중 일부이다.
hashCode = 31 * hashCode + (e == null ? 0: e.hashCode());
구글은 해시 함수를 딥러닝으로 학습한 모델을 적용해 충돌을 최소화한 논문을 발표했고, 해시 테이블 자료구조의 미래를 기대케 했다.
5. 충돌 해결
아무리 좋은 해시 함수라도 충돌은 발생하게 된다. 충돌이 일어날 때 어떤 식으로 처리해야 할까?
1) 개별 체이닝
연결 리스트로 연결하는 방식이다. 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 되므로 인기가 많다. 가장 전통적인 방식으로 흔히 해시 테이블이라고 하면 이 방식을 뜻한다.
구현 원리는 1) 키의 해시 값을 계산 2) 해시 값을 이용해 배열의 인덱스를 구한다. 3) 같은 인덱스가 있으면 연결 리스트로 연결.
잘 구현한 경우 O(1)이지만, 최악의 경우 O(n)이 된다. 자바 8에서는 연결 리스트 구조를 좀 더 최적화해서 데이터 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용한다. 참고로 레드-블랙 트리는 균형 이진 탐색 트리이다.
2) 오픈 어드레싱
충돌 발생 시 빈 공간을 찾아나서는 방식이다. 사실상 무한히 저장할 수 있는 체이닝 방식과 달리 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 발생하면 테이블 공간 내에 탐사를 통해 빈 공간을 찾아 해결한다. 이로 인해 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.
오픈 어드레싱 방식 중 가장 간단한 선형 탐사 방식은 충돌이 발생한 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 특정 위치가 선점되면 바로 그다음 위치를 확인하는 식이다. 이렇게 진행하다가 빈 공간을 발견하면 삽입한다. 선형 탐사 방식은 구현 방법이 간단하면서도, 전체적인 성능도 좋은 편이다.
선형 탐사의 문제점은 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다. 해시 테이블이 연속된 데이터 그룹 생기는 현상을 클러스터링이라 하는데, 클러스터들이 커지면 인근 클러스터들과 서로 합치는 일이 발생한다. 이러면 해시 테이블의 특정 위치에 데이터가 몰리게 되고, 다른 위치에서는 상대적으로 데이터가 거의 없는 상태가 될 수 있다. 이런 클러스터링 현상은 시간이 오래 걸리게 되며, 해싱 효율을 떨어트리는 원인이다.
오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없다. 따라서 로드 팩터 비율을 넘어서면 Growth Factor의 비율에 따라 더 큰 크기의 다른 버킷을 생성 후 여기에 새롭게 복사하는 리해싱 작업이 일어난다. 이는 동적 배열에서 공간이 찰 경우, 더블링으로 새롭게 복사해 옮기는 과정과 유사하다.
6. 파이썬에서의 해시 테이블
파이썬의 해시 테이블은 딕셔너리이다. 파이썬의 해시 테이블은 충돌 시 오픈 어드레싱 방식으로 구현되었다. 파이썬이 체이닝을 사용하지 않는 이유로 연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요하고, 추가 메모리 할당은 느린 작업이기 때문에 택하지 않았다고 한다.
위의 그림을 보듯이 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다. 그러나 슬롯의 80%가 넘어가면 급격한 성능 저하가 일어난다. 따라서 최근 루비나 파이썬 언어들은 오픈 어드레싱 방식을 택해 성능을 높이는 대신, 로드 팩터를 낮게 잡아 성능 저하 문제를 해결하였다. 파이썬의 로드 팩터는 0.66이며 루비는 0.5로 훨씬 적다.
각 언어별 해시 테이블의 구현 방식을 정리하면 다음과 같다.
- C++: 개별 체이닝
- 자바: 개별 체이닝
- 고(Go): 개별 체이닝
- 루비: 오픈 어드레싱
- 파이썬: 오픈 어드레싱
7. 파이썬 구현
HashMap의 put, get, remove 기능을 제공하는 해시맵을 파이썬으로 구현해보겠다.
충돌 완화 방식은 개별 체이닝 방식으로 구현해본다.
(1) 초기화
ListNode라는 이름의 클래스를 연결 리스트 객체로 구현하고, 기본 사이즈를 1000개로 설정하였다. 존재하지 않는 키를 조회할 경우 디폴트를 생성해주는 defaultdict를 사용했다.
(2) 삽입 메소드 put()
def put(self, key, value):
index = key % self.size편의상 모든 키를 정수형으로 지정했다. size 개수만큼 모듈로 연산 후 나머지를 해시값으로 정하는 단순한 형태로 처리했다. 모듈을 통한 해싱은 기본적인 방식이고, 해싱한 결과 index는 해시 테이블의 인덱스가 된다.
if self.table[index].value is None:
self.table[index] = ListNode(key,value)
return만약 해당 인덱스에 아무것도 없으면 키, 값을 삽입하고 바로 종료한다.
p = self. table[index]
while p:
if p.key == key:
p.value= value
return
if p.next is None:
break
p = p.next위 코드는 해당 인덱스에 노드가 존재하는 경우다. 해시 충돌이 발생한 경우, 개별 체이닝 방식으로 충돌을 해결한다. p는 인덱스의 첫 번째 값이며 p.next를 통해 계속 탐색. 종료 조건은 2가지이며, 첫 번째는 이미 키가 존재할 경우 값을 업데이트하고 빠져나가고, 두 번째는 p.next is None이면 루프를 빠져간다.
p.next = ListNode(key, value)루프를 다 돌리면 p.next에 새 노드가 생성되면서 연결된다. 기존에 존재하지 않은 키라면 맨 마지막에 새로운 노드가 연결된다.
(3) 조회 메서드 get()
def get(self, key):
index = key % slef.size
if self.table[index].value is None:
return -1모듈로 연산으로 인덱스를 결정하고 인덱스에 아무도 없으면 -1을 리턴한다.
p = self.table[index]
while p:
if p.key == key:
return p.value
p = p.next
return -1해싱 결과에 하나 이상의 노드가 존재하므로, p.next로 탐색하면서 일치하는 키를 찾는다. 찾으면 값을 리턴하고 찾지 못하면 루프를 빠져나와 -1을 리턴한다.
(4) 삭제 메서드 remove()
값이 있을 때 2가지 케이스로 나눠서 처리한다.
#인덱스의 첫 번째 노드일 때 삭제
p = self.table[index]
if p.key==key:
self.table[index] = ListNode() if p.next is None else p.next
return인덱스의 첫 번째 노드일 때 ListNode()로 빈 노드를 할당하게 했다.
#연결 리스트 노드 삭제
prev = p
while p:
if p.key == key:
prev.next= p.next
return
prev, p = p, p.nextprev는 이전 노드, p는 현재 노드로 계속 p.next로 탐색하다가 일치하는 노드를 찾으면 이전 노드의 다음을 현재 노드의 다음으로 연결한다. 즉 현재 노드를 아무런 연결 고리가 없게 끊어 버린다.
(5) 전체 코드
class MyHashMap:
#초기화
def __init__(self):
self.size = 1000
self.table = collections.defaultdict(ListNode)
#삽입
def put(self, key, value):
index = key % self.size
#인덱스에 노드가 없다면 삽입 후 종료
if self.table[index].value is None:
self.table[index] = ListNode(key,value)
return
#인덱스에 노드가 존재하는 경우 연결 리스트 처리
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)
#조회
def get(self, key):
index = key % slef.size
if self.table[index].value is None:
return -1
#노드가 존재할 때 일치하는 키 탐색
p = self.table[index]
while p:
if p.key == key:
return p.value
p = p.next
return -1
#삭제
def remove(self,key):
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
#연결 리스트 노드 삭제
prev = p
while p:
if p.key == key:
prev.next= p.next
return
prev, p = p, p.next
출처: 파이썬 알고리즘 인터뷰 책
