[자료구조] Hash Table -2

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.: https://github.com/ejImDev/data_structure_study.git

개방주소방식

해시테이블 전체를 열린 공간으로 가정하고 충돌된 키를 일정한 방식에 따라서 찾아낸 empty 원소에 저장
대표적인 개방주소 방식
- 선형조사
- 이차조사
- 랜점조사
- 이중해싱
- 폐쇄주소 방식의 충돌 해결 방법은 키에 대한 해시값에 대응되는 곳에만 키를 저장

선형조사

충돌이 일어난 원소에서부터 순차적으로 검색하여 처음 발견한 empty 원소에 충돌이 일어난 키를 저장
h(key) = i라면, 해시테이블 a[i], a[i+1], a[i+2], … a[i+j] 를 차례로 검색하여 첫번째로 찾아낸 empty 원소에 key를 저장
해시테이블은 1차원 배열이므로, i+j가 M이 되면 a[0]을 검
(h(key)+j) % M 의 식으로 표현 가능, j = 0,1,2,3 …
선형조사는 순차탐색으로 empty 원소를 찾아 충돌된 키를 저장하므로 해시테이블의 키들이 빈틈없이 뭉쳐지는 현상이 발생. 이를 1차 군집화라고 함
이러한 군집화는 탐색, 삽입, 삭제 연산 시 군집된 키들을 순차적으로 방문해야 하는 문제점을 야기
군집화는 해시테이블에 empty 원소 수가 적을수록 더 심화되며 해시성능을 극단적으로 저하시킴

이차조사

선형조사와 근본적으로 동일한 충돌 해결방법
충돌 후 배열 a에서 (h(key) + j²) % M의 식으로 선형조사보다 더 멀리 떨어진 곳에서 empty 원소를 찾음 (j = 0,1,2…)
- 따라 1차 군집화 문제를 해결할 수 있음
같은 해시값을 갖는 서로 다른키들인 동의어(Synonym)들이 똑같은 점프 시퀀스를 따라 empty원소를 찾아 저장하므로 결국 또 다른 형태의 군집화인 2차 군집화가 야기됨
점프 크기가 제곱만큼씩 커지므로 배열에 empty 원소가 있는데도 empty 원소를 건너뛰어 탐색에 실패하는 경우도 피할 수 없음

랜덤조사

선형조사와 이차조사의 규칙적인 점프 시퀀스와는 달리 점프 시퀀스를 무작위화하여 empty 원소를 찾는 충돌 해결 방법
랜덤조사는 의사난수 생성기를 사용하여 다음 위치를 찾음
랜덤조사 방식도 동의어들이 똑같은 점프 시퀀스에 따라 empty 원소를 찾아 키를 저장하게 되고, 이 때문 3차 군집화가 발생

이중해싱

2개의 해시함수를 사용
하나는 기본적인 해시함수 h(key)호 해시테이블의 인덱스로 변환하고, 제 2의 함수 d(key)는 충돌 발생 시 다음 위치를 위한 점프 크기를 다음의 규칙에 따라 정함
(h(key) + j * d(key)) mod M, j = 0,1,2…
이중해싱은 동의어들이 저마다 제2함수를 갖기 때문에 점프 시퀀스가 일정하지 않음
따라서 이중해싱은 모든 군집화 문제를 해결
제 2의 함수 d(key)는 점프 크기를 정하는 함수이므로 0을 리턴해서는 안됨
그 외의 조건으로 d(key)의 값과 해시테이블의 크기 M과 ‘서로 소’ 관계일때 좋은 성능을 보임
하지만 해시테이블 크기 M을 소수로 선택하면 이 제약 조건을 만족

폐쇄 주소 방식

충돌 해결 방법은 키에 대한 해시값에 대응되는 곳에만 키를 저장
충돌이 발생한 키들은 한 위치에 모여 저장
이를 구현하는 가장 대표적인 방법 : 체이닝

재해시

어떤 해싱방법도 해시테이블에 비어있는 원소가 적으면, 삽입에 실패하거나 해시성능이 급격히 저하되는 현상을 피할 수 없음
이러한 경우, 해시테이블을 확장시키고 새로운 해시함수를 사용하여 모든 키들을 새로운 해시테이블에 다시 저장하는 재해시가 필요
재해시는 오프라인에서 이루어지고 모든 키들을 다시 저장해야하므로 O(N)시간이 소요
재해시 수행여부는 적재율에 따라 결정
적재율 ∝ = (테이블에 저장된 키의 수 N) / (테이블 크기 M)
일반적으로 ∝ > 0.75가 되면 해시테이블 크기를 2배로 늘리고, ∝< 0.25가 되면 해시테이블을 1/2로 줄임

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/C6wua2t6MV0