홍시홍의 프로그래밍

해싱이란 해시 테이블을 이용한 탐색 기법 이론적으로 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 -..