[자료구조] 해싱

소개

1. 해싱의 개요 및 특성
2. 해싱함수
3. 해싱함수의 특성 및 용어
4. 제산법
5. 제곱법
6. 숫자 분석법
7. 폴딩법
8. 기수변환법
9. 무작위 방법
10. overflow의 해결
11. 선형검색법
12. 2차 검색법
13. 무작위 검색법
14. 체인이용법

목차

1. 해싱의 개요 및 특성
2. 해싱함수
3. 해싱함수의 특성 및 용어
4. 제산법
5. 제곱법
6. 숫자 분석법
7. 폴딩법
8. 기수변환법
9. 무작위 방법
10. overflow의 해결
11. 선형검색법
12. 2차 검색법
13. 무작위 검색법
14. 체인이용법

본문내용

1. 해싱의 개요 및 특성
Hashing은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다. 짧은 해시 키를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다.

또한 해싱에 의해 정렬된 이름들 각각은 데이터베이스 내에서 개인들 데이터의 키가 될 수 있다. 데이터베이스 검색 수법은 일치하는 것이 먼저 발견될 때까지 각 이름들을 글자단위로 확인하기 시작해야만 한다. 그러나, 만약 이름들 각각이 해시된다면, 각 이름별로 4자리의 고유한 키를 생성하는 것이 가능해진다. 예를 들면 다음과 같다.


Abernathy, Sara
Epperdingle, Roscoe
Moore, Wilfred
Smith, David
(그리고 더 많은 수의 데이터가 알파벳 순으로 정렬되어 있다).
7864 Abernathy, Sara
9802 Epperdingle, Roscoe
1990 Moore, Wilfred
8822 Smith, David
(기타 등등)

어떤 이름을 찾는 작업은 먼저 해시 값을 계산하고, 그 다음에 그 값을 사용하여 일치여부를 비교하는 작업으로 구성된다. 일반적으로 이렇게 하는 것은, 각 문자가 26개의 경우를 갖는 예측할 수 없는 값의 길이에서 찾는 것보다, 각각이 오직 9개의 경우를 갖는 네 자리 수에서 일치하는 것을 찾는 것이 더 빠르다.

2. 해싱함수
해싱 알고리즘을 해시 함수라고 부른다. 해싱 함수(hashing function) h(k)는 어떤 키 k에 대한 테이블 주소(table address)를 계산하기 위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다.

참고자료

· 없음