해싱(Hashing) 이란?
해싱(Hashing)
입력값에 수학적 알고리즘(해시 함수)을 적용하여 고정된 크기의 문자열을 출력하는 과정
키에 대한 연산에 의해 직접 접근이 가능한 구조를 해시 테이블이라 부르며, 해시 테이블을 이용한 탐색을 해싱이라 한다.
충돌 (Collision)
서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상이다.
오버플로우 (overflow)
해시 주소에 더이상 빈 버킷이 남아 있지 않으면 발생한다.
오버플로우는 충돌이 발생하고, 오버플로우가 발생하면 해시테이블에 항목을 더 이상 저장하는 것이 불가능해진다.
개방주소법(open addressing)
: 현재 사용되고 있지 않은 공간을 찾아 저장하는 방법. 빈 공간을 효율적으로 찾는 것이 중요하다. 충돌이 일어났을 때 대처하는 방법에 따라 선형 조사법, 이차 조사법, 이중 해싱법, 체인법 등이 존재한다.
1. 선형 조사법(linear probing)
선형조사법 조사되는 위치:
h(k), (h(k)+1) % 해시테이블 크기,(h(k)+2) % 해시테이블 크기. (h(k)+3) % 해시테이블 크기 (h(k)+4) % 해시테이블 크기
문제점 : clustering 문제(비선형법) -> 한 번 충돌이 시작 시, 그 위치에 집중되는 현상
2. 이차 조사법 (quadratic probing)
- h(k), (h(k)+1) % 해시테이블 크기,(h(k)+4) % 해시테이블 크기. (h(k)+9) % 해시테이블 크기, (h(k)+16) % 해시테이블 크기
문제점 : 2차 클러스터링 문제 -> 집중되어지는 slot을 중심으로 클러스터링이 발생될 확률이 여전히 높다. 또한 오버플로우 처리과정에서 불필요한 data의 탐색을 하기에 탐색효율성이 떨어진다. 이중해싱법/ 체인법을 사용하여 해결할 수 있다.
이차조사법에서 2를 삽입하고자 할 때
3. 이중 해싱법 (double hashing)
h(k), (h(k)+1*h'(k))%해시테이블 크기(h(k)+2*h'(k))%해시테이블 크기.(h(k)+3*h'(k))%해시테이블 크기, (h(k)+4*h'(k))%해시테이블 크기
참고 [h와 h'는 다른 해싱함수]
이중해싱법에서 2를 삽입하고자 할 때
4. 체인법 (chaining)
배열의 각 버킷(해시 테이블)에 저장하는 것은 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드(head node)를 참조하는 것이다.
만약 해시 주소가 같은 키만을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것이다. 충돌을 해결하는 두 번째 방법은 해시 테이블의 구조를 변경하여 각 버킷이 하나 이상의 값을 저장할 수 있도록 하는 것이다.
