해시 충돌 예방 기법

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)까지 다양한 성능의 해시 함수에 따른 최적 해시 함수 필요

 

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^