해싱

알고리즘 8 해싱

해싱의 장점. 속도가 매우 빠르고, 짧은 해시 키를 사용해 항목을 찾으면 원래의 값을 사용하여 찾는 것보다 더 빠르다.

2개이상의 키가 같은 해쉬값을 찾는 경우 충돌이 발생할 수 있음.

해결-> 같은 해쉬값을 갖는 키들을 bucket에 모아놓는다. 버킷은 연결리스트로 구현 한다.

" 각 Bucket을 가리키는 포인터 배열 Bucket[]을 만 당 Bucket의 연결 리스트를 가리키도록 한다.

값 i 로 해시되는 키 값들은 모두 Bucket[i]가 가리키는 연 위치시킨다.

"

충돌해결법 : 오픈해싱

버킷의 수가 키의 갯수와 같은 필요는 없지만,

버킷의 수가 적다면 충돌은 필연적임.

n개의키와m개의 버킷이 있고 키들이 버킷에 균일하게 분포 저장되어있다면. 각 버킷마다 n/m개의 키가 존재.

평균 비교횟수 = n/2m + 1/2

256개의 키라면, 이진검색은 8번 검색.

버킷이 16개라면 8.5번 평균검색

128개라면 1.5 번평균검색

256개라면 1     번의 평균검색

버킷의 수가 충분하고 해시함수가 좋을때, 충돌에 의해 버킷내의 레코드수가 이진검색비교횟수보다 많아질 확률은 극히 적다.