해시 충돌 예방 기법

I. 해시 함수 및 해시 테이블

해시 함수	해시 테이블
– 탐색 키를 입력으로 받아 해시 주소 생성 및 해시 테이블의 인덱스로 해시값을 반환하는 함수	– 해시 키의 인덱스 자료 – 배열로 구성되는 자료구조

 

II. 해시 충돌 예방 기법

구분	충돌 예방 기법	설명
Closed Address (Chaining) 방식	– Direct Chaining	– 동일 해시 테이블 내 유사 레코드를 연결리스트 구성
	– Indirect Chaining	– 해시 테이블과 별도로 기억 공간 확보, 유사레코드 연결
	– Coalesced Chaining	– 충돌 발생 시 빈 버킷을 찾아 삽입, 포인터 위치 기억
	– Separate Chaining	– 충돌 발생한 키 값들을 연결리스트로 처리
Open Address 방식	– 선형 조사법 (Linear Probe)	– 빈 버킷의 순차적 탐색 – hi(x) = (h(x) + i) mod m
	– 이차 조사법 (Double Probe)	– 2차함수 기반 탐색 기법 – (h(x)+C1i2+C2i) mod m
	– 이중 해싱법 (Double Hash)	– 2차 해시함수로 주소 할당 – hi(x) = (h(x) + if(x)) mode m
	– 무작위 검색 Random Search	– Random Number Generator – 무작위 값 대입, 주소할당

• 해시는 일반적으로 Locality가 취약하며, O(1)의 탐색 시간 보장하는 hashmap 사용 필요

 

III. 해시 충돌 예방 기법의 문제점 및 해결방안

문제점	고려사항
– 취약한 데이터접근 패턴 – 구현 및 사용 어려움 – 급격한 성능 감소	– 선형 탐지기법 사용 – 효율적 해시함수 사용 – 해시 테이블 재구성

• 해시 함수는 O(1) 부터 O(n)까지 다양한 성능의 해시 함수에 따른 최적 해시 함수 필요