해시 테이블

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조입니다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점입니다.

해시

해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 의미합니다. 해시 테이블의 핵심은 해시 함수입니다. 해시 함수의 예제는 아래와 같습니다. 예제에서 입력값의 길이는 제 각각인데 화살표로 표시한 함수(해시 함수)를 통과하면 2바이트의 고정 크기 값으로 매핑되고 있습니다.

ABC -> A1
1324BC -> CB
AF32B -> D5

해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱(Hashing)이라 하며, 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법중 하나입니다. 해싱은 최적의 검색이 필요한 분야에 사용되며, 심볼 테이블(일반적으로 해시 테이블로 구현) 등의 자료구조를 구현하기에도 적합합니다.

성능 좋은 해시 함수들의 특징은 아래와 같습니다.

• 해시 함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것

비둘기집 원리(무조건 충돌)

비둘기집 원리란, n개 아이템을 m개 컨테이너에 넣을 때, n > m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 뜻합니다. 이처럼 해시 함수에서도 비둘기집 원리에 따라서 9개의 공간에 있는 곳에 10개의 아이템이 들어온다면 반드시 1번 이상은 충돌이 발생하게 됩니다. 다만, 좋은 해시 함수라면 충돌을 최소화하여 단 1번의 충돌만 일어나겠지만, 좋지 않은 해시 함수는 심하면 9번 모두 충돌이 발생할 수도 있습니다. 따라서 여러번 충돌하는 것은 그만큼 추가 연산을 필요로 하기에 가급적 충돌을 최소화하는 것이 좋습니다.

로드 팩터

로드 팩터(Load Factor)란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것입니다(load factor = n / k). 로드 팩터 비율에 따라 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야 할지를 결정합니다. 또한 이 값은 해시 함수가 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용됩니다. 일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소하게 되며, 자바 10의 경우 0.75를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당합니다.

해시 함수

해시 함수를 통해 키가 해시로 변경되는 과정

위의 그림과 같이 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라고 합니다. 해싱에는 다양한 알고리즘이 있으며, 최상위 분포를 제공하는 방법은 데이터에 따라 제각각입니다. 이 글에서는 해싱의 알고리즘에 대해서는 다루지 않겠습니다.

충돌

이미 언급했지만 아무리 좋은 해시 함수라도 아래의 그림과 같이 충돌(Collision)은 발생하게 됩니다.

해시 테이블의 충돌

위의 그림에서 윤아와 서현은 해시 값이 2로 같은 값이 되어 충돌이 발생했습니다. 이와 같이 충돌이 발생할 경우 처리하는 방식이 두 가지로 나뉘는데 이를 살펴보겠습니다.

개별 체이닝(Separate Chaining)

우선 입력값에 따른 해시의 결과를 아래의 표와 같이 정해보겠습니다. 해시는 키를 해싱한 결과이고, '윤아'와 '서현'을 해싱한 결과는 충돌한다고 가정하겠습니다.

키	값	해시	충돌 여부
윤아	15	2	충돌
유리	47	1
서현	17	2	충돌
수영	7	4

위의 표를 개별 체이닝 방식으로 구현한 그림

해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 연결 리스트로 연결하는 방식입니다. 충돌이 발생한 '윤아'와 '서현'은 '윤아'의 다음 아이템이 '서현'인 형태로 서로 연결리스트로 연결되었습니다. 간단이 원리를 요약하면 아래와 같습니다.

1. 키의 해시 값을 계산합니다.
2. 해시 값을 이용해 배열의 인덱스를 구합니다.
3. 같은 인덱스가 있다면 연결 리스트로 연결합니다.

개별 체이닝 문제점

다만 잘 구현한 경우 대부분의 탐색은 O(1)이지만 최악의 경우, 즉 모든 해시 충돌이 발생했다고 가정할 경우에는 O(n)이 됩니다. 자바 8에서는 연결 리스트 구조를 좀 더 최적화해서, 데이터의 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용하기도 했습니다.

오픈 어드레싱(Open Addressing)

오픈 어드레싱 방식은 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식입니다. 사실상 무한정 저장할 수 있는 체이닝 방식과는 다르게 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없습니다. 또한 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾기에, 개별 체이닝 방식과는 다르게 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장도 없습니다.

오픈 어드레싱 방식

오픈 어드레싱 방식에는 여러 가지가 존재하는데, 가장 간단한 방식인 선형 탐사(Linear Probing)방식을 사용한 그림입니다. 선형 탐사 방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행합니다. 특정 위치가 선점되어 있으면 바로 그다음 위치를 확인하는 식입니다. 이렇게 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입하게 됩니다. 즉, 가장 가까운 다음 빈 위치를 탐사해 새 키를 삽입하는 것입니다.

오픈 어드레싱 문제점

선형 탐사의 한 가지 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다는 점입니다. 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상을 클러스터링(Clustering)이라 하는데, 클러스터들이 점점 커지게 되면 인근 클러스터들과 서로 합쳐지는 일이 발생합니다. 그렇게 되면 해시 테이블의 특정 위치에는 데이터가 몰리고, 다른 위치에는 상대적으로 데이터가 거의 없는 상태가 될 수 있습니다. 이러한 클러스터링 현상은 탐사 시간을 오래 걸리게 하며, 전체적으로 해싱 효율을 떨어뜨리는 원인이 됩니다.

리해싱(Rehashing) 작업

오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없습니다. 따라서 일정 이상 채워지면, 즉 기준이 되는 로드 팩터 비율을 넘어서게 되면, 그로스 팩터(Growth Factor)의 비율에 따라 더 큰 크기의 또 다른 버킷이 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어납니다. 이는 동적 배열에서 공간이 가득 찰 경우, 더블링으로 새롭게 복사해서 옮겨가는 과정과 유사합니다.

언어별 해시 테이블 구현 방식

파이썬에서는 딕셔너리가 해시 테이블로 구현되어 있으며, 충돌 시 오픈 어드레싱 방식을 사용하여 해결합니다. 그 이유는 "연결 리스트(개별 체이닝 방식)를 만들기 위해서는 추가 메모리 할당이 필요하고, 추가 메모리 할당은 상대적으로 느린 작업이기 떄문에 택하지 않았다"고 합니다.

오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋습니다. 다만 슬롯의 80% 이상이 차게 되면 급격한 성능 저하가 일어나며, 체이닝과 달리 전체 슬롯의 전체 개수 이상(로드 팩터 1 이상)은 저장할 수 없습니다. 따라서 파이썬은 오픈 어드레싱 방식을 택해 성능을 높이는 대신, 로드 팩터를 작게 잡아 성능 저하 문제를 해결했습니다.

언어별 해시 테이블 구현

언어	방식
C++	개별 체이닝
자바(코틀린)	개별 체이닝
고(Go)	개별 체이닝
루비	오픈 어드레싱
파이썬	오픈 어드레싱

참조
파이썬 알고리즘 인터뷰
Linear probing vs Chainging
HashMap의 해시충돌(hash collision)과 자바의 대응책

틀린 부분은 댓글로 남겨주시면 수정하겠습니다..!!