해시 탐색(Hash Search)이란?

해시 탐색(Hash Search)은 데이터 검색을 빠르게 수행할 수 있도록 해주는 탐색 기법 중 하나입니다. 이는 해시 테이블(Hash Table)이라는 자료구조를 사용하며, 일반적으로 O(1)의 평균 시간복잡도를 가집니다. 즉, 대부분의 경우 데이터 검색이 한 번의 연산으로 끝나므로 매우 빠른 성능을 보장합니다.

Table of Contents

해시 함수(Hash Function)

해시 탐색에서 가장 중요한 요소는 해시 함수(Hash Function)입니다. 해시 함수는 주어진 키(Key)를 특정한 해시 값(Hash Value)으로 변환하여, 해시 테이블 내의 특정한 위치(Index)를 결정하는 역할을 합니다.

좋은 해시 함수의 조건은 다음과 같습니다:

충돌(Collision)을 최소화할 것: 서로 다른 키들이 동일한 해시 값을 가지는 경우(충돌)가 적어야 함.
계산이 단순하고 빠를 것: 해시 함수가 복잡하면 오히려 연산 속도가 느려질 수 있음.
해시 값이 균등하게 분포할 것: 특정 영역에 데이터가 몰리지 않도록 설계해야 함.

해시 함수 설계 방법

해시 함수는 여러 가지 방식으로 설계할 수 있으며, 대표적인 방법으로는 다음과 같은 기법이 있습니다.

제산법(Division Method)

가장 간단한 해시 함수로, 키를 특정한 소수(Prime Number) P로 나눈 나머지를 해시 값으로 사용하는 방식입니다.

h(k) = k % P

예제:
- 키(Key) = 12345
- P = 7 (소수)
- 해시 값: 12345 % 7 = 4
특징:
- 계산이 단순하여 빠르지만, P의 선택이 중요함.
- 테이블 크기와 P가 서로소일 경우 충돌을 줄일 수 있음.

폴딩법(Folding Method)

키를 여러 부분으로 나눈 후, 이를 더하거나 특정 연산을 수행하여 해시 값을 생성하는 방법입니다.

h(k) = (부분1 + 부분2 + ... ) % 테이블 크기

예제:
- 키(Key) = 567890123
- 이를 두 부분(56789와 0123)으로 나누고 합산: 56789 + 0123 = 57912
- 테이블 크기 1000으로 나눠 해시 값 결정: 57912 % 1000 = 912
특징:
- 키 값이 큰 경우에도 효과적으로 변환 가능.
- 데이터의 특정 패턴이 해시 값에 영향을 줄 수 있음.

제곱법(Mid-Square Method)

키를 제곱한 후, 중간에 있는 값을 해시 값으로 사용하는 방식입니다.

h(k) = (k^2의 중간 자리 값) % 테이블 크기

예제:
- 키(Key) = 123
- 123^2 = 15129
- 중간 숫자 ‘512’를 해시 값으로 사용
특징:
- 키 값이 균등하게 분포할 가능성이 높음.
- 키가 너무 작거나 크면 비효율적일 수 있음.

숫자 분석법(Digit Analysis Method)

여러 개의 숫자로 이루어진 키에서 특정 자리수를 선택하여 해시 값을 생성하는 방법입니다.

h(k) = 선택된 자리의 숫자 조합 % 테이블 크기

예제:
- 키(Key) = 98564731
- 특정 자리(예: 2, 4, 6번째 숫자) 선택 → 8, 6, 7
- 해시 값 = 867
특징:
- 데이터가 고르게 분포되어 있는 경우 효과적.
- 키 값이 특정 패턴을 가지면 비효율적일 수 있음.

해시 충돌(Collision)과 해결 방법

아무리 좋은 해시 함수를 사용해도 충돌(Collision)은 발생할 수 있습니다. 따라서 이를 해결하기 위한 방법이 필요합니다. 대표적인 충돌 해결 방법으로는 다음이 있습니다.

체이닝(Chaining): 같은 해시 값에 대해 연결 리스트(Linked List)를 사용하여 여러 개의 키를 저장하는 방식.
개방 주소법(Open Addressing): 충돌이 발생하면 다른 빈 슬롯을 찾아 저장하는 방식.
- 선형 탐색(Linear Probing):
```
h(k, i) = (h(k) + i) % 테이블 크기
```
- 제곱 탐색(Quadratic Probing):
```
h(k, i) = (h(k) + i^2) % 테이블 크기
```
- 이중 해싱(Double Hashing):
```
h(k, i) = (h1(k) + i * h2(k)) % 테이블 크기
```