해시 테이블
해시 테이블
원소가 저장될 자리가 원소의 값에 의해 단 한번의 계산으로 결정되는 자료구조 (검색 트리와 상반)
평균 상수 시간에 삽입, 삭제, 검색 매우 빠른 응답을 요하는 응용에 유용
- 예 : 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은 오버헤드 필요
– 연결리스트를 위한 공간
• 적재율이 그리 높지 않을 때는 개방 조사 방법이 더 매력적인 경우가 많다.
– 예를 들면 ½이하
자료참조 - 쉽게 배우는 알고리즘 · 관계 중심의 사고법 / 문병로