[알고리즘] 해시 테이블

해시 테이블

해시 테이블

원소가 저장될 자리가 원소의 값에 의해 단 한번의 계산으로 결정되는 자료구조 (검색 트리와 상반)

평균 상수 시간에 삽입, 삭제, 검색 매우 빠른 응답을 요하는 응용에 유용

- 예 : 119 긴급구조 호출과 호출번호 관련 정보 검색, 주민등록 시스템

해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않는다

해시함수

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

• 계산이 간단해야 한다

• 여러 가지 방법이 있으나 가장 대표적인 것은 나누기 방법과 곱하기 방법이다

 

나누기 방법 Division Method

– h(x) = x mod m

– m: 해시 테이블 사이즈. 대개 소수임.

곱하기 방법 Multiplication Method

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

– A: 0 < A < 1 인 상수

– m은 굳이 소수일 필요 없다. 따라서 보통 2^p 으로 잡는다(p 는 정수)

 

[예제] 크기가 16인 해시 테이블에 Multiplication method를 사용하여 다음 원소들을 저장하라. (A=0.618)

(xA mod 1) * m  (값이 정수가 아니면 소수점 이하 버림)

원소 : 25 19 20 21 18 22 23 17 24 

 

충돌

• 해시 테이블의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것

• 충돌 해결 방법은 크게 두 가지가 있다

– 체이닝 Chaining

– 개방주소 방법 Open Addressing

 

체이닝

– 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트linked list로 관리한다

– 추가적인 공간(연결 리스트) 필요

 

개방주소 방법 open addressing

– 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결한다

– 추가적인 공간이 필요하지 않다

– 빈자리가 생길 때까지 해시값을 계속 만들어낸다 -> h0(x), h1(x), h2(x), h3(x), …

 

• 중요한 세가지 방법

– 선형 조사 Linear probing

– 이차원 조사 Quadratic probing

– 더블 해싱 Double hashing

 

선형 조사

가장 간단한 충돌 해결방법으로 충돌이 일어난 바로 뒷자리를 보는 것.

1차 군집 현상 : 특정 영역에 원소가 몰릴 때 치명적으로 성능이 떨어진다.

이차원 조사

바로 뒷자리를 보는 대신 보폭을 이차 함수로 넓혀가며 본다.

2차 군집 현상 : 여러개의 동일한 원소가 초기 해시 함수로 같은 값을 갖게될 경우 모두 같은 순서로 조사를 할 수 밖에 없어 비효율적인 현상이 일어난다.

더블 해싱

두 개의 해시 함수 f(x)와 h(x)를 사용한다. 두 원소의 첫번째 해시 함수 값이 같더라도 두번째 해시 함수 값이 같을 확률은 매우 작아서 2차 군집 문제는 발생하지 않는다.

 

[예제] 크기가 7인 해시 테이블이 해시 함수로 h(x) = x mod 7을 사용한다. 원소 7 8 9 14 21 28를 차례로 저장한 후 방법에 따른 해시 테이블 모양은?

(1) 충돌해결을 Chaining으로

(2) 충돌해결을 Open addressing(선형조사)으로

 

[예제] 크기가 17인 해시 테이블이 해시 함수로 h(x) = x mod 17을 사용한다.

충돌해결은 Open addressing (Quadratic Probing)으로한다. h_i(x)=(h(x)+i^2)mod m

원소 53  51 74  40  36  6   91  17  19  34를 차례로  삽입한 후 해시 테이블 모양은?

[예제] 크기가17인 해시 테이블이 해시 함수로h(x) = x mod 17을 사용한다.

충돌해결은 Open addressing (Double Hashing)으로한다.  h_i(x)=(h(x)+if(x)) mod 17, f(x)=(x mod 13)+1

원소 53  51 74  40  36  6   91  17  19  34를 차례로  삽입한 후 해시 테이블 모양은?

 

※ 원소 삭제 시 유의사항 (선형 조사 예)

만약, 38을 찾을 경우 해시 함수 값인 12자리부터 검색한다. 그런데 두번째 그림에서 1자리의 원소가 없을 경우 38이 삭제되었다고 판단할 수 있기 때문에 삭제 표식을 넣어 해결해야 한다.

 

해시 테이블 검색 시간

• 적재율 α

– 해시 테이블 전체에서 얼마나 원소가 차 있는지를 나타내는 수치

– 해시 테이블에 n개의 원소가 저장되어 있다면 적재율 α = n/m 이다

 

• 해시 테이블에서의 검색 효율은 적재율과 밀접한 관련이 있다. 적재율이 작을 수록 효율이 좋다. 적재율이 매우 낮은 경우에는 방법들의 차이가 거의 없다.

• 일반적으로, 임계값을 미리 설정해 놓고 적재율이 이에 이르면 해시 테이블의 크기를 두 배로 늘인 다음 해시 테이블에 저장되어 있는 모든 원소를 다시 해싱하여 저장한다

 

체이닝에서의 검색 시간

• 정리 1

– 체이닝을 이용하는 해싱에서 적재율이 α일 때, 실패하는 검색에서 조사 횟수의 기대치는 α이다

–

• 정리 2

– 체이닝을 이용하는 해싱에서 적재율이 α일 때, 성공하는 검색에서 조사횟수의 기대치는 

–     1 + α/2 + α/2n 이다

 

개방 조사에서의 검색 시간

• 가정

– 조사순서 h0(x), h1(x), …, hm-1(x)가 0부터 m-1 사이의 수로 이루어진 순열을 이루고, 모든 순열은 같은 확률로 일어난다

• 정리 3

– 적재율 α=n/m 인 개방주소 해싱에서 실패하는 검색에서 조사횟수의 기대치는 최대 1/(1- α )이다

• 정리 4

– 적재율 α=n/m 인 개방주소 해싱에서 성공하는 검색에서 조사횟수의 기대치는 

– 최대 (1/ α) log(1/(1- α)) 이다

 

체이닝과 개방 조사 비교

• 이론적으로 체이닝이 개방 조사 방법보다 평균 조사 횟수가 적다.

• Chaining은 오버헤드 필요

– 연결리스트를 위한 공간

• 적재율이 그리 높지 않을 때는 개방 조사 방법이 더 매력적인 경우가 많다.

– 예를 들면 ½이하

 

 

 

자료참조 - 쉽게 배우는 알고리즘 · 관계 중심의 사고법 / 문병로