해싱 (hashing)

해싱
- 키 값 비교로써 탐색하고자 하는 항목에 접근
- 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근


* 해시 테이블(hash table)
- 키 값의 연산에 의해 직접 접근이 가능한 구조

해싱의 구조

해시 함수 (hash function)

• 탐색키를 입력받아 해시 주소 생성
• 이 해시 주소가 배열로 구현된 해시 테이블의 인덱스

해시 테이블의 구조

해시테이블

• M 개의 버켓으로 구성된 테이블
• 하나의 버켓에 s개의 슬롯 가능

충돌 (collision)

• 서로 다른 두 개의 탐색키 k1과 k2가 같은 경우

오버플로우 (overflow)

• 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하는 것

실제의 해싱

1. 해시 테이블의 크기가 제한되므로, 존재 가능한 모든 키에 대해 저장 공간을 할당할 수 없음
   충돌과 오버플로우는 필연적으로 발생함

2. 알파벳 문자열 키의 해시함수가 키의 첫 번째 문자의 순서여도 overflow가 발생함

좋은 해시 함수의 조건

1. 충돌이 적어야함
2. 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 함
3. 계산이 빨라야함

해시 함수 종류

1. 제산 함수 (나머지 연산자 사용)
   • h(k) = k mod M
   • 해시 테이블의 크기 M은 소수
2. 퐁딩 함수 (접지 함수)
   • 이동 폴딩 (shift folding)
     - 탐색 키를 여러 부분으로 나눈값들을 더하여 해시 주소를 얻음
   • 경계 폴딩 (boundary folding)
     - 탐색키의 이웃한 부분을 거꾸로 더하여 해시 주소를 얻음
3. 중간제곱 합수
   • 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소 생성
4. 비트추출 함수
   • 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용
5. 숫자 분석 방법
   • 키 중에서 편중되지 않는 수들을 해시테이블의 크기에 적합하게 조합하여 사용

충돌 해결책

• 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소를 가지는 현상
• 충돌이 발생하면 오버플로우 발생 (해시 테이블에 항목 저장 불가능)
• 오버플로우를 효과적을 해결하는 방법 필요

오버플로우 해결책

• 선형조사법 (linear probing)
  - 충돌이 일어난 항목을 해시테이블의 다른 위치에 저장
• 체이닝 (chaining)
  - 각 버켓에 삽입과 삭제가 용이한 연결 리스트 할당
  

선형조사법

출돌이 발생했다면,
비어있는 공간이 나올 때까지 조사
(테이블의 끝에 도달하면 다시 테이블의 처음부터 조사)
조사 시작한 곳으로 돌아오면 테이블이 가득 찬 상태

조사되는 위치 : h(k), (h(k)+1) % M, (h(k)+2) % M,...

군집화 문제 발생

• 한번 충돌이 발생하면 그 위치에 항목들이 집중되는 현상
• 탐색 시간을 증가시킴

이차 조사법 (quadratic probing)

선형 조사법과 달리 이차 함수에 의해 이동 폭을 넓혀 가면서 사용

조사되는 위치 : h(k), h(k)+1, h(k)+4, ...

선형 조사법에서의 문제점인 군집 크게 완화 가능

이중 해싱법

선형 조사와 이차 조사에서, 해시 함수가 같은 값이 나오면 동일한 형태로 빈 공간을 찾으므로, 같은 값이 많이 발생하는 해시 함수일 경우 잦은 충돌이 발생함.

재해싱(rehashing)라고도 함

• 오버플로우가 발생하면 원 해시함수와 다른 별개의 해시 함수 사용
• step=C-(k mod C) -> 1에서 C 사이의 값을 생성 (
• h(k), (h(k)+step) % M, (h(k)+2 * step) % M, ...

체이닝

오버플로우 문제를 연결 리스트로 해결

• 각 버켓에 고정된 슬롯이 할당되어 있지 않음
• 각 버켓에, 삽입과 삭제가 용이한 연결 리스트 할당
• 버켓 내에서는 연결 리스트 순차 탐색