2018년 11월 23일
해시 충돌 예방 기법
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)까지 다양한 성능의 해시 함수에 따른 최적 해시 함수 필요
About The Author
