해싱으로 데이터 접근 경로를 설계하는 법

키에서 저장 위치로 바로 가는 방식

해싱은 키값으로 레코드의 주소를 계산하고, 그 주소를 통해 데이터에 직접 접근하는 기법이다. 순차 검색이나 이진 검색과 달리 해시 테이블은 평균적으로 조회·삽입·삭제를 O(1) 시간 복잡도로 처리한다. 대량의 레코드에서 특정 키를 빠르게 찾아야 할 때 이 특성이 핵심이 된다.

해시 테이블을 이루는 단위

해시 함수는 키값을 입력받아 물리적 주소로 매핑한다. 계산이 빨라야 하고, 키가 가능한 한 균등하게 퍼지며, 충돌이 적어야 한다. 동일한 입력에는 항상 같은 결과를 내는 결정성도 필요하다.

해시 키는 주소 계산에 쓰는 레코드의 키값이다. 주민등록번호, 학번, 이메일 주소처럼 레코드를 식별하는 값이 여기에 해당한다.

버켓은 하나의 주소에 대응하는 파일 구역으로, 하나 이상의 레코드를 담을 수 있다. 슬롯은 그 버켓 안에서 레코드 하나를 저장하는 공간이다. 버켓에는 여러 슬롯이 존재할 수 있다.

이 요소들을 묶는 해시 테이블은 키를 값에 연결하는 자료구조이며, 연관 배열을 구현하는 방식 중 하나다.

주소 계산 뒤의 데이터 접근

⤢✕

키값을 해시 함수에 넣으면 해시 주소가 계산된다. 이후 그 주소가 가리키는 해시 테이블 위치로 이동해 저장된 레코드를 찾는다. 검색 과정의 비교 횟수를 줄이는 대신, 같은 주소를 얻는 충돌을 다루는 설계가 필요하다.

충돌이 발생했을 때의 선택지

서로 다른 키가 같은 해시 값을 만들면 해시 충돌이 발생한다. 충돌 자체를 완전히 없앨 수는 없으므로, 테이블의 특성과 데이터 분포에 맞는 처리 방식을 선택해야 한다.

체이닝으로 같은 버켓을 연결하기

체이닝은 같은 버켓에 들어온 여러 키-값 쌍을 연결 리스트로 보관하는 방식이다. 구현이 단순하고 테이블이 가득 차는 문제가 없지만, 최악의 경우 O(n) 시간 복잡도를 가질 수 있다.

⤢✕

빈 슬롯을 찾아 저장하는 개방 주소법

개방 주소법은 충돌이 나면 테이블 안의 다른 빈 슬롯을 찾아 항목을 저장한다. 선형 조사법은 다음 슬롯을 순차적으로 확인하고, 이차 조사법은 제곱수만큼 떨어진 슬롯을 검사한다. 이중 해싱은 두 번째 해시 함수로 건너뛸 간격을 정한다.

⤢✕

테이블을 다시 구성하는 재해싱

재해싱은 해시 테이블의 크기를 늘린 뒤 모든 키-값 쌍을 새 테이블에 다시 배치하는 방식이다. 로드 팩터(load factor)가 특정 임계값을 넘었을 때 수행하며, 공간 효율성과 성능의 균형을 맞추는 데 쓰인다.

빈 슬롯이 사라진 상태

오버플로우는 해시 테이블에 더 이상 빈 슬롯이 없는 과잉 상태다. 새 데이터를 삽입하려면 별도의 오버플로우 영역에 데이터를 두거나, 버켓 크기를 동적으로 늘리거나, 더 큰 테이블을 만들어 재해싱해야 한다.

인덱스, 무결성 검증, 분산 배치에 쓰이는 해싱

데이터베이스에서는 빠른 레코드 검색을 위해 해시 인덱스를 사용한다. 특히 동등 조건 검색(equal search)에 적합하며, MySQL의 MEMORY 스토리지 엔진의 해시 인덱스가 예시다.

보안 영역의 암호학적 해시 함수는 원본 데이터를 복원할 수 없는 단방향 함수다. 데이터 무결성 검증에 활용하며 MD5, SHA-1, SHA-256, SHA-3 등이 있다. 전자서명에서는 전체 메시지 대신 해시값을 암호화해 메시지 인증과 무결성 검증을 수행한다.

⤢✕

자료구조에서는 해시 테이블, 해시 맵, 해시 셋이 대표적이다. 블룸 필터(Bloom Filter)는 원소 존재 여부를 확률적으로 판단하는 자료구조다.

분산 시스템에서는 일관된 해싱(Consistent Hashing)으로 노드 추가·제거에 따른 데이터 재배치를 최소화할 수 있다. 데이터 샤딩(Sharding)은 대규모 데이터를 여러 서버에 나누어 저장하고, 부하 분산(Load Balancing)은 요청을 여러 서버에 균등하게 배분한다.

키를 주소로 바꾸는 해시 함수

제산법(Division Method)은 키를 테이블 크기로 나눈 나머지를 주소로 사용한다. 계산은 단순하고 빠르지만 테이블 크기 선택이 중요하며, 소수를 사용하는 것이 좋다.

h(k) = k mod m에서 m은 테이블 크기다.

중간 제곱법(Mid-square Method)은 키를 제곱한 뒤 중간 비트를 추출한다. 키의 모든 부분이 해시값에 영향을 주지만 계산 비용이 높고 일부 비트만 사용한다.

h(k) = (k² >> r) & m에서 r은 오른쪽 시프트 비트 수, m은 마스크다.

폴딩법(Folding Method)은 키를 여러 부분으로 나누어 합산한다. 긴 키에 효과적이지만 패턴이 있는 키에는 취약할 수 있다.

곱셈법(Multiplication Method)은 키에 상수 A(0<A<1)를 곱한 뒤 소수 부분을 추출하고 테이블 크기를 곱한다. 테이블 크기에 덜 의존하지만 나눗셈보다 느릴 수 있다.

h(k) = ⌊m(kA mod 1)⌋

성능을 좌우하는 테이블 상태

로드 팩터는 해시 테이블이 얼마나 채워졌는지를 나타내며, 항목 수를 테이블 크기로 나눈 값이다. 키 분포를 고르게 만드는 해시 함수의 품질, 체이닝과 개방 주소법 중 어떤 충돌 처리 전략을 택하는지, 테이블 크기를 어떻게 정하는지도 성능에 영향을 준다. 테이블 크기에 소수를 선택하면 충돌 가능성을 줄일 수 있다.

로드 팩터에 따라 테이블 크기를 동적으로 조정하고, 여러 해시 함수를 조합해 충돌을 줄일 수 있다. 자주 접근하는 항목은 캐시하며, 대용량 해시 테이블에는 병렬 접근을 구현하는 방법도 있다.