새소식

컴퓨터공학 💻/알고리즘 분석

[알고리즘] 해시 테이블

  • -
해시 테이블
해시 테이블

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

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

- 예 : 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 오버헤드 필요

연결리스트를 위한 공간

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

예를 들면 ½이하

 

 

 

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

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.