해시 테이블과 충돌 처리 | SW 전공

1. 해시 테이블

해시 테이블은 키를 해시 함수에 넣어 얻은 인덱스에 데이터를 저장한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

index = h(key)

이상적인 경우 삽입·탐색·삭제의 평균 시간은 O(1)이다. 하지만 서로 다른 키가 같은 인덱스를 만들면 충돌(collision)이 발생한다.

좋은 해시 함수는 다음 성질을 가진다.

적재율 α는 저장 원소 수 n을 버킷 수 m으로 나눈 값이다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

α = n / m

적재율이 높아질수록 충돌 가능성과 탐색 시간이 증가한다. 임계값을 넘으면 더 큰 테이블을 만들고 모든 키를 다시 배치하는 재해싱(rehashing)을 수행할 수 있다.

각 버킷이 연결 리스트 등 별도 구조를 가리키도록 한다. 같은 해시값의 원소를 한 버킷의 체인에 저장한다.

모든 원소를 해시 테이블 배열 안에 저장하고 충돌 시 다른 빈 칸을 찾는다.

선형 조사는 구현이 단순하지만 연속된 칸에 원소가 몰리는 1차 군집화가 발생할 수 있다. 삭제 시 단순히 빈 칸으로 만들면 탐색 연결이 끊길 수 있으므로 삭제 표시(tombstone)를 사용하는 구현이 많다.

테이블 크기가 7이고 h(k)=k mod 7일 때 키 10, 17, 24는 모두 인덱스 3을 만든다.

연산	평균	최악
탐색·삽입·삭제	O(1)	O(n)

최악의 경우는 모든 키가 같은 버킷으로 몰리거나 긴 조사 구간이 생기는 경우이다. 해시 테이블은 빠른 정확 일치 탐색에 적합하지만 정렬 순서나 범위 탐색에는 일반적으로 적합하지 않다.

정수 키에는 나눗셈법 h(k)=k mod m을 자주 사용한다. m을 2의 거듭제곱으로만 두면 키의 하위 비트 분포에 지나치게 의존할 수 있어, 문제 조건에 따라 소수 크기를 쓰기도 한다. 문자열은 각 문자를 누적하는 다항 해시를 사용할 수 있다.

PYTHON코드 영역 안에서 좌우로 이동할 수 있습니다.

def poly_hash(s, m, base=31):
    h = 0
    for ch in s:
        h = (h * base + ord(ch)) % m
    return h

암호학적 해시와 자료구조용 해시는 목적이 다르다. 자료구조용은 빠른 분산이 핵심이고, 암호학적 해시는 역상·충돌 공격 저항 같은 보안 성질이 추가로 필요하다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

선형 조사: h_i(k) = (h(k) + i) mod m
이차 조사: h_i(k) = (h(k) + c1·i + c2·i²) mod m
이중 해싱: h_i(k) = (h1(k) + i·h2(k)) mod m

이중 해싱에서 h2(k)와 테이블 크기 m이 서로소이면 모든 칸을 순회할 가능성을 확보할 수 있다.

크기 11, h(k)=k mod 11, 선형 조사로 22, 1, 13, 11, 24를 삽입한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

22 → 0
1  → 1
13 → 2  (13 mod 11=2)
11 → 3  (0,1,2 충돌)
24 → 4  (2,3 충돌)

연속된 군집이 길어질수록 새 키가 군집 끝에 붙는 1차 군집화가 심해진다.

개방주소법의 슬롯은 적어도 세 상태를 구분한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

EMPTY: 한 번도 사용하지 않음 → 탐색 종료 가능
OCCUPIED: 키가 있음
DELETED: 과거 사용 후 삭제 → 탐색은 계속, 삽입에는 재사용 가능

DELETED를 EMPTY로 바꾸면 충돌로 뒤에 저장된 키를 찾지 못할 수 있다. tombstone이 너무 많아져도 성능이 떨어지므로 재해싱으로 정리한다.

균등 해싱을 가정하면 체인의 평균 길이는 적재율 α=n/m 정도이다. 성공·실패 탐색 비용은 대략 O(1+α)로 해석한다. 개방주소법은 α<1이어야 하며 α가 1에 가까워질수록 조사 길이가 급격히 늘어난다.