[알고리즘] 해시 알고리즘: 탐색과 충돌 (Hashing)

📂 해시테이블

정렬알고리즘에 비해 탐색알고리즘은 수시로 탐색이 진행된다(ex. 데이터베이스에서 원하는 데이터를 찾을 때) 따라서 탐색 알고리즘에서 탐색에 소요되는 시간을 단축시키는 것은 굉장히 중요한 이슈이다.

원소가 저장될 자리가 원소의 값에 의해 바로 결정되는 자료구조 → O(1) 시간으로 매우 빠른 응답을 요구할 때 사용되는 기법

cf. 탐색 트리의 경우 원소의 값에 의해 위치가 결정되지만 트리를 탐색해 내려가는 시간이 소요됨

최소값, 특정값 바로 전/후의 값 등을 찾아낼 수 없으며 그냥 특정값의 위치를 찾아내기만 하는 '탐색'의 기능만 함

 

해시테이블에서는 해시함수 h(x) = (ax + b) mod p 를 이용해 원소가 저장될 위치를 결정함

• h(x) = x mod 11
• 값을 균등하게 배분할수록 좋음 (경우에 따라서는 그렇지 않을 수 있음)

탐색

• 16을 탐색하려면 h(16) = 16 mod 11 = 5 이고 해당칸에 들어있음
• 27를 탐색하려면 h(27) = 27 mod 11 = 5 이고 해당칸에 없음
• 27이라는 새로운 데이터를 저장하고 싶을 때 16과 충돌이 발생함 → 충돌문제를 어떻게 해결할까?

충돌

• 해시체인(hash chain) - 연결리스트를 이용해 한 인덱스에 여러개의 key를 연결해 저장한다
• 선형조사 : 충돌된 인덱스에서 시작해 빈칸이 나올때까지 다음 칸으로 이동해 저장하고 탐색한다 
• 일차군집 : 특정 영역에 원소들이 몰려 해시의 효율이 낮아지는 문제 (= 클러스터링 = 쏠림현상)
• 이차원조사 : 바로 다음 칸이 아닌 i^2 칸으로 이동해 저장하고 탐색한다 (일차군집 문제를 해결 ← 분산시킴)
• 이차군집 : x1=x2 라면 h(x1)=h(x2)이므로 어쨌거나 계속 충돌이 발생함
• 이중해싱 : 일/이차군집 문제를 해결하기 위해 또 다른 함수를 이용한다 (아예 다른 충돌 시 사용하는 해시함수) = 리해싱 방법

삭제

• 단순히 빈칸(NULL)이 아니라 DELETED 마크를 표시해둠 (선형조사한 원소의 탐색이 가능해야하므로)

검색시간

O(logn)을 가지는 배열이나 O(logn)의 이진탐색트리는 최악의 경우 O(n)의 시간복잡도를 가진다. 해시테이블을 사용하면 평균적으로 O(1) 시간에 탐색이 가능하다. 만약 해시 체인기법을 사용해 한 인덱스에 여러개의 키를 저장하는 경우, 평균적으로 한 인덱스당 k만큼의 원소가 포함된다면 평균 검색시간은 1 + k 가 될 것이다. O(1+k) 시간을 가질 것.

이때 k > 0.5 라면 일차군집 발생 확률이 높아지는데 이는 비둘기집 원리 때문이다. 이 경우 해시테이블의 크기를 2배로 늘리고 새로운 해시함수를 만든다. 교수님이 여기서 분할상각기법을 논의할 때 다시 언급한다고 하셨는데..

그래서 분할상각기법에 대해 아주 살짝 공부해봤다. 내용은 여기서