오늘은 계산 검색 방식인 해싱에 대하여 작성해보려 합니다.

개요

산술적인 연산을 통해 키가 있는 위치를 계산하여 바로 찾아가는 계산 방식을 해싱이라고 합니다.

키값을 원소의 위치로 변환하는 함수를 해시 함수라고 하며, 해시 함수에 의해 계싼된 주소의 위치에 항목을 저장한 표를 해시 테이블이라 불립니다.

검색 방법

키값에 대하여 해시 함수를 계산하여 주소를 구하고, 구한 주소에 해당되는 해시 테이블을 찾아서 있으면 검색 성공이고, 없으면 실패가 됩니다.

해시 테이블은 n개의 버킷과 m개의 슬롯으로 이루어져 있으며, 해시 함수에 의해서 계산된 주소는 버킷 주소가 됩니다.

사용되는 해시 함수는 0~n-1개 사이의 버킷 수조를 만들어야 합니다.

해시 함수에 의해서 알아낸 버킷에 키값이 저장된 슬롯이 여러개 있다면, 순차검색이 적용되어 검색합니다.

동거자

서로 다른 키값을 가지지만 해싱 함수에 의해 같은 버킷에 저장되는 값을 동거자라고 합니다.

충돌

서로 다른 키값에 대해 해시 함수에 의해서 주어진 버킷 주소가 같은 경우에 충돌이라고 하지만, 충돌이 발생한 경우 동거자로 처리하면 됩니다.

다만, 비어있는 슬롯이 없는 경우에는 오버플로우가 발생하여 문제가 생깁니다.

키값 밀도

사용 가능한 전체 키값들 중에서 현재 해시 테이블에 저장되어서 실제 사용되는 키값의 개수 정도를 나타냅니다.

적재 밀도

적재 밀도는 해시 테이블에 저장 가능한 키값 갯수중에 현재 해시 테이블에 저장되고 있어서 실제 사용되는 키값의 개수 정도를 나타냅니다.

다음 포스팅에서 해시 함수에 대하여 기술될 예정입니다.