자료의 탐색 - 해싱(Hashing)

해싱(Hashing)

순차 탐색이나 이진 탐색의 비교 연산이 아닌 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 찾아가는 계산 탐색 방법.

해싱(Hashing) 탐색방법

 ① 키값에 대해서 해싱 함수를 계산하여 주소를 구한다.

 ② 구한 주소에 해당하는 해시 테이블로 바로 이동한다.

 ③ 해당 주소에 찾는 키가 있으면 탐색을 성공한 것이며, 해당 주소에 찾는 키가 없으면, 찾는 원소가 없는

     것으로 판단한다.

해싱(Hashing) 예제

문제: 10장으로 구성 수가 다음과 같다고 가정한다.

1)해싱 함수를 수 자체 해시값으로 정의한 경우

 

각 숫자가 저장된 위치는 다음과 같이 저장된다.

즉, 34의 경우는 34번째 공간에 저장되며 1은 첫 번째 공간에, 999는 999번째 공간에 저장되어
찾고자 하는 수가 34라면 34번째 수가 있는지 없는지만 확인하면 된다.

 

2)해싱 함수를 5로 나눈 나머지로 정의한 경우

 

나머지가 0인 10, 45, 50, 100은 같은 해시값을 가지므로 충돌이 발생하며, 나머지가 4인 34, 89, 99, 999도 충돌이 발생하게 되므로 다음과 같이 충돌을 해결하기 위한 공간을 확보하여 저장한다. 찾고자 하는 값이 50이라면 해싱 함수에 의해 0이라는 값을 얻고 0의 값을 가진 나머지 값들을 순차적으로 탐색하여 찾게 되므로 총 3번의 비교를 하면 찾을 수 있다.

해싱(Hashing) 비교횟수, 특징

비교횟수

   -최대 비교 횟수 ⇒ n

   -탐색의 평균 비교 횟수 ⇒ 1

특징

   -자료의 계수적 특징을 이용하여 자료의 위치를 결정한다.

   -해싱 함수가 하나의 자료에 대해 유일한 위치를 결정지을 수 있어야 효과적이다.

   -해싱 함수가 하나의 자료에 대해 유일한 위치가 결정이 되지 않은 경우에는 충돌 해결 방법을 고려하여야 한다.

   -탐색 알고리즘은 매우 단순하나 자료 저장을 위한 추가 공간이 필요하다.