|
|
|
|
|
 |
|
[발표과제] 해싱 함수의 종류에 대해 조사해보자
|
|
|
 |
해싱 함수의 종류에 대해 조사해보자
해싱함수란
레코드 키(key)들의 집합을 버켓(Bucket)주소의 집합에 대응시킨다는 의미에서사상함수(mapping function)라고도 한다. 가장 이상적인 해싱 함수는 키 집합의한 레코드(record)와버켓 주소 집합의 한 레코드가 1:1 대응하여 해시 테이블의 정해진 범위에 고르게 분포되어 있어서 충돌을 최소화 하도록 하는 것이다.
그림으로 본 해싱함수
해싱 함수(Hashing function) -레코드 키값(k) → 해싱 함수 h(k)→ 해상표의 상대주소
책에 있는내용1
1)제산잔여해싱(divide and remainder)
*주소수보다 작고 제일큰 Prime number 로 나눈다.
2)중간제곱해싱(mid-square)
*제곱후 가운데 자리수 추출
3)중첩해싱(folding)
*숫자를 접어서 더 한후 접은 자리수 만큼 추출
책에 있는 내용 2
4)숫자추출방법(digit extraction)
의미 있다고 판단되는 몇가지 자리수만 추출하는 방법(예 학번,주민등록번호)
5)숫자이동변환(shifting)
중앙을 중심으로 주소길이만큼 나눈 후 좌우를 각각 시프트 시켜서 더하는 방법
6)진수변환(radix conversion)
키값을 다른진수로 변환 주소자리만큼 추출.
대수적 코딩(algebraic coding )
Is)키의 구성하는 각 자리의 비트 수를 다항의 계수로 간주하고, 해시 표에서 크기로 정한 다항식으로 나누어 나머지를 주소 값으로 하는 방법.
예)데이터 통신에서 CRC발생기와 같은 원리로 이해됨. 다른점은 나머지가 주소임.
001= (111101)mod(1101)
2진나눗셈의 예 (데이타통신책)
Pseudo Random(가 랜덤)
Is)난수를 발생하여 주소 를 정함 충돌이 발생할 경우 다음 난 수를 발생하여 주소를 정한다.
난 수에 적당한 상수를 곱해서 주소 값을 정할 수 있다.
참고)GPS나 위성에 사용한다고 한다.
유니버셜 해싱
.... |
|
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
2011.04.08
51페이지
