해싱(hashing)

<해싱(hashing)>

산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다.

[검색 방법]
키 값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 이동한다. 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패

[해싱 함수(hashing function)]
키 값을 원소의 위치로 변환하는 함수 

[해시 테이블(hash table)]
해싱 함수에 의해서 계산된 주소의 위치에 항목을 저장한 표

데이터를 담을 그룻(테이블)을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것을 말하며 , 해쉬 테이블은 여유공간이 많아야 충분한 제 성능을 발휘할 수 있다.

[용어]

1. 충돌(collision)
- 서로 다른 키 값에 대해서 해싱 함수에 의해 주어진 버킷 주소를 같은 경우
- 충돌이 발생한 경우에 비어있는 슬롯에 동거자 관계로 키 값 저장 

2. 동거자 (synonym)
- 서로 다른 키 값을 가지지만 해싱 함수에 의해서 같은 버킷에 저장된 키 값들 

3. 오버플로우
- 버킷에 비어있는 슬롯이 없는 포화 버킷 상태에서 충돌이 발생하여 해당 버킷에 키 값을 저장할 수 없는 상태

<해싱 함수 종류>

1. 제산 함수

나머지 연산자 mod를 사용하는 방법으로서 키값k를 해시 테이블의 크기 M으로 나눈 나머지를 해시 주소로 사용한다.

h(k) = k mod M

2. 승산 함수

곱하기 연산을 사용하는 방법인데, 키 값k와 정해진 실수 a를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기 M과 곱하여 그 정수값을 주소로 사용한다.

3. 접지 함수

키의 비트수가 해시 테이블 인덱스의 비트수보다 큰 경우에 주로 사용하는 방법이다. 키값 k가 있을 때 해시 테이블 인덱스의 비트수와 같은 크기로 분할한 후 분할된 부분을 모두 더하여 해시 주소를 만든다.

① 이동 접지 함수
각 분할 부분을 이동시켜서 오른쪽 끝자리가 일치하도록 맞추고 더하는 방법
예) 해시 테이블 인덱스가 3자리이고 키 값 k가 123 123 123 12인 경우

② 경계 접지 함수
분할된 각 경계를 기준으로 접으면서 서로 마주보도록 배치하고 더하는 방법
예) 해시 테이블 인덱스가 3자리이고 키 값 k가 123 123 123 12인 경우

Copyrightⓒ2014 By 한빛아카데미(주)