7장. 해시 테이블Hash Table

7장.해시 테이블Hash Table 그에게서 배운 것이 아니라 이미 내 속에 있었던 것이 그와 공명을 한 것이다. - 머레이 겔만

학습목표 해시 테이블의 발생 동기를 이해한다. 해시 테이블의 원리를 이해한다. 해시 함수 설계 원리를 이해한다. 충돌 해결 방법들과 이들의 장단점을 이해한다. 해시 테이블의 검색 성능을 분석할 수 있도록 한다.

저장/검색의 복잡도 배열 이진검색트리 균형잡힌 이진검색트리(예: 레드블랙트리) B-트리 해시 테이블 O(n) 평균 Θ(log n) 균형잡힌 이진검색트리(예: 레드블랙트리) 최악의 경우 Θ(log n) B-트리 Balanced binary search tree보다 상수 인자가 작다 해시 테이블 평균 Θ(1)

해시 테이블 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조 평균 상수 시간에 삽입, 삭제, 검색 매우 빠른 응답을 요하는 응용에 유용 예: 119 긴급구조 호출과 호출번호 관련 정보 검색 주민등록 시스템 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않는다

주소 계산 검색키 주소계산 배열 모양의 테이블

크기 13인 해시 테이블에 5 개의 원소가 저장된 예 해시함수 h(x) = x mod 13 입력: 25, 13, 16, 15, 7 13 1 2 15 3 16 4 5 6 7 8 9 10 11 12 25 해시함수 h(x) = x mod 13

해시 함수 입력 원소가 해시 테이블에 고루 저장되어야 한다 계산이 간단해야 한다 여러 가지 방법이 있으나 가장 대표적인 것은 나누기 방법과 곱하기 방법이다

곱하기 방법Multiplication Method 해시 함수 나누기 방법Division Method h(x) = x mod m m: 해시 테이블 사이즈. 대개 소수임. 곱하기 방법Multiplication Method h(x) = (xA mod 1) * m A: 0 < A < 1 인 상수 m은 굳이 소수일 필요 없다. 따라서 보통 2p 으로 잡는다(p 는 정수)

x xA mod 1 1 1 m (xA mod 1) 곱하기 방법의 작동 과정 m-1

충돌Collision 해시 테이블의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것 충돌 해결 방법은 크게 두 가지가 있다 체이닝Chaining 개방주소 방법Open Addressing

충돌의 예 h(29) = 29 mod 13 = 3 29를 삽입하려 하자 이미 다른 원소가 차지하고 있다! 입력: 25, 13, 16, 15, 7 13 1 2 15 3 16 4 5 6 7 8 9 10 11 12 25 h(29) = 29 mod 13 = 3 29를 삽입하려 하자 이미 다른 원소가 차지하고 있다! 해시함수 h(x) = x mod 13

충돌 해결Collision Resolution 체이닝 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트linked list로 관리한다 추가적인 연결 리스트 필요 개방주소 방법 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결한다 추가적인 공간이 필요하지 않다

체이닝 39 13 1 40 2 3 94 3 42 55 4 43 5 44 70 6 7 8 86 47 9 74 10 11 76 12

개방주소 방법 빈자리가 생길 때까지 해시값을 계속 만들어낸다 중요한 세가지 방법 h0(x), h1(x), h2(x), h3(x), … 중요한 세가지 방법 선형 조사 이차원 조사 더블 해싱

선형 조사Linear Probing hi(x) = (h(x) + i) mod m 예: 입력 순서 25, 13, 16, 15, 7, 28, 31, 20, 1, 38 13 1 2 15 3 16 4 28 5 6 7 8 9 10 11 12 25 13 1 2 15 3 16 4 28 5 31 6 7 8 20 9 10 11 12 25 13 1 2 15 3 16 4 28 5 31 6 38 7 8 20 9 10 11 12 25 hi(x) = (h(x) + i) mod 13

선형 조사는 1차군집에 취약하다 1차군집의 예 1차군집: 특정 영역에 원소가 몰리는 현상 1 2 15 3 16 4 28 5 1 2 15 3 16 4 28 5 31 6 44 7 8 9 10 11 37 12 1차군집의 예

이차원 조사Quadratic Probing hi(x) = (h(x) + c1i2 + c2i) mod m 예: 입력 순서 15, 18, 43, 37, 45, 30 1 2 15 3 4 43 5 18 6 45 7 8 30 9 10 11 37 12 hi(x) = (h(x) + i2 ) mod 13

이차원 조사는 2차군집에 취약하다 2차군집의 예 2차군집: 여러 개의 원소가 동일한 초기 해시 함수값을 갖는 현상 1 2 15 1 2 15 3 28 4 5 54 6 41 7 8 21 9 10 11 67 12 2차군집의 예

더블 해싱Double Hashing hi(x) = (h(x) + i f (x)) mod m h(x) = x mod 13 예: 입력 순서 15, 19, 28, 41, 67 1 2 15 3 67 4 5 6 19 7 8 28 9 10 41 11 12 h0(15) = h0(28) = h0(41) = h0(67) = 2 h1(67) = 3 h1(28) = 8 h(x) = x mod 13 h1(41) = 10 f(x) = x mod 11 hi(x) = (h(x)+i f(x)) mod 13

삭제시 조심할 것 (a) 원소 1이 삭제된다 (b) 38 검색, 문제발생 (c) 표식을 해두면 문제없다 13 1 2 15 3 13 1 2 15 3 16 4 28 5 31 6 38 7 8 20 9 10 11 12 25 13 1 2 15 3 16 4 28 5 31 6 38 7 8 20 9 10 11 12 25 13 1 DELETED 2 15 3 16 4 28 5 31 6 38 7 8 20 9 10 11 12 25 (a) 원소 1이 삭제된다 (b) 38 검색, 문제발생 (c) 표식을 해두면 문제없다

해시 테이블에서의 검색 시간 적재율 α 해시 테이블에서의 검색 효율은 적재율과 밀접한 관련이 있다 해시 테이블 전체에서 얼마나 원소가 차 있는지를 나타내는 수치 해시 테이블에 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- α)) 이다

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

생각해 볼 것 적재율이 아주 낮으면 각 조사 방법들이 차이가 많이 나는가? 성공적인 검색과 삽입의 관계는? [정리 4]의 증명과도 관계 있음 ~11/3/2003

Thank you