제6장 해시 테이블

http://academy.hanb.co.kr

쉽게 배우는 알고리즘

6장. 해시 테이블Hash Table IT COOKBOOK IT COOKBOOK

6장.해시 테이블

Hash Table

그에게서 배운 것이 아니라 이미 내 속에 있었던 것이 그와 공명을 한 것이다. - 제임스 왓슨

- 3 - 한빛미디어㈜

학습목표

• 해시 테이블의 발생 동기를 이해한다.

• 해시 테이블의 원리를 이해한다.

• 해시 함수 설계 원리를 이해한다.

• 충돌 해결 방법들과 이들의 장단점을 이해한

다.

• 해시 테이블의 검색 성능을 분석할 수 있도록

한다.

IT COOKBOOK IT COOKBOOK

저장/검색의 복잡도

• Array – O(n)

• Binary search tree

– 최악의 경우 Θ(n) – 평균 Θ(logn)

• Balanced binary search tree(e.g. red-black tree)

– 최악의 경우 Θ(log n)

• B-tree

– 최악의 경우 Θ(log n)

– Balanced binary search tree보다 상수 인자가 작다

• Hash table: 검색 효율의 극단

숙명여대 멀티미디어과학과 5

-• 원소가 저장될 자리가 원소의

값

에 의해

결정되는 자료구조

• 평균 상수 시간에 삽입, 삭제, 검색

• 매우 빠른 응답을 요하는 응용에 유용

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

• Hash table은 최소 원소를 찾는 것과 같은

작업은 지원하지 않는다

Hash Table

IT COOKBOOK IT COOKBOOK

주소 계산

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

숙명여대 멀티미디어과학과 7 -입력: 25, 13, 16, 15, 7 0 13 1 2 15 3 16 4 5 6 7 7 8 9 10 11 12 25

Hash function h(x) = x mod 13 적재율(load factor) = 5/13

크기 13인 Hash Table에 5 개의 원소가 저장된 예

IT COOKBOOK IT COOKBOOK

• 해시 함수의 요구조건

– 입력 원소가 hash table에 고루 저장되어야 한다. • 서로 다른 원소가 한 주소에 충돌할 확률이 작아지기 때문 – 계산이 간단해야 한다.

• 여러 가지 방법이 있으나 가장 대표적인 것은

division method

와

multiplication method

이다

숙명여대 멀티미디어과학과 9

-• h(x) = x mod m

• m: table 사이즈

– 대개 2의 멱수에 가깝지 않은 소수가 바람직

– m = 2

p

_{라면 입력 원소의 하위 p비트에 의해}

해시값이 결정되는 문제가 있음

– 해시값은 입력 원소의 모든 비트를 이용하는

것이 바람직

해시 함수 1 – Division Method

IT COOKBOOK IT COOKBOOK

• 원리

– 먼저 입력 값을 0과 1 사이의 수로 대응시키고 – 해시 테이블 크기 m을 곱하여 0 ~ m-1 사이로 팽창시킨다.

• 구현

– x에 A를 곱한 다음 소수부만 취한다. – 방금 취한 소수부에 m을 곱하여 그 정수부를 취함 h(x) = m(xA mod 1) A: 0 < A < 1 인 상수 – m은 굳이 소수일 필요 없다. 따라서 보통 2p _으로 잡는다(p 는 정수) – 크누스는 잘 작동하는 A 값으로 ( 5-1)/2를 제안

해시 함수 2 – Multiplication Method

숙명여대 멀티미디어과학과 11 -xA mod 1 0 1 0 1 m-1 x m (xA mod 1) Multiplication method의 작동 예 - m: 65,536, A=0.6180339887 - 원소 1,025,390의 해시값을 구해보자. • xA = 1,025,390 * 0.6180339887 = 633,725.871673093 • 여기서 소수부는 .871673093이고, • 해시 테이블 크기 m을 곱하면 57,125.967… • 결국, 원소 1,025,390의 해시 주소는 57,125로 결정됨. IT COOKBOOK IT COOKBOOK

• Hash table의 한 주소를 놓고 두 개 이상의 원소가

자리를 다투는 것

– Hashing을 해서 삽입하려 했으나 이미 다른 원소가 자리를 차지하고 있는 상황

• Collision resolution 방법은 크게 두 가지가 있음

– Chaining – Open Addressing

Collision

숙명여대 멀티미디어과학과 13

-Collision의 예

입력: 25, 13, 16, 15, 7 0 13 1 2 15 3 16 4 5 6 7 7 8 9 10 11

12 25 Hash function h(x) = x mod 13

29를 삽입하려 하자 이미 다른 원소가 차지하고 있다! h(29) = 29 mod 13 = 3 IT COOKBOOK IT COOKBOOK

• Chaining

– 같은 주소로 hashing되는 원소를 모두 하나의 linked list로 관리한다 – 해시 테이블 외에 추가적인 linked list 필요

• Open addressing

– Collision이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결한다 – 추가적인 공간이 필요하지 않다

Collision Resolution

숙명여대 멀티미디어과학과 15 -1 2 3 4 5 6 7 8 9 0 39 13 40 94 3 42 43 44 70 86 47 55 74 76 10 11 12

Chaining을 이용한 Collision Resolution의 예

• 효율을 위해 리스트에 삽입 시 리스트 맨 앞에 삽입함. – 리스트 순서는 삽입 역순임 • 원소 삭제 시에는 리스트에서 삭제하면 됨 • 교재 203p. 알고리즘 6-1 • 장점: 적재율이 1을 넘어도 사용할 수 있음 IT COOKBOOK IT COOKBOOK

• 빈자리가 생길 때까지 해시값을 계속 만들어냄

– 충돌이 일어나도 어떻게든 주어진 테이블 공간에서 해결한다. – h₀(x), h₁(x), h₂(x), h₃(x), … – 단점: 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음

• 충돌 시 다음 주소를 결정하는 세가지 방법

– 선형조사(Linear probing) – 이차방정식 조사(Quadratic probing) – 더블 해싱(Double hashing )

Open Addressing

숙명여대 멀티미디어과학과 17 -예: 입력 순서 25, 13, 16, 15, 7, 28, 31, 20, 1, 38 0 13 1 2 15 3 16 4 28 5 6 7 7 8 9 10 11 12 25 0 13 1 1 2 15 3 16 4 28 5 31 6 38 7 7 8 20 9 10 11 12 25 0 13 1 2 15 3 16 4 28 5 31 6 7 7 8 20 9 10 11 12 25

선형 조사(Linear Probing)

hi(x) = (h(x) + i) mod m // 충돌이 일어난 바로 뒷 자리를 본다는 의미 hi(x) = (h(x) + i) mod 13 IT COOKBOOK IT COOKBOOK 0 1 2 15 3 16 4 28 5 31 6 44 7 8 9 10 11 37 12 Primary clustering의 예

Linear Probing은 Primary Clustering에 취약하다

일차 군집(Primary clustering): 특정 영역에 원소가 몰리는 현상 • 군집 영역이 커질수록 해당 군집 영역으로 해싱될 가능성이 커짐 – 군집이 심하지 않은 영역에 비해 영역의 크기가 빨리 커짐 • 그러다 두 개의 군집된 영역이 붙으면 영역이 갑자기 커지기도 함.

숙명여대 멀티미디어과학과 19 -0 1 2 15 3 4 43 5 18 6 45 7 8 30 9 10 11 37 12

이차방정식 조사(Quadratic Probing)

hi(x) = (h(x) + c1i2+ c2i) mod m 예: 입력 순서 15, 18, 43, 37, 45, 30 hi(x) = (h(x) + i2) mod 13 • h(x), h(x)+1, h(x)+4, h(x)+9, … – 선형 조사에서 처럼 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있기를 기대함. • 단점: 여러 개의 원소가 같은 초기 해시값을 갖게 되면 모두 같은 순서로 조사할 수 밖에 없음. IT COOKBOOK IT COOKBOOK Secondary clustering의 예

Quadratic Probing은 Secondary Clustering에 취약하다

0 1 2 15 3 28 4 5 54 6 41 7 8 21 9 10 11 67 12 Secondary clustering: 여러 개의 원소가 동일한 초기 해시 함수 값을 갖는 현상 • hi(x) = (h(x) + i2) mod 13 이라면 – 원소 28: 두 번 만에 빈자리 찾음 – 원소 41: 세 번 만에 – 원소 67: 네 번 만에 – 원소 54: 다섯 번 만에 빈자리를 찾음. • 보폭은 넓어지지만 최초의 해시값이 같은 원소들은 이로 인해 이득을 보지 못함.

숙명여대 멀티미디어과학과 21 -0 1 2 15 3 4 67 5 6 19 7 8 9 28 10 11 41 12 h0(15) = h0(28) = h0(41) = h0(67) = 2 // 첫 해시 함수값은 모두 2 h1(67) = (2 + 1*((67 mod 11)+1)) mod 13 = 4 h1(28) = (2 + 1*((28 mod 11)+1)) mod 13 = 9 h1(41) = (2 + 1*((41 mod 11)+1)) mod 13 = 11

더블 해싱(Double Hashing)

hi(x) = (h(x) + i f (x)) mod m 예: 입력 순서 15, 19, 28, 41, 67 - 첫 해시값이 같더라도 두 번째 해시값이 같을 확률은 매우 작아 서로 다른 보폭으로 점프 - 2차 군집 문제 발생 안 함 h(x) = x mod 13 f(x) = (x mod 11) + 1 h_i(x) = (h(x)+i f(x)) mod 13 m’: m 보다 조금 작은 소수로 잡는 것이 바람직 IT COOKBOOK IT COOKBOOK

더블 해싱에서 두 번째 해시 함수 f(x)

• f(x)의 특징

– 해시 테이블 크기 m과 서로 소인 값이어야 바람직

• 만약 f(x)와 m이 1보다 큰 최소공약수 d를

가진다면?

– x의 자리를 찾기 위해 해시 테이블 전체 중 기껏해야 m/d 밖에 보지 못함.

• 권고

– 해시 테이블 크기 m을 소수로 잡고, – f(x)의 값이 항상 m 보다 작은 자연수가 되게 하면 이들이 항상 서로 소가 될 수 있음.

숙명여대 멀티미디어과학과 23 -0 13 1 1 2 15 3 16 4 28 5 31 6 38 7 7 8 20 9 10 11 12 25 0 13 1 2 15 3 16 4 28 5 31 6 38 7 7 8 20 9 10 11 12 25 0 13 1 DELETED 2 15 3 16 4 28 5 31 6 38 7 7 8 20 9 10 11 12 25 (a) 원소 1 삭제 (b) 38 검색, 문제발생 (c) 표식을 해두면 문제없다

삭제 시 조심할 것

선형 조사를 예를 들면: IT COOKBOOK IT COOKBOOK

• 적재율(Load factor) α

– Hash table 전체에서 얼마나 원소가 채워져 있는지를 나타내는 수치 – Hash table에 n 개의 원소가 저장되어 있다면 α = n/m 이다

• Hash table에서의 검색 효율은 적재율과 밀접한

관련이 있다.

Hash Table에서의 검색 시간

숙명여대 멀티미디어과학과 25

-• 정리 1

– Chaining을 이용하는 hashing에서 load factor가 α일 때, 실패하는 검색에서 probe 횟수의 기대치는 α 이다

• 정리 2

– Chaining을 이용하는 hashing에서 load factor가 α일 때, 성공하는 검색에서 probe 횟수의 기대치는 1 + α/2 + α/2n 이다. – 증명: 교재 213p 참조.

Chaning에서의 검색 시간

IT COOKBOOK IT COOKBOOK

• Assumption (uniform hashing)

– Probe 순서 h₀(x), h₁(x), …, h_m-1(x)가 0부터 m-1 사이의 수로 이루어진 permutation을 이루고, 모든 permutation은 같은 확률로 일어난다

• 정리 3

– Load factor α=n/m 인 open addressing hashing에서 실패하는 검색에서 probe 횟수의 기대치는 최대 1/(1- α )이다

• 정리 4

– Load factor α=n/m 인 open addressing hashing에서 성공하는 검색에서 probe 횟수의 기대치는 최대 (1/ α) log(1/(1- α)) 이다

숙명여대 멀티미디어과학과 27

-• Load factor가 높아지면 일반적으로 hash

table의 효율이 떨어짐

• 과도한 적재율 방지 알고리즘

– 일반적으로, threshold을 미리 설정해 놓고 적재율이 이에 이르면, – Hash table의 크기를 두 배로 늘인 다음, – hash table에 저장되어 있는 모든 원소를 다시 hashing하여 저장한다.

Load Factor가 우려스럽게 높아지면

IT COOKBOOK IT COOKBOOK

생각해 볼 것

• Load factor가 아주 낮으면 각 probing 방법들이

차이가 많이 나는가?

• 성공적인 검색과 삽입의 관계는?

– [정리 4]의 증명과도 관계 있음

- 29 - 한빛미디어㈜