정적 해싱: 고정 버킷에서 충돌과 로드 팩터를 다루는 법

고정된 버킷으로 키를 빠르게 찾는 구조

해싱은 길이가 제각각인 데이터를 고정 길이의 값으로 매핑하는 과정이다. 정적 해싱은 이 결과를 담을 버킷 수를 처음부터 고정해 둔 해시 테이블 방식이다. 데이터베이스 인덱스, 캐시, 메모리 관리처럼 키 기반 탐색이 필요한 곳에서 쓰이며, 검색 성능을 O(1)에 가깝게 만드는 핵심 자료구조다.

테이블은 해시 함수, 버킷, 슬롯으로 나뉜다. 해시 함수는 키를 테이블 주소로 바꾸고, 버킷은 데이터를 보관하는 단위이며, 슬롯은 버킷 안에서 레코드가 실제로 놓이는 자리다. 주소는 0부터 (버킷 수 - 1) 범위에 있다.

⤢✕

해시 함수가 분포를 결정한다

좋은 해시 함수는 계산이 빨라야 하고, 데이터가 특정 버킷에 몰리지 않도록 균등하게 분포시켜야 한다. 서로 다른 키가 같은 해시 값을 갖는 충돌도 가능한 한 줄여야 한다.

나누기 방법은 h(k) = k mod m으로 계산한다. 구현은 단순하지만 균등 분포를 보장하기 어렵고, m에 소수(prime number)를 사용하면 성능이 향상된다.

곱하기 방법은 h(k) = ⌊m(kA mod 1)⌋을 사용한다. A는 0과 1 사이의 상수이며 보통 황금비 0.618...을 쓴다. 키 값의 분포에 덜 민감하다는 장점이 있다.

폴딩 방법은 키를 여러 부분으로 나눈 뒤 연산 결과를 조합한다. 이동 폴딩(Shift Folding)은 나눈 부분을 더하고, 경계 폴딩(Boundary Folding)은 일부를 뒤집어 더한다. 중간 제곱법(Mid-Square Method)은 키를 제곱한 뒤 중간 비트를 가져오며, h(k) = 제곱값의 중간 r비트로 표현한다.

충돌이 생겼을 때 선택할 방식

서로 다른 키가 같은 해시 주소를 얻는 충돌은 정적 해싱에서 피할 수 없는 문제다. 보통 개방 주소법과 체이닝 중 하나로 처리한다.

개방 주소법은 테이블 안에서 빈 자리를 찾는다

개방 주소법(Open Addressing)은 충돌이 발생하면 다른 버킷을 찾아 데이터를 저장한다. 별도 오버플로우 영역은 필요 없지만, 삭제할 때는 tombstone 같은 특별한 처리가 필요하다.

선형 조사법(Linear Probing)은 충돌 뒤 다음 버킷을 순서대로 확인한다. 계산식은 h'(k, i) = (h(k) + i) mod m이며, i는 조사 횟수다. 구현은 간단하지만 인접한 항목이 몰리는 군집화(Clustering)가 생길 수 있다.

⤢✕

이차 조사법(Quadratic Probing)은 제곱 간격으로 다음 버킷을 확인한다. h'(k, i) = (h(k) + c₁i + c₂i²) mod m을 사용하며, 일차 군집화는 해결하지만 이차 군집화가 발생할 수 있다.

이중 해싱(Double Hashing)은 해시 함수 두 개를 사용한다. h'(k, i) = (h₁(k) + i·h₂(k)) mod m으로 주소를 구하며, 군집화를 최소화하는 가장 효과적인 개방 주소법이다.

체이닝은 같은 주소의 레코드를 연결한다

체이닝(Chaining)은 같은 해시 값을 받은 레코드를 연결 리스트로 관리한다. 버킷 오버플로우 문제를 해결할 수 있지만 포인터 공간을 위한 추가 메모리가 든다.

⤢✕

로드 팩터가 성능의 경계가 된다

충돌이 없을 때 정적 해싱의 탐색은 O(1)이다. 키가 균등하게 분포한다는 가정에서도 평균 시간 복잡도는 O(1)이며, 모든 키가 같은 버킷으로 해싱되는 최악의 경우에는 O(n)까지 떨어질 수 있다.

로드 팩터는 α = n/m으로 계산한다. 여기서 n은 항목 수, m은 버킷 수다. 일반적으로 α ≤ 0.7~0.8을 유지하는 것이 권장된다. 체이닝의 평균 탐색 시간은 1 + α/2이고, 개방 주소법의 평균 탐색 시간은 1/(1-α)이다.

버킷 수가 정해져 있다는 점은 확장성의 한계가 된다. 데이터가 늘수록 성능은 저하되고, 로드 팩터가 높아지면 재해싱(Rehashing)이 필요하다. 재해싱은 전체 테이블을 다시 구성하므로 비용이 크며, 실시간 시스템에서는 성능 저하 요인이 될 수 있다.

데이터 규모와 운영 제약에 맞춰 고르기

해시 인덱스는 동등 검색(Equality Search)에 최적화되어 있고, MySQL의 MEMORY 스토리지 엔진에서도 사용된다. Memcached와 Redis 같은 메모리 캐시는 빠른 키-값 검색과 웹 서버 세션 관리에 활용한다. 컴파일러의 심볼 테이블은 변수와 함수명을 관리하며, 네트워크 라우팅 테이블은 IP 주소를 바탕으로 빠르게 경로를 결정한다.

정적 해싱과 동적 해싱의 차이는 버킷을 늘릴 수 있는지에 있다.

특성	정적 해싱	동적 해싱
버킷 수	고정	가변
확장성	제한적	우수
구현 복잡도	낮음	높음
성능 안정성	로드 팩터에 의존	상대적 안정
공간 효율성	사전 크기 결정 필요	필요에 따라 확장
대표 알고리즘	기본 해싱	선형 해싱, 확장 해싱

초기 크기는 예상 데이터 량의 1.3~1.5배로 잡고, 소수(prime number) 크기를 사용하는 방식을 고려할 수 있다. 해시 함수와 충돌 해결 방식도 데이터 특성에 맞춰야 한다. 메모리 제약이 적다면 체이닝을, 메모리 효율이 더 중요하다면 개방 주소법을 선택할 수 있다. 로드 팩터 임계값을 정하고 점진적 재해싱도 검토 대상이다.

고정 구조의 약점을 보완하는 해싱 기법

로빈 후드 해싱(Robin Hood Hashing)은 각 키의 이상적 위치와 현재 위치의 차이를 줄이는 전략이다. 쿠쿠 해싱(Cuckoo Hashing)은 여러 해시 함수를 사용하며, 최악의 경우에도 O(1) 룩업을 보장하고 로드 팩터 제한은 ~50%이다. 홉스코치 해싱(Hopscotch Hashing)은 개방 주소법과 체이닝의 장점을 결합해 지역성을 보존하고 캐시 효율성을 높인다.

정적 해싱은 구현이 단순하고 성능을 예측하기 쉬워 데이터 크기를 예상할 수 있는 환경에 적합하다. 다만 대용량 데이터처럼 확장성이 중요한 상황에서는 동적 해싱을 고려해야 하며, 해시 함수와 충돌 해결 방식의 선택이 성능을 좌우한다.