티스토리 뷰
인프런에서 권오흠 교수님의 알고리즘 강좌를 듣고 필기한 내용이다.
수강한 파트는 Hashing이다.
해쉬 테이블은 dynamic set을 구현하는 효과적인 방법의 하나
- 적절한 가정하에서 평균 탐색, 삽입, 삭제 시간 O(1)
- 보통 최악의 경우 theta(n)
해쉬 테이블이란
- 해쉬 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장
- h : U -> {0, 1, ..., m-1}
여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합 (U의 예 -> 모든 자연수의 집합)
- 키 k가 h(k)로 해슁되었다고 한다.
- 해쉬 테이블은 일반적으로 하나의 배열
- index = h(k) : 즉, 각 키에 대한 해쉬함수 값을 그 키를 저장할 배열 인덱스로 사용함
해쉬 함수의 예
- 모든 키들을 자연수라고 가정.
- 예: 문자열
- ASCII 코드 : C=67, L=76, R=82, S=83
- 문자열 CLRS는 (67 * 128^3) + (76 * 128^2) + (82 * 128^1) + (83 * 128^0) = 141,764,947
- 해쉬 함수의 간단한 예
- h(k) = k % m, 즉 key를 하나의 자연수 k로 해석한 후 테이블의 크기 m으로 나눈 나머지
- 항상 0 ~ m-1 사이의 정수가 됨
충돌(Collision)
- 두 개 이상의 키가 동일한 위치로 해슁되는 경우
- 즉, 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 상황
- 일반적으로 |U| >> m 이므로 항상 발생 가능
- 만약 |K| > m 이라면 당연히 발생 (K는 실제로 저장된 키들의 집합)
- 충돌이 발생할 경우 대처 방법이 필요하다
- 대표적인 두 가지 충돌 해결 방법 : chaining과 open addressing
chaining에 의한 충돌 해결
동일한 장소로 해슁된 모든 키들을 하나의 연결리스트(Linked List)로 저장
- 키의 삽입(Insertion)
- 키 k를 리스트 T[h(k)]의 맨 앞에 삽입: 시간 복잡도 O(1)
- 중복된 키가 들어올 수 있고 중복 저장이 허용되지 않는다면 삽입시 리스트를 검색해야 함.
따라서 시간 복잡도는 리스트의 길이에 비례함
- 키의 검색(Search)
- 리스트 T[h(k)]에서 순차검색
- 시간복잡도는 키가 저장된 리스트의 길이에 비례
- 키의 삭제(Deletion)
- 리스트 T[h(k)]로 부터 키를 검색 후 삭제
- 일단 키를 검색해서 찾은 후에는 O(1)시간에 삭제 가능
- 최악의 경우는 모든 키가 하나의 슬롯으로 해슁되는 경우
- 길이가 n인 하나의 연결리스트가 만들어짐
- 따라서 최악의 경우 탐색시간은 theta(n) + 해쉬함수 계산시간
- 평균시간복잡도는 키들이 여러 슬롯에 얼마나 잘 분배되느냐에 의해서 결정
SUHA(Simple Uniform Hashing Assumption)
- 각각의 키가 모든 슬롯들에 균등한 확률로 독립적으로 해슁된다는 가정
- 성능분석을 위해 주로 하는 가정임
- hash함수는 deterministic하므로(특정 key에 대하여 random하게 index가 계산되는 것이 아니므로) 현실에서는 불가능
- Load factor a = n / m (SUHA라는 가정`에 따른 정리임)
- n : 테이블에 저장될 키의 개수
- m : 해쉬 테이블의 크기, 즉 연결리스트의 개수
- 각 슬롯에 저장된 키의 평균 개수
- 연결리스트 T[j]의 길이를 nj라고 하면 E[nj] = a
- 만약 n = O(m)이면 평균 검색시간은 O(1)
Open Addressing에 의한 충돌 해결
- 모든 키를 해쉬 테이블 자체에 저장
- 테이블의 각 칸(slot)에는 1개의 키만 저장
- 충돌 해결 기법
- Linear Probing
- Quadratic probing
- Double hashing
Open Addressing - Linear Probing
- h(k), h(k) + 1, h(k) + 2, ... 순서로 검사하여 처음으로 빈 슬롯에 저장
테이블의 끝에 도달하면 다시 처음으로 circular하게 돌아감
Linear Probing의 단점
- primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미
- 이런 cluster가 생성되면 이 cluster는 점점 더 커지는 경향이 생김
- Quadratic probing (항상 offset이 동일)
- 충돌 발생시 h(k), h(k) + 1^2, h(k) + 2^2, h(k) + 3^2, ... 순서로 시도
- Double hashing (키 값에 따라 offset이 다름)
- 서로 다른 두 해쉬 함수 h1과 h2를 이용하여 <- 엄밀하게 말하면, 두번째 해쉬 함쉬 h2는 0이 나오면 안됨
h(k, i) = (h1(k) + i * h2(k)) mod m
Open Addressing - 키의 삭제
- 단순히 키를 삭제할 경우 문제가 발생
- 가령 A2, B2, C2가 순서대로 모두 동일한 해쉬 함수값을 가져서 linear probing으로 충돌 해결
- B2를 삭제한 후 C2를 검색 => index 3이 비어있어서, 문제 발생
- index 3을 deleted로 표시하던가, index 3 으로 다른 키를 옮기던가 하는 등의 조치가 필요함
'모각코' 카테고리의 다른 글
모각코 5일차 결과 (2. 10) (0) | 2019.02.10 |
---|---|
모각코 5일차 목표 (2. 10) (1) | 2019.02.10 |
모각코 4일차 목표 (1.31) (0) | 2019.01.31 |
모각코 3일차 결과 (1.25) (0) | 2019.01.26 |
모각코 3일차 목표 (1.25) (0) | 2019.01.25 |