해시 함수 (Hash Function)

지난 글에서 해시 테이블의 구조와 충돌 해결 전략을 다뤘습니다. 이번에는 해시 테이블의 성능을 결정하는 핵심 부품인 해시 함수(Hash Function)를 깊이 살펴봅니다. 해시 함수가 어떤 조건을 갖춰야 하는지, 문자열 해싱은 어떻게 동작하는지, 그리고 Python이 왜 SipHash를 사용하는지 이해하면 해시 테이블 관련 성능 이슈를 훨씬 명확하게 파악할 수 있습니다.

해시 함수의 역할

해시 함수 h는 임의 크기의 데이터(키)를 고정 크기 정수(해시값)로 변환합니다.

h: key → integer

해시 테이블에서는 인덱스 = h(key) % capacity로 저장 위치를 결정합니다.

좋은 해시 함수의 조건

1. 결정론적: 같은 입력은 항상 같은 출력
2. 균등 분포: 해시값이 버킷에 고르게 분포해 충돌 최소화
3. 빠른 계산: 해시 계산 자체가 병목이 되면 안 됨
4. 눈사태 효과: 입력 1비트 변화로 출력 비트의 ~50%가 변해야 유사한 키의 충돌 방지

문자열 해시 함수 — 다항식 해싱

가장 흔한 방법입니다. 각 문자의 ASCII 값에 가중치를 곱해 합산합니다.

def poly_hash(s: str, p: int = 31, M: int = 10**9 + 7) -> int:
    """호너의 방법으로 O(n) 다항식 해싱"""
    h = 0
    for c in s:
        h = (h * p + ord(c)) % M
    return h

print(poly_hash("hello"))   # 안정적인 정수
print(poly_hash("hellp"))   # 완전히 다른 값 (눈사태 효과)

소수 p의 선택

• 소수를 사용하면 해시값이 더 고르게 분포됩니다.
• p = 31: 소문자 영문자 (26개)보다 큰 소수
• p = 53: 대소문자 영문자 (52개)보다 큰 소수

롤링 해시 (Rolling Hash)

슬라이딩 윈도우에서 창을 한 칸 이동할 때 O(1)에 해시를 재계산합니다.

def rolling_hash(s: str, k: int, p: int = 31, M: int = 10**9 + 7):
    """길이 k의 윈도우를 이동하며 해시값 생성"""
    h = 0
    p_k = pow(p, k, M)   # p^k mod M

    # 첫 번째 창
    for c in s[:k]:
        h = (h * p + ord(c)) % M
    yield h

    for i in range(k, len(s)):
        # 새 문자 추가, 오래된 문자 제거
        h = (h * p - ord(s[i - k]) * p_k + ord(s[i])) % M
        yield h

비암호학적 해시 함수

빠른 속도가 목적이며 보안이 필요 없는 경우에 사용합니다.

FNV-1a

def fnv1a_32(data: bytes) -> int:
    FNV_PRIME = 0x01000193
    FNV_OFFSET = 0x811c9dc5
    h = FNV_OFFSET
    for byte in data:
        h ^= byte
        h = (h * FNV_PRIME) & 0xFFFFFFFF
    return h

print(fnv1a_32(b"hello"))  # 0x4f9f2cab

MurmurHash3 (개념)

# 실제 사용 시 mmh3 라이브러리 활용
import mmh3
print(mmh3.hash("hello", seed=42))   # 빠른 128-bit 해시

암호학적 해시 함수

역산 불가능, 충돌 저항이 핵심입니다. 보안 목적(패스워드, 전자서명, 무결성 검증)에 사용합니다.

import hashlib

# SHA-256 — 256비트 해시
sha = hashlib.sha256(b"hello").hexdigest()
print(sha)  # 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

# bcrypt — 패스워드 해싱 (해시 시간을 의도적으로 느리게)
import bcrypt
pw = b"my_secret_password"
hashed = bcrypt.hashpw(pw, bcrypt.gensalt(rounds=12))
print(bcrypt.checkpw(pw, hashed))   # True

Python hash()와 HashDoS 방어

Python 3.3+에서 hash()는 SipHash-1-3을 사용합니다.

# PYTHONHASHSEED: 프로세스마다 다른 랜덤 시드 (기본값 = 무작위)
# 같은 키도 실행마다 해시값이 다름 → HashDoS 공격 방어
print(hash("hello"))   # 실행마다 다름

# 불변 타입만 해시 가능
print(hash(42))        # 42 (정수 해시 = 값 자체)
print(hash(3.14))      # 고정값
print(hash((1, 2)))    # 튜플 해시
# hash([1, 2])         # TypeError — 가변 타입 불가

HashDoS 공격: 해시 함수가 고정 시드라면 공격자가 의도적으로 같은 버킷에 충돌하는 키를 대량 삽입해 O(1) 해시 테이블을 O(n²)으로 만들 수 있습니다. 무작위 시드가 이를 방어합니다.

커스텀 객체의 해시

Python에서 커스텀 클래스를 dict 키로 사용하려면 __hash__와 __eq__를 함께 정의해야 합니다.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        # 불변 값의 튜플로 해시 위임 — 안전하고 간단
        return hash((self.x, self.y))

p1 = Point(1, 2)
p2 = Point(1, 2)
print(p1 == p2)              # True
print(hash(p1) == hash(p2))  # True (같은 해시값)

d = {p1: "origin"}
print(d[p2])                  # "origin" — 동일 키로 인식

정리

• 좋은 해시 함수는 결정론적, 균등 분포, 빠른 계산, 눈사태 효과를 갖춰야 합니다.
• 문자열 해싱에는 다항식 해싱(p=31, M=10⁹+7)이 실용적입니다.
• 보안 목적에는 SHA-256 등 암호학적 해시, 성능 목적에는 MurmurHash/FNV를 사용합니다.
• Python hash()는 SipHash로 HashDoS를 방어하며, 가변 타입은 해시 불가입니다.

---

지난 글: 해시 테이블

다음 글: 충돌 해결 — 분리 체이닝 (Collision Resolution: Separate Chaining)

읽어주셔서 감사합니다. 😊