07 해시 테이블

해시 테이블 : 원소의 값에 의해 원소가 저장될 위치를 결정

즉, 단 한 번의 계산으로 자신의 자리를 찾기가 가능

 

해시 함수의 성질

1. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.

2. 계산이 간단해야 한다.

 

1. Division Method

$h(x) = x mod m$

m: table size, 보통 prime number

 

2. Multiplication Method

$h(x) = (xA mod 1) * m$

0 < A < 1 : constant

m은 굳이 소수일 필요가 없다. 보통 $2^p$로 설정

 

충돌(Collision) 해결

1. Chaining

같은 주소로 해싱되는 원소들을 모두 하나의 연결 리스트에 매달아서 관리

저장할때는 head에 연결하는 것이 효율적,

검사할때는 해당 연결리스트를 끝까지 탐색

적재율이 1을 넘어도 사용가능

 

2. Open Addressing

추가 공간을 허용하지 않음

원소가 자신의 해시 값과 일치하는 주소에 저장된다는 보장이 없다.

0번째 해시 함수, 1번째 해시 함수, ... 를 사용한다. ($h_0 (x), h_1 (x), h_2 (x), \cdots$)

 

2-1) Linear Probing (선형 조사)

$$h_i (x) = (h(x)+i)~mod~m~~~i = 0,1,2, \cdots$$

Primary Clustering에 취약 (한군데 원소들이 몰려서 저장되는 현상)

 

2-2) Quadratic Probing (이차원 조사)

$$h_i (x) = (h(x) + c_1 i^2 +c_2 i)~mod~m~~~i=0,1,2, \cdots$$

Secondary Clustering에 취약 (최초 해시값이 같으면 2차, 3차 해시값도 같아서 비효율적)

 

2-3) Double Hashing

$$h_i (x) = (h(x) + i\cdot f(x))~mod~m~~~i=0,1,2,\cdots$$

두 원소의 첫번째 해시 값이 같더라도 두번째 함수 값이 같을 확률이 매우 작다.

권장하는 방법 :

$$h(x) = x~mod~m$$

$$f(x) = 1+(x~mod~m')~(m'은 m보다 조금 작은 소수)$$

 

+) 개방 주소 방법에서 원소 삭제를 할때

개방 주소 방법을 사용했을 때 해시 테이블에서 원소를 검색할때에는 빈자리가 나올때까지 $h_i (x)$를 계산한다.

그런데 해당 원소가 삭제되어 테이블이 빈자리로 남으면 그 다음 원소를 검색하는데 문제가 생긴다.

따라서 원소를 삭제한 후에는 그 자리에 'DELETED'라는 상수 값을 넣어줘서 그 다음 원소를 검색할 수 있도록 해준다.

 

+) 해시 테이블의 load factor (적재율)

해시 테이블의 적재율은 낮으면 공간의 낭비이고 높으면 검색 성능이 떨어진다.

그래서 적당한 적재율의 유지가 필요하다.

주로 사용하는 방법은 다음과 같다.

load factor의 threshold를 설정, 해시 테이블의 적재율이 그 값을 넘어가면

해시 테이블의 크기를 2배 늘리고 모든 원소를 re-hashing하여 저장