-------------------------------------------------------------------
요약: 다음과 같은 방법들로 해쉬 함수의 충돌을 방지함
- 오픈 어드레싱(open addressing method)
1. 선형 조사법(Linear Probing)
2. 이차 조사법(Quadratic Probing)
3. 이중 해쉬(Double Hash)
- 닫힌 어드레싱(closed addressing method)
4. 체이닝(Chaining)
--------------------------------------------------------------------
해쉬함수의 충돌(collision) 문제 해결
1. 선형 조사법(Linear Probing)
- 충돌 발생 시 그 옆자리가 비었는 지 살펴보고, 비었을 경우 그 자리에 대신 저장
예시) 해쉬함수 f(x)를 key%7로 정의하고 테이블 내부 저장소가 배열 형태로 존재한다 가정했을 때,
key가 9인 데이터각 들어옴 -> 해쉬값 2이므로 인덱스 2 위치에 데이터 저장
key가 2인 데이터가 들어옴 -> 해쉬값 2이므로 키가 9인 데이터와 충돌 발생 -> 바로 옆인 인덱스 3이 비었는 지 확인 -> 비었다면 이곳에 저장
- 즉 다음과 같은 순서로 빈자리를 찾게 됨
f(k)+1 -> f(k)+2 -> f(k)+3 .....
- 선형 조사법의 문제점
충돌 횟수가 증가함에 따라서 특정 영역에 데이터가 몰리는 클러스터 현상이 발생
2. 이차 조사법(Quadratic Probing)
- 선형 조사법의 문제점을 극복하기 위해 등장
- 바로 옆이아닌 좀 더 멀리서 빈 공간을 탐색
- 즉 다음과 같은 순서로 빈자리를 찾게 됨
f(k)+1^2 -> f(k)+2^2 -> f(k)+3^2 .....
선형 조사법과 이차 조사법을 적용시킬 때 주의할 점
- 슬롯의 상태를 Empty, Deleted, Inuse로 나누어 관리해야 함
- Empty는 슬롯이 비었다는 의미
- Deleted는 슬롯에 데이터가 채워졌었지만 현재 삭제된 상태를 의미
- Inuse는 데이터가 채워져있음을 의미
- Empty상태와 Deleted상태를 굳이 구분하는 이유는 아까의 상황에서 key가 2인 데이터가 key가 9인 데이터에 밀려 옆자리에 저장이 되었는데,
이후 key가 9인 데이터가 삭제되어 인덱스 2 자리 슬롯이 비어버리는 상황이 일어날 수 있다.
- 이 상황에서 우리가 key가 2인 데이터를 탐색한다고 해보자.
- key가 2인 데이터의 해쉬값은 2이기때문에 인덱스 2번째 슬롯부터 먼저 살펴볼텐데 이때 이 슬롯이 empty라면 현재 테이블에 이 데이터는 존재하지 않는다고 판단할 수 있다.
- 하지만 이 슬롯이 deleted라면 충돌 가능성을 염두해두고 선형or 이차 조사법에 근거하여 탐색의 과정을 거쳐야 한다.
3. 이중해쉬(Double Hash)
- 이차 조사법은 선형 조사법의 문제점을 어느 정도 해결했지만, 충돌 시 빈 슬롯을 찾기 위해 접근하는 위치가 늘 동일하다는 문제점을 지님
- 이 빈 공간 탐색을 좀 더 불규칙하게 만들기 위한 조사 방법이 이중해쉬
- 1차 해쉬 함수는 키를 근거로 저장위치를 결정하기 위한 것
- 2차 해쉬 함수는 충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것
- 많이 쓰이는 형태
1차 해쉬 함수 h1(k) = k%15 (15자리엔 보통 배열의 크기를 대입)
2차 해쉬 함수 h2(k) = 1+(k%c)
- c는 보통 15보다 작은 소수(prime number)로 결정한다.
- 소수 사용 이유? 통계를 근거로 소수를 사용했을 때 충돌 확률이 적다고 알려져 있기 때문
- 15보다 작게 만드는 이유는 2차 해쉬 값이 가급적 1차 해쉬 값을 넘어서지 않게 하기 위함. 1차 해쉬 값이 10인데 2차 해쉬 값의 최대값이 32라면 빈 공간을 찾아 배열을 쓸데없이 몇 바퀴 돌 수 도 있기 때문
예시) 키로 3, 18, 33이 존재할 경우 위의 해쉬 함수를 도입해보자.
1차 해쉬 함수 h1(k) = k%15
2차 해쉬 함수 h2(k) = 1+ (k%7)
- 1차 해쉬 함수는 모두 3으로 동일
- 2차 해쉬 함수는 키 18일때 h2(18) = 1+(18%7) = 5, 키가 33일때 h2(33) = 1+(33%7) = 6
키가 3인 데이터가 저장되고 이후
키 18인 데이터가 저장될 때 1차 해쉬 함수가 같으므로 충돌이 발생
2차 해쉬 함수를 이용하여 다음과 같은 순서로 빈 슬롯을 탐색
h2(18) -> h2(18)+5 -> h2(18)+5*2 -> h2(18)+5*3 ...
4. 체이닝(Chaining)
- 앞의 선형조사법, 이차조사법, 이중해쉬 방법을 통틀어 'open addressing method'라 칭한다.
- 이와는 근본적으로 다른 'closed addressing method'가 존재. 이는 자기 위치를 고수한다는 의미이다.
- 2차원 배열을 구성하고 해쉬 값 별로 다수의 슬롯을 마련하는 방법도 있지만 이 방법은 메모리 낭비가 심하다.
- 체이닝 방법은 연결 리스트를 사용하여 구현한 대표적인 'closed addressing method'이다.
- 충돌이 발생하면 연결리스트로 데이터를 연결해나간다.
- 탐색 시 동일 해쉬 값으로 묶여있는 데이터를 모두 탐색해야 한다는 불편이 따르지만, 해쉬 함수를 잘 정의하여 애초에 충돌 가능성이 높지 않다면 이는 부담되지 않는 수준
댓글