해싱(Hashing)은 해시 함수(hash function)라 불리는 수학적 함수를 사용하여 텍스트나 숫자 목록으로부터 고유한 값을 생성하는 과정입니다. 숫자 키나 알파벳·숫자가 혼합된(alphanumeric) 키를 처리할 수 있는 다양한 해시 함수가 존재하며, 대표적인 방식들은 아래에서 자세히 살펴보겠습니다.
해시 함수(Hash Functions)
해시 함수는 임의 크기의 입력값을 고정된 범위의 해시 값으로 변환하는 역할을 합니다. 실무에서 널리 알려진 대표적인 해시 함수 방식은 다음과 같습니다.
1. 나눗셈 방법(Division Method)
나눗셈 방법은 해시 함수를 만드는 가장 간단한 방식입니다. 함수의 형태는 다음과 같습니다.
h(k) = k mod n
여기서 h(k)는 키 값 k를 해시 테이블의 크기 n으로 나눈 나머지를 의미합니다. n을 소수(prime number)로 선택하면 키들이 해시 테이블 전체에 더욱 균일하게 분포되므로, 가능하면 소수를 사용하는 것이 좋습니다.
나눗셈 방법의 예시는 다음과 같습니다.
k = 1276
n = 10
h(1276) = 1276 mod 10
= 6계산 결과 해시 값은 6입니다.
다만 나눗셈 방법에는 단점이 있습니다. 연속된 키들이 해시 테이블에서도 연속된 해시 값으로 매핑되어 특정 영역에 데이터가 몰릴 수 있으며, 이는 성능 저하로 이어질 수 있습니다.
2. 곱셈 방법(Multiplication Method)
곱셈 방법에서 사용되는 해시 함수는 다음과 같습니다.
h(k) = floor( n × ( kA mod 1 ) )
여기서 k는 키이고, A는 0과 1 사이의 임의의 상수입니다. 키 k와 상수 A를 곱한 뒤 그 결과의 소수 부분(fractional part)만 분리하고, 여기에 테이블 크기 n을 곱하여 최종 해시 값을 구합니다.
곱셈 방법의 예시는 다음과 같습니다.
k = 123
n = 100
A = 0.618033
h(123) = 100 × (123 × 0.618033 mod 1)
= 100 × (76.018059 mod 1)
= 100 × 0.018059
= 1계산 결과 해시 값은 1입니다.
곱셈 방법의 장점은 어떤 값의 A를 사용해도 동작한다는 점입니다. 물론 황금비(0.618033...)처럼 특정 값이 더 균일한 분포를 만든다는 연구 결과도 알려져 있습니다.
3. 중간 제곱 방법(Mid Square Method)
중간 제곱 방법은 매우 효율적인 해시 함수로 평가받는 기법입니다. 먼저 키 값을 제곱한 후, 그 결과에서 중간 r자리 숫자를 추출하여 해시 값으로 사용합니다. r의 값은 해시 테이블의 크기에 따라 결정됩니다.
중간 제곱 방법의 예시는 다음과 같습니다.
해시 테이블이 100개의 메모리 위치를 가지고 있다면, 두 자리 숫자로 모든 위치를 매핑할 수 있으므로 r = 2가 됩니다.
k = 50 k × k = 2500 h(50) = 50
계산 결과 해시 값은 50입니다.
해시 테이블(Hash Tables)
해시 테이블은 키(key)를 값(value)에 매핑하는 자료구조입니다. 내부적으로 해시 함수를 사용하여 데이터 키의 저장 위치(인덱스)를 계산하고, 해당 인덱스에 키를 저장합니다. 덕분에 평균적으로 O(1)의 시간 복잡도로 빠른 검색, 삽입, 삭제가 가능합니다.
해시 테이블에 저장할 키 시퀀스는 다음과 같습니다.
35 50 11 79 76 85
이때 사용되는 해시 함수 h(k)는 다음과 같습니다.
h(k) = k mod 10
각 키를 해시 함수에 적용하면 서로 다른 키가 같은 인덱스를 가리키는 충돌(collision)이 발생할 수 있습니다. 이러한 충돌을 해결하기 위해 선형 탐사(linear probing) 기법을 사용하며, 충돌이 발생하면 바로 다음 빈 슬롯을 찾아 값을 저장합니다.
선형 탐사를 적용한 결과, 위의 키들은 해시 테이블에 다음과 같이 저장됩니다.
- 35 → 35 mod 10 = 5 → 인덱스 5에 저장
- 50 → 50 mod 10 = 0 → 인덱스 0에 저장
- 11 → 11 mod 10 = 1 → 인덱스 1에 저장
- 79 → 79 mod 10 = 9 → 인덱스 9에 저장
- 76 → 76 mod 10 = 6 → 인덱스 6에 저장
- 85 → 85 mod 10 = 5 → 충돌 발생! 인덱스 5가 이미 차 있으므로 다음 빈 슬롯인 인덱스 7에 저장
이처럼 해시 테이블은 해시 함수와 충돌 해결 기법을 조합하여 대량의 데이터를 효율적으로 관리할 수 있는 강력한 자료구조입니다. 데이터베이스 인덱싱, 캐시 구현, 사전(Dictionary) 자료형 등 다양한 분야에서 폭넓게 활용되고 있습니다.