Hashing 알아보기

오늘은 검색방법중 해싱에 대하여 알아보았습니다.

해싱은 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 검색방법입니다.

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

검색법

키 값에 대해 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블을 찾습니다.

있으면 검색됩니다.

해시 테이블은 n개의 버킷과 m개의 슬롯으로 구성되며, 함수에 의해 계산되는 주소는 버킷 주소가 됩니다.

동거자

모든 키값이 다 사용되지 않으므로, 메모리 절약을 위해 버킷의 수를 줄이고 같은 버킷에 여러 개의 슬롯을 두게 됩니다.

이렇게 되면 다른 키값이 같은 버킷에 있다면 이 키들은 동거자라고 불립니다.

충돌

서로 다른 키값에 대해 해싱 함수에 의해 주어진 버킷 주소가 같은 경우를 충돌이라고 합니다.

다 차 있는 포화 버킷 상태에서 그 상태에 충돌이 난다면, 오버플로우가 납니다.

키값 밀도

사용가능한 키들 중에 현재 해시 테이블에 저장되어서 실제 사용된 키의 갯수를 나타냅니다.

적재 밀도

해시 테이블에 저장가능한 키값의 갯수중, 현재 해시 테이블에서 실제 사용중인 키값의 갯수를 나타냅니다.

해싱 함수 종류

  • 중간 제곱 함수

키값을 제곱한 결과값에서 중간에 잇는 비트를 주소로 사용하는 방법입니다.

  • 제산 함수

나머지 연산자를 사용하는 방법입니다.

  • 승산 함수

곱하기 연산을 사용하는 방법입니다.

  • 접지 함수

키의 비트수가 해시 테이블의 인덱스 비트수보다 큰 경우 사용하는 방법입니다.

  • 숫자 분석 함수

키값을 이루고 있는 각 자릿수의 분포를 분석하면서 주소로 사용하는 방법입니다.

  • 진법 변환 함수

10진수가 아닐 때 사용하는 방법입니다.

  • 비트 추출 함수

해시 테이블의 크기가 2^k일 때 키값을 2진수로 놓고, 임의의 비트를 추출하여 사용하는 방법입니다.

Written on March 20, 2018