해시테이블
지금까지 트리 자료구조는 대부분은 다른 원소와 비교하여 저장할 위치를 찾아갔다. 그러나 해시테이블은, 원소를 저장할 위치가 그 원소 값에 의해 결정되는 자료구조다.
해시테이블의 특징은 다음과 같다.
- 저장/검색/삭제에 있어서 상수에 가까운 수행시간을 갖는다. = > Θ(1)
- 최소 원소 찾기 같은 연산은 지원하지 않는다.
지금부터 위의 그림을 예시로 해시테이블에 대해 설명하겠다.
위와 같은 해시테이블의 크기 m을 7이라 하자. 그렇다면 테이블은 0~6까지의 인덱스를 갖는다.
해시함수 Hash function
원소를 저장할 때, 가운데 해시함수 hash function를 거쳐서 적절한 위치에 저장된다. 따라서 해시함수는 검색 키 값을 해시 테이블주소로 매핑하는 함수라는 의미다.
해시함수는 입력원소가 테이블에 골고루 흩어지도록 주소를 계산해야 한다. 다시 말해, 충돌이 발생해서는 안된다.
또한, 계산이 간단해야 한다.
해시함수는 대표적으로 두 가지 방법이 있다.
- 나누기 방법 division method : h(x) = x mod m
테이블의 크기가 m, 저장하려는 원소가 x다.
여기서 중요한 건, m의 결정이다. m은 2^p에 가깝지 않은 '소수 prime number'가 바람직하다. m = 2^p라면, 하위 p 비트에 의해 해시값이 결정되기에 원소 분산이 잘 이뤄지지 않을 수 있다. 따라서 소수를 사용하자.
- 곱하기 방법 multiplication method : h(x) = floor[m(xA mod 1)]
- A : 0< A <1인 상수
- mod 1은 어떤 값에서 소수부만 취하는 연산
- floor는 소수부를 버리는 연산이다.
테이블의 크기는 상관없으나 상수 A의 결정이 해시 값 분포에 영향을 미친다.
충돌 Collision
해시테이블에서 충돌이란, 해시테이블의 한 주소를 놓고 두 개 이상의 원소가 관계되는 것을 의미한다. 이미 한 원소가 자리를 차지하고 있는 상황에 그 자리에 다른 원소를 배치해야 하는 상황이다.
해시함수로 인해 테이블에 군집화가 일어날 수 있다. 이 군집화란, 해시원소 값이 테이블에 연달에 저장된 상태를 의미한다.
이런 군집화 상태에서 만약 새 원소를 삽입하려고 보니 2번에서 충돌이 일어난다면 어찌되는가? 처리방법에 따라 다르지만 이해하기 쉬운 경우를 설명하자면 2번에서 3번으로, 3번에서 충돌이 일어났으니 4번으로, 다시 5번으로. 이런 식을 반복하다가 빈 자리를 찾아간다. 이는 테이블의 성능 저하로 이어지므로 군집화는 예방되어야 한다.
다만, 해시함수는 다대일 함수로, 충돌은 어쩔 수가 없다. 따라서 충돌이 적게 일어나도록 해시함수를 결정하고, 충돌이 일어나더라도 해결방법을 이용해서 처리해야 한다.
충돌을 해결할 방법은 크게 두 가지로 나뉜다.
- 체이닝 chaining : 하나의 주소로 해싱되는 원소들을 하나의 연결리스트로 관리하는 것이다. 크기가 m인 테이블에 m 이상의 원소를 저장할 수 있다. 다만 그만큼 공간을 차지하게 된다. 다음은 체이닝의 예를 보여준다.
- 개방주소 open address : 개방주소는 세 가지로 나뉜다. 선형조사, 이차조사, 더블 해싱
선형조사 linear probing : 개방주소 중에서 가장 간단하다. 충돌이 일어났다면 충돌이 일어난 자리의 바로 뒷자리를 조사한다. h(x) = (h(x) + i) mod m, i= 1,2,3,4, ...
다만 선형조사는 1차 군집 primary clustering 문제가 발생할 가능성이 있다. 이 군집화는 점점 더 큰 군집으로 형성되어 성능이 치명적으로 감소된다.
이차조사 quadratic probing : 충돌이 발생하면 보폭을 이차 함수에 의해 넓혀가며 조사하는 방식이다. 특정영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있다. h(x) = (h(x) + ci^2 + ci) mod m, i = 1,2,3,4,5, ...
다만 2차 군집 secondary clustering 문제가 발생할 수 있다. 이는 여러 원소가 초기 해시 함수값이 동일해서 한 번 충돌이 일어나면 모두 같은 곳을 같은 순서로 조사하게 됨을 의미한다.
더블 해싱 double hashing : 두 개의 함수를 사용하여, 충돌이 일어나면 f(x)만큼씩 점프한다. 이는 첫번째 해시값에서 충돌이 일어나도 두 번째 함수값도 같을 확률이 매우 작다는 것을 알 수 있다.
h(x) = h(x) + (i*f(x)) mod m, i = 0,1,2,...
h(x) = x mod m, f(x) = 1+(x mod m')을 권장한다.
삽입/검색/삭제
- 삽입 : 아래 코드에서 보이듯, T(해시테이블)에 x(원소)를 삽입하고 x가 저장된 위치를 리턴한다. 참고로 m은 테이블의 크기를 나타낸다.
hashInsert(T[], x)
{
i ← 0;
repeat {
j ← hi(x);
if (T[j] = NIL)
then { T[j] ← x; return j ; }
else i++;
} until (i = m);
error “테이블 오버플로우”;
}
- 검색 : T에서 x를 찾아, 이 원소가 저장된 위치를 리턴한다.
hashSearch(T[], x)
{
i ← 0;
repeat {
j ← hi(x);
if (T[j] = x)
then return j ;
else i++;
}
until (T[j] = NIL or i = m);
return NIL;
}
- 삭제 : 삭제에서 알아둘 것은 절대 자료를 그냥 삭제하면 안된다는 것이다. 자료를 삭제한 자리에 DELETED라는 상수 값을 저장해둘 필요가 있다. 원래 자료가 있던 자리로 인식하기에 충돌로 밀려나 다른 곳에 저장된 자료를 찾아가는데 지장이 없어진다. 다만 삭제가 빈번할수록 효율이 떨어질 수 있다.
'공부한 기록 > 알고리즘' 카테고리의 다른 글
| 알고리즘(13) - 동적 프로그래밍 dynamic programming (0) | 2023.05.17 |
|---|---|
| 알고리즘(12) - 집합의 처리 (4) | 2023.05.08 |
| 알고리즘(10) - 검색트리 - B-Tree, 다차원 검색트리(KD-Tree) (0) | 2023.04.06 |
| 알고리즘(9) - 검색트리 - 레드블랙트리 red-black tree (0) | 2023.04.04 |
| 알고리즘(8) - 검색트리 ( search tree ) (0) | 2023.04.03 |