6장 해시 테이블
원소끼리 비교해 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정한다.
1. 해시 테이블
- 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
- 해시값은 해시 함수에 의해 계산
- 적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율로서 성능에 중요한 영향을 끼침.
2. 해시 함수
다음의 두 가지 성질을 만족해야 함
a. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
b. 계산이 간단해야 한다.
2.1 나누기 방법
- 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 하는 방법
- h(x) = x mod m : m은 해시 테이블의 크기
- m은 2의 멱수(2^p) 에 가깝지 않은 소수를 택하는 것이 좋다. 2의 멱수라면 입력 원소의 하위 p비트에 의해 해시값이 결정되기 때문이다.
2.2 곱하기 방법
- 입력값을 0과 1사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 팽창시키는 방법(0<A<1 범위의 상수 A 필요)
- 계산 방법
* x에 A를 곱한 다음 소수부만 취한다.
* 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
* h(x) = m(xA mod 1)의 정수부
- Knuth는 잘 작동하는 값으로 (루트5 - 1)/2를 제안
3. 충돌 해결
- 충돌: 해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것
3.1 체이닝
- 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리
- 임의의 원소를 연결 리스트에 삽입할 때 해당 리스트의 맨 앞에 삽입하는 것이 좋다.
3.2 개방주소 방법(Open Addressing)
- 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 방법
- 충돌이 일어나면 다음 해시 함수로 다음 자리를 찾는다. 그래도 차 있으면 자리를 찾을 때까지 계속한다.
3.2.1 선형 조사(Linear Probing)
- 충돌이 일어난 바로 뒷자리를 보는 것
- h(x) = (h(x) + i) mod m
- 특정 영역에 원소가 몰릴 때는 치명적으로 성능이 떨어진다.
3.2.2 이차원 조사(Quadratic Probing)
- 충돌시 바로 뒷자리를 보는 대신에 보폭을 이차함수에 의해 넓혀가면서 본다.
- h(x) = (h(x) + c1*i^2 + c2*i) mod m, i = 0, 1, 2, ...
- 선형 조사에서의 단점인 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어 날 수 있다.
- 여러개의 원소가 동일한 초기 해시 함수값을 갖게 되면 모두 같은 순서로 조사를 할 수 밖에 없으므로 비효율적이 된다.
3.2.3 더블 해싱
- h(x) = (h(x) + i*f(x)) mod m, h(x)와 f(x)는 서로 다른 해시 함수, i = 0, 1, 2, ...
* h(x) = x mod m, f(x) = 1 + (x mod m'), m'은 m보다 조금 작은 소수
- 두 원소의 첫 번째 해시값이 같더라도 두 번째 함수값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프를 하게 된다.
- 두 번째 해시 함수 값 f(x)가 해시 테이블 크기 m과 서로 소인값이어야 한다.
* f(x)와 m이 최소공약수 d를 가지면 x의 자리를 찾기 위해 해시 테이블 전체 중에 기껏해야 1/d 밖에 보지 못하게 된다.
* m을 소수로 잡고 f(x)의 값이 항상 m보다 작은 자연수가 되도록 하면 된다.
3.2.4 삭제시 문제점
- 원소(x)를 저장할 때 충돌로 인하여 여러번 해시 함수를 통해 위치를 찾은 경우 기존에 겹쳤던 원소(y)를 삭제하면 나중에 x를 찾을 때 y의 위치가 비어 있으므로 찾지 못하게 되는 문제가 생긴다.
- 따라서, 원래 원소가 있었던 위치라는 것을 표시해 주어야 위치를 찾아 갈 수 있다.
4. 검색 시간 분석
책 참조
댓글 없음:
댓글 쓰기