728x90
반응형
SMALL
- 개념
- 키 값으로부터 저장 주소를 직접 계산해 즉시 접근하는 방법.
- 매우 빠른 검색이 장점이지만, 충돌(collision) 해결이 반드시 필요.
1) 제산 방법 (나눗셈법, Division/Modulo)
- 정의: 키를 테이블 크기 m으로 나눈 나머지를 주소로 사용 → h(k) = k mod m
- 팁: m은 소수 사용 권장(패턴 충돌 완화)
- 예시: k=202, m=101 → h=0
2) 중간 제곱법 (Mid-Square)
- 정의: 키를 제곱한 뒤 중간 자리/비트를 취해 주소로 사용
- 장점: 키 분포가 고르지 않아도 중간 비트가 섞여 분산 효과
- 예시: k=123 → k^2=15129 → ‘512’ 사용 → (512 mod m)
3) 중첩 방법(폴딩법, Folding)
- 정의: 키를 일정 길이 블록으로 쪼개 더하거나(XOR) 결합한 뒤 주소로 사용
- 예시: 12345678 → 1234 + 5678 = 6912 → (6912 mod m)
4) 기수 변환법 (Radix Conversion)
- 정의: 키를 다른 진법으로 해석/변환하여 주소 생성
- 용도: 문자열/복합키를 숫자로 바꿀 때 유용
- 예시: 문자열 ‘ABC’를 36진수로 변환 → 정수값 → (정수 mod m)
5) 계수 분석 방법 (다항/폴리노미얼 해싱, Polynomial/Rolling)
- 정의: 키(특히 문자열)를 다항식으로 보고 계수 누산
- h(s) = (c0*b^(n-1) + c1*b^(n-2) + … + cn-1) mod m
- 장점: 문자열에 균등 분포, 롤링 해시 등에 활용
- 예시: b=31, m=1e9+7로 문자코드 누산
6) 무작위 방법 (무작위/유니버설 해싱)
- 정의: 무작위 계수/함수를 사용해 해시 함수를 확률적으로 선택
- 장점: 특정 입력에 대한 최악의 충돌 공격 완화
- 예시: h_{a,b}(k) = ((a*k + b) mod p) mod m (a,b 무작위, p는 큰 소수)
728x90
반응형
LIST