[자료구조] Hash Table
Hash Table이란?
key와 value로 데이터를 저장하는 자료구조
해시테이블은 검색속도가 매우 빠르다. 그 이유는 내부적으로 배열(bucket)을 사용하여 데이터를 저장하기 때문
key 값에 해시함수를 적용해서 배열의 고유한 index를 생성하고 이 index를 기준으로 값을 찾는다.
해시테이블의 평균 시간복잡도는 O(1)이다.
Hash Collision (해시충돌)
keys로 들어가는 값의 hash 값이 같은 경우 hash collision이라고 한다.
위 문제를 해결하는 방법은?
Sol1) Separate Chaining (분리 연결법)
bucket에서 충돌이 나면 해당 값과 기존 값을 연결시키는 기법이다.
위 사진에서 John을 저장한 후 Sandra가 같은 hash값을 가져 둘이 충돌했다. 그래서 LinkedList를 이용하여 John 뒤에 Sandra를 연결시킨다.
즉, 데이터의 hash값이 변경되지 않는다.
Chaining의 장점
- 한정된 장소를 효율적으로 사용 가능
- 해시 함수를 선택하는 중요성이 상대적으로 적다.
- 상대적으로 적은 메모리를 사용 (미리 공간 할당 필요x)
Chaining의 단점
- 한 bucket ( 같은 hash값을 가진 경우) 에 데이터가 쏠리면 검색 효율이 낮아진다.
- 외부 저장 공간을 사용하게 된다.
Sol2) Open Addressing(개방주소법)
collision이 나는 경우, 비어있는 hash를 찾아 데이터를 저장하는 기법이다.
즉, 개방주소법에서의 해시테이블은 1개의 hash와 1개의 value가 매칭된다.
그럼, 비어있는 hash는 어떻게 찾을까?
- 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장한다.
- 제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장한다.
- 이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장한다.
Open Addressing의 장점
- 다른 저장공간 없이 해시테이블 내에서 데이터 저장이 가능
Open Addressing의 단점
- Hash 함수의 성능이 전체 해시테이블의 성능을 좌지우지한다.
- 데이터의 길이가 늘어나면 그의 해당하는 저장소를 마련해야 한다.
Hash Table의 단점
1. 순서가 있는 배열에서는 x
2. Hash Function의 의존도가 높다.
코드에 적용하기 [c++]
hash_map은 비표준 container지만 unordered_map은 STL 표준 Container이고 hash_map과 거의 동일한 기능을 제공한다. MSDN의 hash_map 페이지에서도 unordered_map 사용을 권장 중이다.
1. map
레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반
-> 모든 데이터는 정렬되어 저장된다.
검색 속도가 O(logN) 이다.
중복된 키를 가질 수 없다.
[STL map 기본 사용법] twpower.github.io/91-how-to-use-map-in-cpp
#include<map>
2. unordered_map
hash_table 기반
-> 각 node를 정렬 x
검색 속도가 O(1)이다.
[STL unordered_map 기본 사용법] math-coding.tistory.com/31
#include< unordered_map >
3. multimap
중복되는 key를 가질 수 있다.
STL map에 포함되므로 #include <map>으로 사용할 수 있다.
map과 동일하게 정렬되어 저장된다.