+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.
해시 테이블
< 탐색을 지원하는 집합을 구현하는 방법 >
1. 배열- 최악의 경우: O(n)
2. 이진 탐색
- 평균: O(log n)
- 최악의 경우: O(n)
3. Red - Black Tree
- 최악의 경우: O(logn)
4. B - Tree
- 최악의 경우: O(log n)
- 트리의 높이가 작다.
O(log n) 보다 빨리 풀 수 있는가?
=> 해시 테이블 (Hash Table) 사용
- 평균: O(1)
가장 단순한 방식의 해시 테이블 구현
1 ~ N 사이의 수 k개가 원소인 집합을 다음과 같이 구현한다.
1. 크기가 N인 배열 A를 생성한다.
2. 수 i가 이 집합의 원소라면, A[i] = 1, 아니면 A[i] = 0로 설정한다.
- 삽입 시 소요시간: O(1)
- 삭제 시 소요시간: O(1)
- 검색 시 소요시간: O(1)
< 문제점 >
=> N이 매우 큰 수라면, 배열의 A의 대부분이 비어있으므로 메모리 낭비가 크다.
해쉬 함수를 이용한 해시 테이블 구현
해쉬 테이블
= 원소가 저장될 자리가 원소의 값에 의해 바로 결정되는 자료구조
x가 저장될 자리를 h(x)에 해당하는 칸으로 결정한다. (O(1) 시간에 결정)
+ 탐색 트리의 경우, 원소의 값에 의해 결정되지만, 트리를 탐색해서 내려가야한다.
탐색 외에 다른 연산은 지원하지 않는다.
(존재 여부만 확인)
+ 이진 탐색 트리의 경우, 최소값, 특정 값 바로 이전 값, 바로 다음 값 등을 찾을 수 있다.
아이디어
빠르게 계산할 수 있는 함수( = 해시 함수)를 이용하여 원소가 저장될 위치를 결정한다.
해쉬 함수: h(x) = (ax + b) mod p
+ a, b는 서로소, p는 소수이다. (p는 해시 테이블 크기)
=> 값을 균등하게 배분할 수 있을수록 좋다.
ex) {25, 13, 16, 15, 7}을 해시 테이블에 저장
h(x) = x mod 13
< 위 예시의 문제점 >
1. p로 나눈 나머지가 같을 경우, 다음에 저장할 원소를 저장할 수 없고, 찾을 수 없다. (충돌)
ex) 다음에 저장할 원소가 38이라면, 13으로 나눈 나머지가 12로 25와 같다.
ex) 29가 존재하는지 찾는다면, h(29) = 3이다. A[3]에 값이 있지만 29이 아닌 16이 있다.
2. 빈칸이 많아 메모리 낭비가 크다.
충돌 문제
테이블에 p로 나눈 나머지가 같은 키 값을 삽입할 경우, 키의 충돌이 발생한다.
=> 키를 어디에 저장할지, 저장한 키를 어떻게 찾을지를 설정해야한다.
ex) {25, 13, 16, 15, 7}이 해시 테이블에 다음 값을 삽입한다. (h(x) = x mod 13)
해시 체인
=> 키들을 연결 리스트로 저장한다.
+ 배열의 크기보다 더 많은 값을 저장할 수 있다.
< 문제점 >
=> 같은 인덱스에 저장된 키 값들이 서로 붙어있을 것처럼 보이지만 사실 메모리가 서로 떨어져 있기 때문에 성능이 저하된다.
선형 조사
p로 나눈 나머지가 같을 경우 적용하는 함수
=> hi(x) = (h(x) + i) mod m
=> 다음 칸으로 한 칸씩 이동하여 빈 칸이 나오면 그 칸에 값을 저장한다.
< 문제점 >
=> 특정 영역에 원소들이 몰리는 일차 군집 문제가 발생한다.
즉, 상관없는 값을 읽고 비교하게 되므로 효율이 떨어지게 된다.
이차원 조사
p로 나눈 나머지가 같을 경우 적용하는 함수
=> hi(x) = (h(x) + i^2) mod m
=> 다음 칸으로 삽입에 실패한 횟수의 제곱 칸만큼 이동하여 빈 칸이 나오면 그 칸에 값을 저장한다.
< 문제점 >
=> p로 나눈 나머지가 같은 값을 계속해서 삽입할 경우, 계속 충돌이 벌어지는 이차 군집 문제가 발생한다.
ex) 28, 41, 54, 67은 모두 2에 들어가야하므로 계속해서 충돌이 일어난다.
선형조사와 마찬가지로, 상관없는 값을 읽고 비교하게 되므로 효율이 떨어지게 된다.
이중 해싱
p로 나눈 나머지가 같을 경우 적용하는 함수
=> hi(x) = (h(x) + i × f(x)) mod m
=> 다음 칸으로 f(x) 칸만큼 이동하여 빈 칸이 나오면 그 칸에 값을 저장한다.
f(x) = 1 + (cx + d) mod q
+ 적어도 1은 증가해야하므로 + 1, p와 q은 서로소이다.
이차 군집을 막기 위해, 똑같은 칸만큼 이동하는 대신 또 다른 해시 함수 f(x)를 이용한다.
ex) f(x) = 1 + (x mod 11)일 때,
h(28) = h(41) = h(67)
f(28) = 7, f(41) = 9, f(67) = 2
+ 테이블이 적당히 비어 있을 때 삽입하는 것이 성능에 좋다.
+ 삽입과 탐색은 같은 방식으로 탐색한다. (본질적으로 같다.)
해시 테이블 삭제
단순히 빈칸으로 남길 시, 다른 값들을 찾아갈 수 없는 현상이 발생한다.
=> 따라서 단순히 지우지 않고, DELETED로 표시한다.
DELETED는 빈 칸이므로 값을 쓸 수 있고, 탐색 시 다음 값으로 계속 진행할 수 있다.
- 삽입 시 DELETED 역할: 값이 없다!
- 탐색 시 DELETED 역할: 값이 있다!
ex) 예를 들어, 16을 지운다면 28을 찾아갈 수 없다.
검색 시간
저장된 원소 수 = n
해시 테이블의 크기 = m
적재율 a = n / m
- 평균적으로, 해시 테이블의 한 원소당 a만큼의 원소가 있다고 생각할 수 있으므로 평균 검색 시간은 1 + a이다. (p로 나눈 나머지가 같은 원소의 개수 = a)
비둘기집 정리에 의해 a > 0.5일 경우 일차 군집이 발생할 확률이 높다.
=> 해시 테이블의 크기를 두 배로 늘리고, 새로운 해시 함수를 사용하여 해시 테이블을 다시 만든다.
'Study > Algorithm Study' 카테고리의 다른 글
| [Algorithm] Segment Tree (1) | 2024.06.15 |
|---|---|
| BIT (Binary Indexed Tree) (2) | 2024.04.03 |
| [Algorithm] 탐색 트리 (0) | 2023.11.03 |
| [Algorithm] 정렬: 계수 정렬, 선택 문제 (1) | 2023.10.05 |
| [Algorithm] 정렬: 버킷 정렬, 기수 정렬 (0) | 2023.09.24 |
