Hash table
- 해쉬 테이블은 dynamic set을 구현하는 효과적인 방법의 하나
dynamic set : 탐색, 삽입, 삭제 3가지 연산을 지원하는 방법
- 적절한 가정하에서 평균 탐색, 삽입, 삭제시간 o(1)
- 보통 최악의 경우 o(n)
- 해쉬 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장
- h : U -> {0,1,2,...,m-1}
- 키 k가 h(k)로 해슁되었다고 말함
충돌
- 두 개 이상의 키가 동일한 위치로 해슁되는 경우
- 즉, 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 상황
- 일반적으로 U >> m이므로 항상 발생 가능
-충돌이 발생할 경우 대처 방법이 필요
- 대표적인 두 가지 충돌 해결 방법 : chaining과 open addressing
chaining
- 동일한 장소로 해슁된 모든 키들을 하나의 연결리스트(linked list)로 저장
- 키의 삽입
- 키 k를 리스트 T[h(k)]의 맨 앞에 삽입 : 시간복잡도 o(1)
- 중복된 키가 들어올 수 있고 중복 저장이 허용되지 않는다면 삽입시 리스트를 검색해야함. 따라서 시간복잡도는 리스트의 길이에 비례
- 키의 검색
- 리스트 T[h(k)]에서 순차검색
- 시간복잡도는 키가 저장된 리스트의 길이에 비례
-키의 삭제
- 리스트 T[h(k)]로 부터 키를 검색 후 삭제
- 일단 키를 검색해서 찾은 후에는 o(1)시간에 삭제 가능
- 최악의 경우는 모든 키가 하나의 슬롯으로 해슁되는 경우
- 길이가 n인 하나의 연결리스트가 만들어짐
- 따라서 최악의 경우 탐색시간은 o(n) + 해쉬함수 계산시간
- 평균시간복잡도는 키들이 여러 슬롯에 얼마나 잘 분배되느냐에 의해서 결정
SUHA(Simple Uinform Hashing Assumption)
- 각각의 키가 모든 슬롯들에 균등한 확률로(equally likely) 독립적으로 해슁된다느 가정
- 성능분석을 위해서 주로 하는 가정임
- hash함수는 deterministic하므로 현실에서는 불가능
- Load factor a = n/m
- n : 테이블에 저장될 키의 개수
- m : 해쉬테이블의 크기, 즉 연결리스트의 개수
- 각 슬롯에 저장된 키의 평균 개수
- 연결리스트 T[j]의 길이를 n라고 하면 E[n] = a
- 만약 n=o(m)이면 평균검색시간은 o(1)
Open Addressing
- 모든 키를 해쉬 테이블 자체에 저장
- 테이블의 각 칸(slot)에는 1개의 키만 저장
- 충돌 해결 기법
- Linear probing
- Quadratic probing
- Double hashing
Linear probing
h(k), h(k)+1, h(k)+2, .... 순서로 검사하여 처음으로 빈 슬롯에 저장 테이블의 끝이 도달하면 다시 처음으로 circular하게 들어감
- Linear probing의 단점
- primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미
- 이런 cluster가 생성되면 이 cluster는 점점 더 커지는 경향이 생김
-> cluster가 커지면 cluster의 길이만큼 탐색 시간이 걸리게 된다. '키 값이 원래 저장되어야 할 자리에서 멀어진다'를 의미
- Quadratic probing
- 충돌 발생시 h(k), h(k)+1^2, h(k)+2^2,h(k)+3^2,.... 순서로 시도
- Double hashing
- 서로 다른 두 해쉬 함수 h1과 h2를 이용하여
- h(k,i) = (h1(k) + i*h2(k)) mod m
h1(14) = 1
h2(14) = 4
- 처음에는 1을 보고 1이 채워져 있다면 1+4 즉 5를 보고 5가 채워져 있다면, 9를 본다.
Open Addressing - 키의 삭제
- 단순히 키를 삭제할 경우 문제가 발생
- 가령 A2, B2, C2가 순서대로 모두 동일한 해쉬함수값을 가져서 linear probing으로 충돌 해결
- B2를 삭제한 후 C2를 검색
- A2,B2,C2를 insert를 해서 2,3,4칸을 채운다 그 뒤에 B2를 삭제시키면 3칸이 비어있게 됨 이렇게 되면 C2를 검색하는데 문제가 발생
해결하기 위한 방법
- B2를 삭제한 뒤 C2를 옮겨야한다.
* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.
댓글