해시 테이블(Hash Table)이란?

해시 테이블(Hash Table)은 키(Key)를 값(Value)에 매핑할 수 있는 자료구조를 의미한다. 해시 테이블의 가장 큰 특징은 대부분의

연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다.

해시 함수(Hash Function)

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

예를 들어, 입력값 ABC, 1324BC, AF32B로 각각 3글자, 6글자, 5글자를 2바이트의 고정 크기 값으로 매핑하는 함수를 해시 함수라고

한다. 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라고 하며, 해싱은 정보를 가능한 빠르게 저장하고 

검색하기 위해 사용하는 중요한 기법 중 하나이다. 이외에도 해시 함수는 체크섬, 손실 압축, 무작위화 함수, 암호 등과도 관련이 깊으며

때로는 서로 혼용되기도 한다. 

좋은 해시 함수란?

해시 함수 값 충돌이 적고, 연산이 쉽고 빠르며, 해시 테이블 전체에 해시 값이 균일하게 분포할 수 있으며, 사용할 키의 모든 정보를

사용하여 해싱할 수 있고, 해시 테이블 사용 효율이 높은 함수이다.

로드 팩터란?

로드 팩터란 해시 테이블에 저장된 데이터 개수 N을 버킷의 개수 K로 나눈 것(Load Factor = N / K)을 의미한다. 로드 팩터 비율에 

따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야 할지를 결정한다. 또한 이 값은 해시 함수가 키들을 잘 분산해

주는지를 말하는 효율성 측정에도 사용된다. 일반적으로 로드 팩터가 증가할 수록 해시 테이블의 성능은 점점 감소하게 된다.

충돌을 처리하는 방법 1) : 개별 체이닝

해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 연결 리스트로 기존의 값과 새로운 값을 연결하는 방식을 의미한다. 

간단한 원리를 요약하자면 우선, 키의 해시 값을 계산한다. 이후 해시 값을 이용하여 배열의 인덱스를 구한다. 그런데 같은 인덱스에 

값이 있다면 연결 리스트로 연결한다. 잘 구현한 경우 탐색은 O(1)이지만, 최악의 경우, 즉 모든 해시 충돌이 발생할 경우 O(n)이 된다.

충돌을 처리하는 방법 2) : 오픈 어드레싱

오픈 어드레싱은 충돌 발생 시 탐사를 토해 빈 공간을 찾아나서는 방식이다. 사실상 무한정 저장할 수 있는 체이닝 방식과 달리 

오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아

해결하며, 이 때문에 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.

또한, 탐사 방식이 선형적일 경우 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 발생한다. 해시 테이블

여기저기에 연속된 데이터 그룹이 생기는 현상을 클러스터링이라 하는데, 클러스터들이 점점 커지게 되면 인근 클러스터들과

서로 합쳐지는 일이 발생한다. 그렇게 되면 해시 테이블의 특정 위치에 데이터가 몰리게 되고 다른 위치에는 상대적으로 데이터가

거의 없는 상태가 될 수 있다. 이러한 클러스터링 현상은 탐사 시간을 오래 걸리게 하며 전체적으로 해싱 효율을 떨어뜨리는 원인이 된다.

오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없다. 따라서 일정 이상 채워지면, 즉 기준이 되는 로드 팩터 비율을

넘어서게 되면 그로스 팩터 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어난다.

파이썬의 해시 테이블 구현 방식

파이썬은 오픈 어드레싱 방식으로 구현되어 있다. 파이썬이 체이닝을 사용하지 않는 이유는 연결 리스트를 만들기 위해서는 추가 메모리

할당이 필요하고 추가 메모리 할당은 상대적으로 느린 작업이기 때문이다. 그러나 오픈 어드레싱 방식은 슬롯의 일정 비율을 넘어가면

성능이 나빠진다. 파이썬의 로드 팩터는 0.66으로 이 기준을 넘어갈 경우 리해싱 작업이 발생한다.