[해시테이블/해시함수/충돌] 개념 알아보기

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조를 구현하는 자료구조이다. 

 

해시 테이블의 가장 큰 특징은 대부분의 연산이 시간복잡도가 O(1) 이라는 점이다. 

덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 

 

1. 해시 

해시 테이블의 핵심은 해시 함수다.

해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 

 

여기서 입력값은 ABC, 1324BC, AF32B로 각각 3글자, 6글자, 5글자이지만,

화살표로 표시한 특정 함수를 통과하면 2바이트의 고정 크기 값으로 매핑된다.

여기서 화살표 역할을 하는 함수가 바로 해시 함수다. 

(해시 함수를 만드는 방법론도 하나의 주제가 될 수 있지만 코딩테스트 주제를 벗어난다. 

참고로,  구글은 해시 함수를 딥러닝으로 학습한 모델을 적용해 충돌을 최소화하는 논문을 발표하기도 했다. )

 

 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱(Hashing)이라한다. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나다. 해싱은 최적의 검색이 필요한 분야에 사용되며, 체크섬, 손실압축, 무작위화 함수, 암호 등과도 관련이 깊다.

 

 

< 성능 좋은 해시 함수들의 특징 >

1. 해시 함수 값 충돌의 최소화

2. 쉽고 빠른 연산

3. 해시 테이블 전체에 해시 값이 균일하게 분포 

4. 사용할 키의 모든 정보를 이용하여 해싱 

5. 해시 테이블 사용 효율이 높을 것 

 

<해시 충돌을 이해하는데 도움되는 예시 - 비둘기집 원리>

비둘기집 원리란 n개 아이템을 m개 컨테이너에 넣을 떄, n>m 이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 말한다. 

예를 들어, 9개의 공간에 10개의 아이템이 들어온다면 반드시 1번 이상은 충돌이 발생하게 된다. 

좋은 해시 함수라면 충돌을 최소화한 단 1번의 충돌만 일어나게 하겠지만, 좋지 않은 해시 함수의 경우 심하면 9번 모두 충돌해서 10번 모두 충돌해서, 9개의 공간 중 1개밖에 사용하지 못할 수도 있다. 

여러 번 충돌한다는 것은 그만큼 추가 연산을 필요로 하기 때문에 가급적 충돌은 최소화하는 것이 좋다. 

 

<로드 팩터>

로드팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다. 

Load Factor = n / k 

로그 팩터 비율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야 할지 결정한다. 

또한 이 값은 해시 함수가 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용된다. 

자바 10에서는 해시맵의 디폴트 로드 팩터를 0.75로 정했다. 

일반적으로 로드 팩터가 증가할 수록 해시 테이블의 성능은 점점 감소하게 되며, 자바 10의 경우 0.75를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당한다. 

 

2. 충돌 

아무리 좋은 해시 함수라도 충돌 Collision 은 발생하게 된다. 

충돌이 발생할 경우 어떤 식으로 처리하게 되는지 살펴보자 

<개별 체이닝>

 

해시 테이블의 기본 방식인 개별 체이닝을 충돌 발생 시 이 그림과 같이 연결리스트로 연결하는 방식이다. 

이처럼 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 되므로, 개별 체이닝 방식은 인기가 높다. 

 

1. 키의 해시 값을 계산한다. 

2. 해시 값을 이용해 배열의 인덱스를 구한다. 

3. 같은 인덱스가 있다면 연결 리스트로 연결한다. 

 

 

잘 구현한 경우 대부분의 탐색은 O(1) 이지만 최악의 경우, 즉 모든 해시 충돌이 발생했다고 가정할 경우에는 O(n)이 된다. 

자바 8에서는 연결 리스트 구조를 좀 더 최적화해서, 데이터 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용하기도 했다. 

(참고로, 레드-블랙 트리는 자가 균형 이진 탐색 트리이다.)

 

<오픈 어드레싱>

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

오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없다. 따라서 일정 이상 채워지면, 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어난다.

 

여러 가지 오픈 어드레싱 방식중에서 가장 간단한 방식인 선형 탐사 방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 특정 위치가 선점되어 있으면 바로 그다음 위치를 확인하는 식이다. 이렇게 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입하게 된다. 

 

선형 탐사의 한 가지 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다는 점이다. 

해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상을 클러스터링이라고 한다. 

클러스터들이 점점 커지게 되면 인근 클러스터들과 서로 합쳐지는 일이 발생한다. 

이러한 현상은 탐사 시간을 오래 걸리게 하며, 전체적으로 해싱 효율을 떨어뜨리는 원인이 된다. 

 

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

파이썬의 해시 테이블은 충돌 시 오픈 어드레싱 방식을 사용한다. 

파이썬이 체이닝을 사용하지 않는 이유는 연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요하고, 추가 메모리 할당은 상대적으로 느린 작업이기 때문이다. 

오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다. 

그러나 슬롯의 80% 이상이 차게 되면 급격한 성능 저하가 일어나며, 체이닝과 달리 로드 팩터 1 이상은 저장할 수 없다. 

빈 공간을 탐사하는 선형 탐사 방식은 공간이 찰수록 탐사에 점점 더 오랜 시간이 걸리며, 가득 차게 될 경우 더 이상 빈 공간을 찾을 수 없기 때문이다. 

 

따라서 최근의 루비나 파이썬 같은 모던 언어들은 오픈 어드레싱 방식을 택해 성능을 높이는 대신, 로드 펙터를 작게 잡아 성능 저하 문제를 해결한다. 파이썬의 로드 펙터는 0.66으로 자바보다 작으며 루비는 0.5로 훨씬 더 작다. 

 

언어	방식
C++	개별 체이닝
자바	개별 체이닝
고	개별 체이닝
루비	오픈 어드레싱
파이썬	오픈 어드레싱