[알고리즘] 탐색 - 해시테이블

해시 테이블

해싱
- 키 값을 기반으로 데이터의 저장 위치를 직접 계산함으로써 상수 시간 내에 데이터를 저장, 삭제, 탐색할 수 있는 방법
해시 테이블
- 각 위치마다 주소가 부여되어 있는 저장공간
- 배열 형태
- 배열의 각각의 위치들을 슬롯이라 칭함

해시 함수

키 값을 해시 테이블의 주소로 변환하는 함수
종류
- 제산 잔여법, 비닝, 중간 제곱법
- 문자열을 위한 함수(비닝, 단순 합, 가중 합) 등
계산이 용이해야 함
적은 충돌 발생
- 각 키를 테이블의 각 슬롯에 균등하게 사상시킬 수 있어야 함

해시 함수 - 제산 잔여법

h(K) = K mod M (k:키값, M:해시 테이블의 크기)
- h(123) = 123 mod 11 = 2
M의 선택에 주의해야 함
- M=2^r^이면 h(K)는 키 값의 하위 r비트의 값이 됨
- 키 값의 전체 비트가 주소 계산에 활용되지 못함
- M은 2의 거듭제곱과 상당한 차이가 있는 소수로 선택하는 것이 바람직

해시 함수 - 비닝

U를 단순하게 M 등분하여 각 등분을 각 슬롯으로 해시
상위 비트의 분포가 고르지 못하면 몇 개의 슬롯에 집중되는 문제

해시 함수 - 중간 제곱법

h(K) = (K^2^/2^m^) mod 2^r^
- m : 키 값을 제곱한 결과에서 사용하지 않을 하위의 비트 크기
- r : 해시 주소로 취할 비트의 크기
모든/대부분의 비트가 결과 생성에 기여
- 상위/하위 자리의 분포에 의해 지배적인 영향을 받지 않음

해시 함수 - 문자열을 위한 비닝

U를 단순하게 M 등분하여 각 등분을 각 슬롯으로 해시
문자열의 앞쪽 일부를 해시 결과로 사용
- 입력 문자열의 앞쪽의 분포가 고르지 못하면 결과가 슬롯에 고르게 분포되지 못함

해시 함수 - 문자열을 위한 단순 합

각 문자의 코드 값을 합한 후 제산 잔여법 적용
M « SUM 일 때 유용
짧은 문자열에 대해서는 비효과적
문자의 출현 순서는 고려되지 않음 ex) h(‘ABC’) = h(‘BCA’)

해시 함수 - 문자열을 위한 가중 합

각 문자의 코드 값 자리에 따른 가중치를 곱한 값을 합한 후 제산 잔여법을 적용

충돌

서로 다른 키 값 x, y에 대하여 h(x)=h(y)인 경우
충돌 해결 방법
- 개방 해싱(연쇄법) : 충돌된 데이터를 테이블 밖의 별도의 장소에 저장/관리 -> 연결 리스트 사용
- 폐쇄 해싱(개방 주소법) : 해시 테이블 내의 다른 슬롯에 충돌된 데이터를 저장/관리
  - 종류 : 버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱

충돌 해결 방법 - 개방 해싱

해시 테이블의 각 슬롯을 연결 리스트의 헤더로 사용
- 해시 테이블과 연결 리스트가 주기억장치 내에서 유지될 때 적합

충돌 해결 방법 - 폐쇄 해싱 - 버킷 해싱

해시 테이블 슬롯을 버킷으로 묶어 버킷 단위로 해싱

충돌 해결 방법 - 폐쇄 해싱 - 선형 탐사

탐사 순서
- 어떤 키 K에 대해서 탐사되는 슬롯의 순서열
- p(K, i) -> p(K, 0)=h(K), p(K, 1), p(K, 2), p(K, 3) …
선형 탐사
- p(K, i) = (h(K) + i) mod M
- 홈 위치가 사용 중이면 빈 슬롯을 찾을 때까지 테이블의 다음 슬롯으로 순차적으로 이동
- 가장 간단하지만 최악의 방법

충돌 해결 방법 - 폐쇄 해싱 - 이차탐사

탐사 순서의 계산에 이차식을 이용
- 충돌이 발생하는 횟수의 제곱 형태로 탐사 순서를 결정
서로다른 홈 위치를 갖는 두 키는 서로 다른 탐사 순서를 가짐
모든 슬롯이 탐사 순서에 사용되지 않음
- 탐사 함수와 해시 테이블 크기가 적절히 조합되면 많은 슬롯의 방문이 가능
2차 클러스터링 문제
- 동일한 홈 위치를 갖는 두 키는 동일한 탐사 순서를 가짐

충돌 해결 방법 - 폐쇄 해싱 - 이중해싱

탐사 순서를 원래의 키 값을 이용하여 해싱
1차/2차 클러스터링 문제 해결
서로 다른 두 키의 홈 위치가 동일해도 서로 다른 탐사 순서를 가짐
좋은 이중 해싱을 구하려면 탐사 순서에 있는 모든 상수가 해시 테이블의 크기 M과 서로 소가 되어야 함