정적해싱의 버킷 구조와 충돌 처리 방식

키에서 저장 위치까지 연결하는 고정 버킷 구조

정적해싱은 데이터베이스 시스템과 파일 구조에서 사용하는 검색 기법이다. 키 값을 해시 함수에 전달해 데이터가 들어갈 버킷 주소를 정하고, 그 주소가 실제 저장 위치를 가리킨다. 버킷은 하나 이상의 레코드를 담는 물리적 공간 단위다.

⤢✕

해시 테이블의 버킷 수는 처음 정한 뒤 바뀌지 않는다. 따라서 현재 파일 크기를 바탕으로 해시 함수를 선택하게 되며, 파일이 커지면 해싱 구조 전체를 다시 구성해야 할 수 있다.

키를 버킷 주소로 바꾸는 방식

MidSquare 방식

키 값을 제곱하고 그 결과의 중간 비트를 꺼내 버킷 주소로 쓴다.

예시:
키 값 = 3742
제곱 = 14,002,564
중간 4자리 추출 = 0025
버킷 주소 = 25

Division 방식

키를 소수(prime number)로 나눈 나머지를 주소로 사용한다. 소수를 선택하면 충돌 가능성을 줄일 수 있다.

예시:
키 값 = 8675
나누는 소수 = 101
버킷 주소 = 8675 % 101 = 66

Folding 방식

키를 같은 길이의 부분으로 나누고, 각 부분을 더해 주소를 만든다.

예시:
키 값 = 123456789
분할 (3자리씩) = 123, 456, 789
합 = 123 + 456 + 789 = 1368
버킷 주소 = 1368 또는 1368 % 테이블크기

같은 주소를 가리킬 때 생기는 문제

서로 다른 키가 동일한 해시 주소로 변환되면 충돌(Collision)이 발생한다. 해시 함수가 서로 다른 입력에 대해 같은 출력을 낸 경우다.

⤢✕

오버플로우(Overflow)는 이미 가득 찬 버킷에 새 데이터를 넣어야 할 때 발생한다. 정적해싱에서는 버킷 수가 고정돼 있으므로, 이 상황을 처리할 방법을 미리 정해야 한다.

버킷이 찼을 때의 처리 선택지

선형 검색법(Linear Method)

오버플로우가 나면 주소 + 1의 다음 버킷부터 빈 자리를 순서대로 찾는다.

⤢✕

구현은 단순하지만 군집화(clustering)가 생길 수 있다.

2차 검색법(Quadratic Probing)

충돌 뒤에는 1², 2², 3², ...만큼 떨어진 위치를 차례로 확인한다.

초기 해시 주소 = h
충돌 발생 시 검색 순서: h+1², h+2², h+3², ...

선형 검색법보다 군집화가 덜할 수 있지만, 2차 군집화 현상은 남는다.

재해싱(Re-Hashing)

오버플로우가 해소될 때까지 여러 해시 함수를 적용하는 방법이다.

⤢✕

데이터를 더 고르게 분포시킬 수 있지만, 여러 해시 함수를 계산하는 오버헤드가 늘어난다.

무작위 검색법(Random Method)

난수 생성기로 다음 버킷 주소를 정한다. 군집화는 줄일 수 있으나 이미 확인한 버킷을 다시 확인할 가능성이 있다.

체인 이용법(Chaining)

버킷마다 연결 리스트(Linked List)를 두고, 오버플로우가 발생한 데이터를 리스트에 연결한다.

⤢✕

버킷 수의 제한 없이 데이터를 저장할 수 있는 대신, 추가 메모리와 포인터 연산이 필요하다.

정적해싱이 쓰이는 자리

정적해싱은 DBMS가 데이터 레코드에 빠르게 접근하는 인덱싱, 웹 서버나 데이터베이스 서버의 메모리 캐시, 컴파일러와 인터프리터의 심볼 테이블에 활용된다. 프로그래밍 언어의 Dictionary와 HashMap 같은 자료구조 구현에도 이 개념이 적용된다.

성능을 좌우하는 조건

로드 팩터(Load Factor)는 해시 테이블 항목 수를 버킷 수로 나눈 값이며, 일반적으로 0.7~0.8이 최적의 성능을 제공한다. 키를 버킷에 균등하게 분산시키는 해시 함수인지, 어떤 충돌 및 오버플로우 해결 방식을 쓰는지도 검색 성능에 영향을 준다.

평균 시간 복잡도는 삽입, 검색, 삭제 모두 O(1)이다. 충돌이 집중되는 최악의 경우에는 각각 O(n)이 될 수 있다.

버킷 수가 변하는 해싱과의 차이

특성	정적해싱	동적해싱
버킷 수	고정	가변적(필요에 따라 증가)
재구성	전체 재구성 필요	부분적 재구성 가능
성능	로드 팩터에 민감	로드 팩터에 덜 민감
구현 복잡성	상대적으로 간단	복잡함
공간 효율성	처음에 큰 공간 할당 필요	필요에 따라 공간 할당

동적해싱(Dynamic Hashing)은 정적해싱의 한계를 보완하기 위해 개발됐다. 데이터 양의 변화가 큰 환경이라면 버킷을 유연하게 늘릴 수 있는 구조가 더 적합할 수 있다.

운영 시 확인할 기준

예상 데이터 양의 1.3~1.5배 정도로 초기 버킷을 할당하고, 데이터 특성에 맞는 해시 함수를 선택한다. 데이터 접근 패턴에 따라 충돌 해결 전략을 정하며, 로드 팩터가 임계값을 넘으면 재해싱을 수행한다. 고정된 구조의 단순성을 택할지, 데이터 증가에 따른 재구성 비용을 감수할지에 따라 정적해싱의 적합성이 달라진다.