해시 함수 설계 (Hash Function Design)

해시 함수 설계 (Hash Function Design)

임의 크기의 입력(키)을 고정 크기의 해시 값(인덱스)으로 변환하는 함수로, 해시 테이블의 성능은 해시 함수의 품질에 직접 의존

좋은 해시 함수 조건: ① 균등 분포(Uniform Distribution) ② 빠른 계산(O(1)) ③ 결정적(Deterministic) ④ 눈사태 효과(입력 1비트 변화 → 출력 절반 변화)

나눗셈법 (Division Method)

• •h(k) = k mod m, m은 테이블 크기
• •m 선택: 2의 거듭제곱 피하기(하위 비트만 사용), 소수(prime) 권장
• •장점: 단순, 빠름 / 단점: m 선택에 민감

곱셈법 (Multiplication Method)

• •h(k) = ⌊m × (k × A mod 1)⌋, 0 < A < 1 (Knuth 권장: A ≈ (√5-1)/2 ≈ 0.6180)
• •m 선택에 덜 민감, 균등 분포 우수
• •장점: m에 독립적 / 단점: 부동소수점 연산 필요

유니버설 해싱 (Universal Hashing)

• •해시 함수 집합 H에서 무작위 선택, 최악 케이스를 확률적으로 방지
• •임의의 두 키 x ≠ y에 대해 Pr[h(x) = h(y)] ≤ 1/m
• •h(k) = ((a×k + b) mod p) mod m, p는 큰 소수, a∈{1,...,p-1}, b∈{0,...,p-1}
• •장점: 적대적 입력에도 기대 성능 O(1) 보장

암호학적 해시와의 차이

• •해시 테이블 해시: 빠른 계산 우선, 역상 저항 불필요, 균등 분포 중시
• •암호학적 해시(SHA-256 등): 역상 저항, 충돌 저항, 속도 느림, 보안 목적

비교: 나눗셈법(단순/m의존) vs 곱셈법(m독립/부동소수점) vs 유니버설(확률적최적/복잡)

연관: 해시 테이블, 해시 충돌, 균등 분포, 암호학적 해시, Bloom Filter