해시 테이블 (Hash Table)
해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형 (ADT)을 구현하는 자료구조이다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 이는 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 된다.
해시 (Hash)
해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다. 해시 테이블의 핵심은 해시 함수이다. 입력값 ABC, 1324BC, AF32B가 주어진다면 입력값들의 크기는 모두 다르지만 해시 함수를 거쳐 고정 크기 값으로 매핑된다.
ABC -> A1
1324BC -> CB
AF32B -> D5이렇게 3글자, 6글자, 5글자의 입력값을 모두 2글자로 매핑하는 역할을 하는 함수를 해시 함수라고 한다.
해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라 하고 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나이다. 해싱은 최적의 검색이 필요한 분야에 사용되며 심볼 테이블 등의 자료구조에도 적합하다. 이외에도 해시 함수는 CheckSum, 무작위화 함수, 암호 등에도 사용된다.
성능이 좋은 해시 함수의 특징은 다음과 같이 정리할 수 있다.
- 해시 함수 값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 높은 해시 테이블 사용 효율
해시 함수 값 충돌
아무리 잘 짜여진 해시 함수라고 해도 충돌은 생각보다 쉽게 발생한다. 이 예로 생일 문제를 들 수 있다. 1년은 365일이므로 여러 사람이 모였을 때에 2명이 같은 생일일 확률은 비둘지집 원리에 따라 366명이 모여야 발생할 것이라고 일반적으로 생각하게 된다. 그러나 실제로는 23명만 있어도 50%가 넘고 57명이 모이면 99%를 넘게 된다.
23명이 모이는 경우를 10만번 실험했고 그 결과 생일이 같을 확률은 50.7%가 나왔다. 이처럼 충돌은 매우 쉽게 일어난다.
비둘기집 원리
서랍 원리라고도 불리며 간단한 귀류법으로 모순을 이끌어내 쉽게 증명할 수 있다. 9개의 비둘기집에 10마리의 비둘기를 넣어야 한다면 반드시 1번 이상의 충돌이 발생한다. 좋은 해시 함수라면 1번만 발생하겠지만 좋지 않은 해시 함수의 경우 최악의 경우 9번 모두 충돌하여 9개 중 1개의 공간만 사용하게 될 수도 있다. 여러번 충돌한다는 것은 그만큼 추가 연산을 필요로 하기 때문에 가급적 충돌은 최소화하는 것이 좋다.
로드 팩터 (Load Factor)
로드 팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다. 로드 팩터에 따라 해시 함수를 재작성할지 해시 테이블의 크기를 조정할지 결정하게 된다. 또한 로드 팩터는 해시 함수가 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용된다. 자바 10에서는 로드 팩터를 0.75로 정하였고 이를 시간과 공간 비용의 적절한 절충안이라고 말한다. 일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 안좋아지고 자바 10의 경우에는 0.75를 넘을 경우 동적 배열처럼 해시 테이블의 공간을 재할당한다.
충돌 (Collision)
아무리 좋은 해시 함수라도 충돌은 발생한다.
이 그림에서는 윤아와 서현이 해시 함수를 거치면서 해시값 충돌이 발생한 것을 볼 수 있다. 충돌을 처리하는 방식에는 2가지가 있다.
개별 체이닝 (Separate Chaining)
키 값 해시 충돌여부
윤아 15 2 충돌
유리 47 1
서현 17 2 충돌
수영 7 4위와 같이 키와 값, 해시가 정해져 있을 때 이를 그림으로 나타내면 다음과 같다.
해시 테이블의 기본 방식이기도한 개별 체이닝은 충돌 발생 시 위의 그림과 같이 연결 리스트로 연결을 한다. 이렇게 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 구현이 가능하기 때문에 개별 체이닝 방식은 인기가 높다. 원래 해시 테이블 구조의 원형이기도 하며 가장 전통적인 방식으로 흔히 해시 테이블이라고 하면 이 방식을 가리킨다. 개별 체이닝의 원리는 다음과 같다.
- 키의 해시 값을 계산한다.
- 해시 값을 이용해 배열의 인덱스를 구한다.
- 같은 인덱스가 있다면 연결 리스트로 연결한다.
잘 구현한 경우 대부분의 경우 O(1)에 탐색이 가능하지만 최악의 경우 모든 해시 충돌이 발생하여 O(n)에 탐색을 하게 될 수도 있다.
오픈 어드레싱 (Open Addressing)
오픈 어드레싱 방식은 충돌 발생 시 탐사를 통해 빈 공간을 찾아내는 방식이다. 사실상 무한정으로 저장할 수 있는 개별 체이닝 방식과 달리 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 그 공간으로 할당시킨다. 이 때문에 개별 체이닝과 달리 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.
키 값 해시 충돌여부
윤아 15 2 충돌
유리 47 1
서현 17 2 충돌
수영 7 4
위의 표를 그림으로 나타내면 위와 같이 나타낼 수 있다. 여러 가지 오픈 어드레싱 방식 중에서 가장 간단한 방식인 선형 탐사 방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 탐사 중 비어있는 공간을 발견하면 삽입하게 된다. 윤아의 해시값이 먼저 2에 해당하는 주소에 들어갔기 때문에 서현은 다음 빈 공간인 3을 찾아간 것을 볼 수 있다. 이렇게 선형 탐사 방식은 구현 방법이 간단하면서도 의외로 전체적인 성능이 좋은 편이다.
선형 탐사 방식의 한가지 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않는다는 점이다. 현재 위치부터 순차적으로 탐사를 진행하기 때문에 해시 테이블 여기저기에 연속된 데이터 그룹이 생기게 된다. 이를 클러스터링이라고 하는데 클러스터들이 점점 커지게 되면 인근의 클러스터와 함쳐지게 된다. 이렇게 되면 해시 테이블의 특정 위치에는 데이터가 몰리게 되고 다른 위치에는 상대적으로 데이터가 거의 없는 상태가 될 수 있다. 이러한 클러스터링 현상은 탐사 시간을 오래 걸리게 하고 전체적으로 해싱 효율을 떨어트리는 원인이 된다.
오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에 삽입할 수 없다. 따라서 일정 이상 채워지면, 즉 기준이 되는 로드 팩터를 넘게 되면 그로스 팩터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱(ReHashing) 작업이 일어난다. 이는 동적 배열에서 공간이 가득 찰 경우, 더블링을 통해 새롭게 복사해 옮겨가는 과정과 비슷하다.
언어별 해시 테이블 구현 능력
파이썬에서 가장 흔히 쓰이는 자료형 중 하나인 딕셔너리는 해시 테이블로 구현되어 있다. 면접 시 "해시 테이블로 구현된 파이썬의 자료형을 제시하라" 라는 질문을 받는다면 바로 딕셔너리라고 답할 수 있어야 한다.
파이썬은 오픈 어드레싱 방식으로 해시 테이블을 구현한다. CPython 구현에 다음과 같은 주석이 적혀있다.
체이닝 시 malloc으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다.
연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요하고, 추가 메모리 할당은 상대적으로 느린 작업이기 때문에 택하지 않았다는 뜻이다.
오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다. 그러나 슬롯의 80% 이상이 차게 되면 급격하게 성능 저하가 일어나고, 체이닝과 달리 전체 슬롯의 전체 개수 이상, 즉 로드 팩터 1 이상은 저장할 수 없다. 빈 공간을 탐사하는 선형 탐사 방식은 공간이 찰수록 탐사에 점점 더 오랜 시간이 걸리게 되고 가득 차게될 경우에는 더 이상 빈 공간을 찾을 수 없게 된다.
최근의 루비나 파이썬같은 모던 언어들은 위와 같은 이유로 오픈 어드레싱 방식을 채택하여 성능을 높이는 대신, 로드 팩터를 작게 잡아 성능 저하 문제를 해결한다. 파이썬의 로드 팩터는 0.66으로 자바보다 작고, 루비는 0.5로 훨씬 더 작다.
언어 방식
C++ 개별 체이닝
자바 개별 체이닝
고(Go) 개별 체이닝
루비 오픈 어드레싱
파이썬 오픈 어드레싱