해싱(Hashing)

해싱이란

해시 테이블을 이용한 탐색 기법

이론적으로 O(1)에 탐색가능

 

해시 함수 : 인덱스를 해시 주소로 바꿔주는 함수

해시 함수 조건

- 충돌이 적어야 한다

- 해시 주소가 고르게 분포되어야한다

- 계산이 빨라야 한다.

 제산 함수 일 경우 소수로 나눈다

 

폴딩 이동 폴딩, 경계 폴딩

탐색키가 문자열일 경우 호너의 방법 사용

 

해싱은 충돌을 잘 처리해야 한다

충돌이 일어날 경우, 선형 조사법과 체이닝으로 해결

 

충돌 해결법 2가지

1. 오픈 어드레싱

2. 체이닝

 

오픈 어드레싱 종류 3가지

1. 선형 조사법

 - h(k)+1 ,,,, +2 ,,,,+3 으로

2. 이중 조사법

 - 제곱을 더함 h(k) +1^2,2^2,3^2식으로

3. 이중 해싱법

 - 해시 2개 사용

 - 첫번째 해시 kmod H 두번째 해시 P - (kmodP) 

 - H와 P는 서로수이여야 효과가 좋음

 

선형조사법

충돌이 일어날 경우, 뒤에 빈 해시테이블에 값을 넣어줌

군집화 해결을 위해서 이차 조사법,  이중 해싱법 를 사용

 

체이닝

충돌이 일어날 경우, 연결리스트를 사용하여 뒤에 넣어주는 방법

 

해시의 성능

적재 밀도에 따라 다르다

적재 밀도 = 저장된 항목의 개수 / 해싱 테이블의 버켓의 개수

 

참고 자료 : C언어로 쉽게 풀어쓴 자료구조