Hash - 오버플로우 처리 방법

먼저 해시 함수가 가져야 할 특징 3가지가 있다.

1. 충돌이 적어야 한다.
2. 해시 테이블에 고르게 분포시킬 수 있는 주소의 연산 값이 나와야 한다.
   이는 곧 1번을 충족할 수 있다.
3. 계산이 빨라야 한다.

위 3가지를 고루 갖추지 못한다면 100개의 버킷 중에 하나의 버킷만 나와서 오버플로우가 발생하는 참사가 일어날 수 있다.

 

위의 특징을 고루 갖춘 함수 중 하나로 제산 함수라는 것이 있다.

제산 함수

레코드(키) 값을 소수로 나누어 나머지 값을 주소로 지정하는 해시 함수.

ex) h(k) = k % 7

 

---

만약 위 특징을 갖춘 해시 함수를 만들었는데도 오버플로우가 발생한다면?

 

내가 아는 선에서 두 가지의 방법이 있다.

1. 선형 탐사법 (Linear Probing)
2. 분리 연결법 (Separate Chaining)

1. 선형 탐사법

해시 함수로 거쳐 나온 주소 값이 가리키는 버킷이 아닌, 다른 버킷에 저장하는 것이다.

하지만 막무가내로 다른 버킷에 저장할 경우 나중에 탐색을 할 때 시간 복잡도가 증가할 수 있다.

 

2. 분리 연결법

버킷의 수는 정해져 있으므로 연결 리스트나 트리를 활용하는 방법이다.

연결 리스트는 배열이 아닌 next와 같은 속성을 가지는 노드 단위로 연결되어 있기 때문에 값의 추가, 삭제에 용이하다.

 

충돌을 방지하는 방법에 대한 자세한 내용은 아래 글에 기재하였다.

 

https://lifeandit.tistory.com/112

Hash Table에 대하여

 

출처

https://luv-n-interest.tistory.com/188?category=873976 

[C언어] 자료구조 - Hash -오버플로우 처리 방법 및 기본 연산-2