해싱으로 키 기반 레코드 접근 설계하기

키에서 저장 위치를 계산하는 방식

해싱(Hashing)은 키값 K를 해시함수 h(K)에 넣어 고정 길이 해시값으로 바꾸고, 그 결과로 파일이나 메모리의 물리 주소인 버킷을 정해 레코드에 접근하는 기법이다. 주소는 보통 A = h(K) mod m 형태로 계산하며, 탐색·삽입·삭제를 평균 O(1) 시간에 처리한다.

해시 구조는 보안과 자료구조 양쪽에서 쓰인다. 전자서명과 부인방지, 해시 알고리즘에는 해시의 보안 성질이 필요하고, 해시 테이블에서는 키-값 데이터를 빠르게 찾기 위한 주소 계산이 중심이 된다.

해싱을 구성하는 단위는 다음과 같다.

해시함수는 키를 물리 주소로 매핑한다. 균등한 분포, 계산 비용, 충돌 최소화가 품질을 좌우한다.
해시키는 주소 계산에 사용하는 레코드의 키값이다.
버킷(Bucket)은 하나 이상의 레코드를 수용하는 주소 단위의 저장 구역이다.
슬롯(Slot)은 버킷 안에서 레코드 하나를 담는 최소 저장 단위다.

분포와 저장 구조가 성능을 좌우한다

키가 특정 값에 치우쳐 있으면 충돌이 늘어나므로, 해시함수는 균등 분포를 만들어야 한다. 키의 편향을 완화하는 혼합(mixing)과 모듈러 또는 비트마스킹 조합을 사용한다.

보안 해시와 인덱싱 해시는 목적이 다르다. SHA-2/3, BLAKE2/3 같은 보안 해시는 단방향성과 충돌저항성을 우선하지만, 인덱싱용 해시는 속도와 균등 분포를 우선한다. 단방향성(제1역상저항성), 제2역상저항성, 충돌저항성은 보안 해시에 필요한 성질이며, 인덱싱 해시의 필수 요건은 아니다.

버킷 크기와 슬롯 수를 정할 때는 캐시 친화성, 메모리 정렬, 디스크 페이지 크기를 함께 고려한다. 이는 I/O를 줄이고 캐시 적중률을 높이기 위한 선택이다. 버킷이 포화되면 개방 주소법이나 체이닝으로 충돌을 처리한다.

충돌과 오버플로를 다루는 선택지

정적 해싱은 충돌과 버킷 포화라는 한계를 가진다. 충돌이나 오버플로가 누적되면 평균 접근 시간이 늘어난다. 선형 탐사, 2차 탐사, 랜덤 탐사, 체이닝으로 이를 처리할 수 있으며, 확장 요구가 크면 Extendible Hashing이나 Linear Hashing 같은 동적 해싱을 고려한다.

전략	성능(평균)	확장성	일관성/클러스터링	안정성(오버플로)	운영 편의
선형 탐사	높음(α 낮을 때)	리사이즈 필요	1차 클러스터링 심화	테이블 포화에 취약	구현 단순
2차 탐사	높음	리사이즈 필요	1차 클러스터링 완화	포화 시 급격한 저하	구현 보통
랜덤 탐사	보통~높음	리사이즈 필요	클러스터링 최소화	탐사 길이 변동 큼	구현 보통
체이닝	높음(적절한 버킷)	체인 확장 용이	체인 길이 분산에 의존	오버플로를 체인으로 흡수	삭제/동시성 유리

개방 주소법은 메모리 지역성이 좋지만, 삭제 뒤 tombstone을 관리해야 한다. 체이닝은 메모리와 포인터 오버헤드가 있고, 고부하 상태에서는 체인이 길어져 O(1) 접근이 O(k)로 악화될 수 있다.

부하율은 α = 저장 요소 수 / 슬롯 수로 계산한다. 개방 주소법은 α가 0.7~0.8을 넘으면 성능이 급락하는 경향이 있다. 임계치를 넘으면 크기를 2배로 확장하고 재해싱한다. 동시성 환경에서는 버킷 또는 테이블 락과 단계적 리해시(incremental rehash)를 고려해야 한다.

해시 테이블의 처리 흐름

⤢✕

레코드를 찾지 못했거나 테이블이 포화됐거나 탐사가 실패하면 리사이즈와 재해싱을 트리거할 수 있다. 쓰기 작업은 버킷 또는 슬롯 단위 락을 사용하며, 장애가 나면 롤백과 재시도 로직을 적용한다.

보안과 시스템에서의 활용

전자서명과 부인방지에서는 메시지를 해시한 다이제스트에 개인키로 서명해 원문의 위·변조 탐지와 부인방지를 제공한다. 패스워드 저장에는 bcrypt, scrypt, Argon2 같은 느린 해시에 솔트를 적용해 무차별 대입 공격을 완화한다. 파일이나 아티팩트를 배포할 때 SHA-256 체크섬을 제공하면 전달 경로의 위·변조를 탐지할 수 있다.

자료구조와 시스템에서는 해시 테이블 기반 캐시가 LRU와 해시 인덱스를 결합해 평균 O(1) 접근을 제공한다. 데이터베이스 해시 인덱스는 정확 일치(equal) 질의를 최적화하며, 페이지 단위 버킷과 오버플로 체인을 관리해야 한다. 분산 시스템에서는 일관 해싱(Consistent Hashing)으로 노드 추가·제거 때 키 재분배를 최소화한다.

선형 탐사 해시 테이블 예제

이 예제는 Python 3.10+ 환경에서 단일 스레드를 가정한 교육용 단순화 구현이다.

# Python 3.10+
TOMBSTONE = object()

class HashTable:
    def __init__(self, capacity=8, load_factor=0.75):
        self.n = 0
        self.cap = capacity
        self.lf = load_factor
        self.keys = [None] * self.cap
        self.vals = [None] * self.cap

    def _idx(self, key):
        return (hash(key) & 0x7fffffff) % self.cap

    def _resize(self):
        old_keys, old_vals = self.keys, self.vals
        self.cap *= 2
        self.keys = [None] * self.cap
        self.vals = [None] * self.cap
        self.n = 0
        for k, v in zip(old_keys, old_vals):
            if k is not None and k is not TOMBSTONE:
                self.put(k, v)

    def put(self, key, val):
        if (self.n + 1) / self.cap > self.lf:
            self._resize()
        i = self._idx(key)
        first_tomb = None
        while True:
            if self.keys[i] is None:
                target = first_tomb if first_tomb is not None else i
                self.keys[target], self.vals[target] = key, val
                self.n += 1
                return
            elif self.keys[i] is TOMBSTONE:
                if first_tomb is None:
                    first_tomb = i
            elif self.keys[i] == key:
                self.vals[i] = val
                return
            i = (i + 1) % self.cap

    def get(self, key):
        i = self._idx(key)
        while self.keys[i] is not None:
            if self.keys[i] is not TOMBSTONE and self.keys[i] == key:
                return self.vals[i]
            i = (i + 1) % self.cap
        return None

    def delete(self, key):
        i = self._idx(key)
        while self.keys[i] is not None:
            if self.keys[i] is not TOMBSTONE and self.keys[i] == key:
                self.keys[i], self.vals[i] = TOMBSTONE, None
                self.n -= 1
                return True
            i = (i + 1) % self.cap
        return False

# 사용 예
ht = HashTable()
for k in ["a", "b", "c"]:
    ht.put(k, k.upper())
assert ht.get("b") == "B"
ht.delete("b")
assert ht.get("b") is None

이 구현은 평균 O(1) 접근을 목표로 하며, 부하율 임계치를 넘으면 2배 확장과 재해싱을 수행한다. 보안 해시와 달리 언어 내장 hash는 재현성이나 보안을 보장하지 않으므로, 저장소 키 안정성이 필요하면 별도 해시 함수를 사용해야 한다.

부하율 관리가 운영 안정성으로 이어진다

적합한 해시함수를 선택하고 α≤0.75를 유지하면 평균 접근 시간 O(1)을 달성할 수 있다. 인덱스 스캔과 비교하면 응답 지연을 5~20배 단축할 수 있으며, 이는 워크로드와 캐시 적중률에 의존한다.

체이닝은 오버헤드 10~30% 안에서 충돌을 흡수할 수 있다. 개방 주소법은 메모리 효율이 좋지만 리사이즈 비용이 발생한다. 부하율 모니터링과 단계적 재해싱은 피크 타임의 중단을 최소화하고, 장애 시 로그 기반 복구는 데이터 무결성을 유지하는 데 쓰인다.