알고리즘 알고리즘
해시 테이블 (Hash Table)
Contents Contents
z 해시 테이블 z 해시 함수 z 충돌 해결
z 해시 테이블에서의 검색 시간 분석
3
해시 해시 테이블 테이블
z 저장 / 검색의 복잡도
배열
•
O
(n
) 이진 검색 트리
• 최악의 경우
Θ
(n
)• 평균
Θ
(logn
) 균형 잡힌 이진 검색 트리 (예: 레드 블랙 트리)
• 최악의 경우
Θ
(logn
) B-트리
• 최악의 경우
Θ
(logn
)• 균형 잡인 이진 검색 트리보다 상수 인자가 작다
해시 테이블
• 평균
Θ
(1)해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 해싱 (hashing)
산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식
검색 방법
• 키 값에 대해서 해싱 함수를 계산하여 주소를 구하고,
• 구한 주소에 해당하는 해시 테이블로 바로 이동
– 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패
해싱 함수(hashing function)
• 키 값을 원소의 위치로 변환하는 함수
해시 테이블(hash table)
• 해싱 함수에 의해서 계산된 주소의 위치에 항목을 저장한 표
5
해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 해싱의 주소 계산
검색 키 주소계산
배열 모양의 테이블
해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 해싱의 예 #1
[ 위치 번호에 따른 도서 찾기 ]
7
해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 해싱의 예 #2
[ 학번에 따른 강의실 좌석 배정 ]
해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 해싱의 용어
충돌 (collision)
• 서로 다른 키 값에 대해서 해싱 함수에 의해 주어진 버킷 주소가 같은 경우
• 충돌이 발생한 경우에 비어있는 슬롯에 동거자 관계로 키 값 저장
동거자 (synonym)
오버플로우 (overflow)
[ 동거자의 예 : 같은 좌석에 앉은 짝궁 ] [ 오버플로우의 예 ]
9
해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 해싱의 용어 (cont’d)
키 값 밀도
• 사용 가능한 전체 키 값들 중에서 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값의 개수 정도
적재 밀도 (Load Factor)
• 해시 테이블에 저장 가능한 키 값의 개수 중에서 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값의 개수 정도
개수 값의 키 전체 가능한 사용
개수 값의 키 사용중인 밀도 실제
값
키 =
개수 슬롯 개수 버킷
개수 값의 키 중인 사용 실제
개수 값의 키 전체 가능한 저장
테이블에 해시
개수 값의 키 사용중인 밀도 실제
적재
= ∗
=
해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 해시 테이블 (hash table)
원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
평균 상수 시간에 삽입, 삭제, 검색
매우 빠른 응답을 요하는 응용에 유용
• 예:
– 119 긴급구조 호출과 호출번호 관련 정보 검색 – 주민등록 시스템
해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지
않는다
11
해시 해시 테이블 테이블 (cont (cont ’ ’ d) d)
z 크기 13인 해시 테이블에 5 개의 원소가 저장된 예
입력: 25, 13, 16, 15, 7
25 12
11 10 9 8
7 7
6 5 4
16 3
15 2
1
13 0
해시함수 h ( x ) = x mod 13
해시 해시 함수 함수
z 해시 함수 (hash function)
해시 함수의 조건
• 해싱 함수는 계산이 쉬워야 한다.
• 해싱 함수는 충돌이 적어야 한다.
• 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.
13
해시 해시 함수 함수 (cont (cont ’ ’ d) d)
z 직접 해싱 (direct hashing)
어떠한 알고리즘도 사용하지 않으며 키가 곧 주소
• 키 값을 직접적인 해시 주소로 사용한다.
• 어떠한 동일 주소 및 주소 충돌이 발생하지 않도록 보장한다.
• 단점 : 공간의 낭비가 발생
해시 해시 함수 함수 (cont (cont ’ ’ d) d)
z 제산 잔여 해싱 (division remainder hashing)
나눗셈-나머지 방식(modulo division)
• 나머지 연산자 mod(C에서의 % 연산자)를 사용하는 방법
• 키 값 x 를 해시 테이블의 크기 m 으로 나눈 나머지를 해시 주소로 사용
• 해시 주소는 충돌이 발생하지 않고 고르게 분포하도록 생성되어야 하므로 키 값을 나누는 해시 테이블의 크기 M은 적당한 크기의 소수(prime number) 사용
h(x) = x mod m
15
해시 해시 함수 함수 (cont (cont ’ ’ d) d)
z 승산 해싱 (multiplication hashing)
곱하기 연산을 사용하는 방법
① x 에 A 를 곱한 다음 소수부만 취한다. A를 어떻게 잡느냐에 따라 분포에 영향
- A : 0 < A < 1 인 상수
② 방금 취한 소수부에 m (
해시 테이블 크기
)을 곱하여 그 정수부를 취한다.- m은 굳이 소수일 필요 없다. 따라서 보통 2
p으로 잡는다(p 는 정수).
h(x) = (xA mod 1) * m
해시 해시 함수 함수 (cont (cont ’ ’ d) d)
z 수 추출 해싱 (digit extraction hashing)
키 값을 이루고 있는 각 자릿수의 분포를 분석하여 해시 주소로 사용하는 방법
• 예)
– 여섯 자리 사원 번호를 사용하여 세 자리 주소(000~999)를 해싱할 수 있다.
– 첫 번째, 세 번째, 네 번째 수를 추출하여 그 값을 주소로 사용 가능
125870 Æ 158
122801 Æ 128
121267 Æ 112
…
123413 Æ 134
17
해시 해시 함수 함수 (cont (cont ’ ’ d) d)
z 중간 제곱 해싱 (midsquare hashing)
키 값을 제곱한 결과 값에 중간에 있는 적당한 비트를 주소로 사용하는 방법
• 서로 다른 키 값은 서로 다른 중간 제곱 함수 값을 갖게 된다.
• 예) 키 값 00110101 10100111에 대한 해시 주소 구하기
00110101 10100111 X 00110101 10100111 00001011001111101001 11101001001011110001
해시 주소
충돌 충돌 해결 해결
z 충돌 (collision)
해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것
입력: 25, 13, 16, 15, 7
25 12
11 10 9 8
7 7
6 5 4
16 3
15 2
1
13 0
해시함수 h(x) = x mod 13
29를 삽입하려 하자이미 다른 원소가 차지하고 있다!
h(29) = 29 mod 13 = 3
19
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
z 체이닝 (chaing)
해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 하는 방법
• 버킷에 슬롯을 동적으로 삽입-삭제하기 위해 연결 리스트를 사용 – 각 버킷에 대한 헤드 노드를 1차원 배열로 만들고 각 버킷에 대한 헤드
노드는 슬롯들을 연결 리스트로 가지고 있어서 슬롯의 삽입이나 삭제 연산을 쉽게 수행할 수가 있다.
– 버킷 내에서 원하는 슬롯을 검색하기 위해서는 버킷의 연결 리스트를 선형 검색한다.
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
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 [ 체이닝을 이용한 충돌 해결의 예 ]
21
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
z 개방 주소(open addressing) 방법
빈자리가 생길 때까지 해시 값을 계속 만들어낸다
•
h
0(x
),h
1(x
),h
2(x
),h
3(x
), … 중요한 세가지 방법
• 선형 조사
• 이차원 조사
• 더블 해싱
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
z 개방 주소 방법 : 선형 조사 (linear probing)
예: 입력 순서 25, 13, 16, 15, 7, 28, 31, 20, 1, 38
25 12
11 10 9 8
7 7
6 5
28 4
16 3
15 2
1
13 0
25 12
11 10 9
20 8
7 7
38 6
31 5
28 4
16 3
15 2
1 1
13 0
25 12
11 10 9
20 8
7 7
6
31 5
28 4
16 3
15 2
1
13 0
hi(x) = (h(x) + i) mod 13
h
i(x) = (h(x) + i) mod m
23
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
12
37 11
10 9 8 7
44 6
31 5
28 4
16 3
15 2
1 0
[ 1차 군집의 예 ]
“선형 조사는 1차 군집에 약하다”
1차 군집 : 특정 영역에 원소가 몰리는 현상
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
z 개방 주소 방법 : 이차원 조사 (quadratic probing)
12
37 11
10 9
30 8
7
45 6
18 5
43 4
3
15 2
1 0
예 : 입력 순서 15, 18, 43, 37, 45, 30
h
i(x) = (h(x) + i
2) mod 13
h
i(x) = (h(x) + c
1i
2+ c
2i) mod m
25
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
[ 2차 군집의 예 ]
“이차원 조사는 2차 군집에 약하다”
12
67 11
10 9
21 8
7
41 6
54 5
4
28 3
15 2
1 0
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
z 개방 주소 방법 : 더블 해싱 (double hashing): 충돌 시, 두 해시 함수의 함을 주소로 선택
11
41 10
9
28 8
7
19 6
5 4
67 3
15 2
1 0
h(x) = x mod 13 f(x) = x mod 11
h
i(x) = (h(x)+i f(x)) mod 13
h0(15) = h0(28) = h0(41) = h0(67) = 2h1(67) = 3
h1(28) = 8
h1(41) = 10 예 : 입력 순서 15, 19, 28, 41, 67
h
i(x) = (h(x) + i f (x)) mod m
27
충돌 충돌 해결 해결 (cont (cont ’ ’ d) d)
z 개방 주소 방법 (선형조사): 자료 삭제 시 주의
25 12
11 10 9
20 8
7 7
38 6
31 5
28 4
16 3
15 2
1 1
13 0
25 12
11 10 9
20 8
7 7
38 6
31 5
28 4
16 3
15 2
1
13 0
25 12
11 10 9
20 8
7 7
38 6
31 5
28 4
16 3
15 2
DELETED 1
13 0
(a) 원소 1이 삭제되었다 (b) 38을 검색하면, 없다고 판단. 문제발생. 원소 38은 주소 6에 저장
(c) 표식을 해두면 문제없다
