12장 검색<계산 검색 방식>

 

비교 검색 방식 - 검색 대상의 키를 비교하여 검색하는 방법 (순차 검색, 이진 검색, 이진 트리 검색)

계산 검색 방식 - 키를 비교하지 않고 계수적인 성질을 이용한 계산으로 검색 하는 방법 (해싱)

해싱

해싱은 계수적인 성질을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다. 해싱 검색은 키값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 가서 항목이 있으면 검색 성공이 되고 없으면 검색 실패가 된다.

해싱 함수 조건

○ 해싱 함수는 계산이 쉬워야 한다. 비교 검색 방법을 사용하여 키값의 비교 연산을 수행하는 시간보다 해싱 함수를 사용하여 계산 하는 시간이 빨라야 해싱 검색을 사용하는 의미가 있다.

○ 행싱 함수는 충돌이 적어야 한다. 충돌이 많이 발생한다는 것은 같은 버킷을 할당받는 키값이 많다는 뜻이다. 즉 비어있는 버킷이 많은데도 어떤 버킷은 오버플로우가 발생할 수 있는 상태가 되므로 좋은 해싱 함수가 될 수 없다.

○ 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.

오버플로우 처리 방법(선형 개방 주소법, 체이닝 방법)

해시 테이블의 크기가 5 이고 제산 함수를 해시 함수로 사용하는 경우에 선형 개방 주소법을 사용하여 오버플로우를 해결하는 예시다 해시 함수 h(k) = k mod 5 가 되고, 저장할 키값은 { 45, 9, 10, 96, 25 } 다.

1. 선형 개방 주소법

해싱 함수로 구한 버킷에 빈 슬롯이 없어서 오버플로우가 발생하면 그 다음 버킷에 빈 슬롯이 있는지 조사한다. 

 

(1) 키값 45 저장하기 h(45) = 45 mod 5 = 0  →  해시 테이블 0번에 45저장

(2) 키값 9 저장하기 h(9) = 9 mod 5 = 4  →  해시 테이블 4번에 9저장

(3) 키값 10 저장하기 h(10) = 10 mod 5 = 0  →  해시 테이블 0번에 10저장 충돌발생!

(4) 키값 96 저장하기 h(96) = 96 mod 5 = 1  →  해시 테이블 1번에 96저장 충돌발생!

(5) 키값 25 저장하기 h(25) = 25 mod 5 = 0  →  해시 테이블 0번에 25저장 충돌발생!

 

2. 체이닝 방법

각 버킷에 하나 이상의 키값을 저장할 수 있는 방법이다. 버킷 내에서 원하는 슬롯을 검색하기 위해서는 버킷의 연결 리스트를 선형 검색한다.

 

(1) 키값 45 저장하기 h(45) = 45 mod 5 = 0  →  해시 테이블 0번에 45저장

(2) 키값 9 저장하기 h(9) = 9 mod 5 = 4  →  해시 테이블 4번에 9저장

(3) 키값 10 저장하기 h(10) = 10 mod 5 = 0  →  해시 테이블 0번에 10저장

(4) 키값 96 저장하기 h(96) = 96 mod 5 = 1  →  해시 테이블 1번에 96저장

(5) 키값 25 저장하기 h(25) = 25 mod 5 = 0  →  해시 테이블 0번에 25저장