해시 테이블
해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조이다.
해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.
해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.
성능 좋은 해시 함수들의 특징은 다음과 같다.
- 해시 함숫값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높을 것
로드 팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다.
로드 팩터 비율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야 할지를 결정한다.
일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소하게 된다.
따라서 특정 로드 팩터를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당한다.
충돌이 발생했을 때 처리하는 방법으로는 대표적으로 개별 체이닝, 오픈 어드레싱이 있다.
개별 체이닝은 충돌 발생 시 연결 리스트로 연결하는 방식이다.
자세히 설명하자면 키의 해시 값을 계산하고, 해시 값을 이용해 배열의 인덱스를 구한다. 같은 인덱스가 있다면 연결 리스트로 연결한다.
개별 체이닝은 최악의 경우 O(n)의 시간 복잡도를 갖는다.
따라서 데이터의 개수가 많아지면 연결 리스트가 아닌 레드 블랙 트리로 저장하는 형태로 사용하기도 한다.
오픈 어드레싱은 충돌 발생 시 탐사를 통해 빈 공간을 찾아 나서는 방식이다.
사실상 무한히 저장할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다.
따라서 일정 이상 채워지면, 즉 기준이 되는 로드 팩터 비율을 넘어서게 되면
그로스 팩터 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어난다.
또한, 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결하며,
이 때문에 개별 체이닝 방식과 달리 모든 원소가 반드시 자신의 해시 값과 일치하는 주소에 저장된다는 보장은 없다.
또한, 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다.
해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 이러한 현상을 클러스터링이라 하는데,
클러스터들이 점점 커지게 되면 인근 클러스터들과 서로 합쳐지는 일이 발생한다.
이는 탐사 시간을 오래 걸리게하며 전체적으로 해싱 효율을 떨어뜨리는 원인이 된다.
파이썬의 딕셔너리는 오픈 어드레싱 방식의 해시 테이블로 구현되어 있다.
이유는 체이닝 시 malloc으로 메모리를 할당하는 오버 헤드가 높아 오픈 어드레싱을 택했다고 한다.
그리고 파이썬의 로드 팩터는 0.66으로 로드 팩터를 작게 잡아 성능 저하 문제를 해결하고자 하였다.