해시
키에 대응하는 값을 저장하는 자료구조
삽입(insert), 삭제(erase), 탐색(find), 갱신(update)이 모두 O(1) 으로 이루어진다.
키에 따라서 배열의 적절한 인덱스를 값을 찾아주는 해시 함수에 따라서 테이블로 관리를 한다. 이러한 테이블을 해시 테이블이라고 한다.
충돌 회피
서로 다른 키가 중복된 해시 값을 가지는 경우에 충돌이 발생한다.
이런 충돌을 회피할 수 있도록 하는 방법으로는 chaining과 open addressing이 존재한다.
두 가지 방법은 다음과 같이 충돌을 회피한다.
chaining
각 인덱스를 연결리스트로 구성해서 같은 해시 값을 가지는 키가 존재하면 해당 인덱스의 리스트에 원소를 추가한다.
같은 해시 값을 가지는 원소가 매우 많으면 리스트를 순회하는데에 오랜 시간이 걸린다.
N개의 원소가 있을 때 최악의 경우, 모든 원소가 하나의 insert를 제외한 erase, find, update 함수는 O(N)이 되어 버린다는 단점이 있다. 이러한 단점을 보완하기 위해서는 적절한 해시 값을 설정할 수 있는 좋은 해시 함수를 정해야 한다.
open addressing
해당하는 해시 값의 테이블에 이미 값이 존재하면 그 다음 칸에 저장한다.
고객의 카드번호를 키, 고객의 이름을 값으로 가지며, 고객의 카드번호의 마지막 네자리를 해시 값으로 가지는 경우에서 삽입, 탐색, 삭제를 진행하는 경우를 살펴보자.
insert
kim, lee, bae, yang 순서로 삽입을 하는 경우
kim은 해시 값으로 3333을 가지며, 해당 인덱스가 비어있으므로 3333에 저장된다.
lee는 해시 값으로 3333을 갖지만, 이미 kim이 존재하므로 비어있는 다음 칸인 3334에 저장된다.
bae는 해시 값으로 3334를 갖지만, 이미 lee가 존재하므로 비어있는 다음 칸인 3335에 저장된다.
yang은 해시 값으로 3333을 갖지만, 3333에 이미 값이 존재하고, 다음 칸인 3334에도 값이 존재하며, 3335에도 값이 존재하므로 다음 칸인 3336에 저장된다.
find
-
3492 0658 8348 3333(yang의 카드 번호)이 누구의 카드 번호인지 찾는 경우
해시값인 3333 인덱스부터 확인을 한다. 일치하지 않으므로 다음 인덱스인 3334를 확인하고, 계속해서 다음 인덱스를 확인하면 3336 인덱스에 해당 카드 번호가 존재하고 yang의 카드임을 알 수 있다. -
5555 6666 7777 3335(존재하지 않은 고객의 카드 번호)가 누구의 카드 번호인지 찾는 경우
해시값인 3335 인덱스부터 확인을 한다. 일치하지 않으므로 다음 인덱스인 3336, 3337을 확인한다.
3337 인덱스가 비어있으므로 저장되어 있지 않은 카드 번호임을 알 수 있다.
erase
6278 5651 9104 3333 카드 번호를 지우는 경우
find와 동일하게 3334 인덱스에 해당 카드 번호가 존재하는 것을 발견하여 삭제할 수 있다.
하지만 바로 제거하면 3335와 3336인덱스에 해당하는 정보들을 찾을 수 없게 된다.
따라서 해당 칸이 원래 값이 존재하던 상태임을 알려주어야 한다. 쓰레기 값을 넣어든지, 확인할 수 있는 배열을 따로 만들어어야 한다.
Linear Probing 선형 탐사
충돌이 발생하는 경우에 한 칸 이동하여 값을 저장하는 방식
장점
- 인접한 영역을 확인하여 연산을 수행할 수 있어 Cache hit rate가 높다.
단점
- Clustering이 생겨 성능에 영향을 줄 수 있다.
연산을 수행할 때 빈칸이 생길 때까지 이동하여 삽입, 탐색, 삭제를 진행하는데 linear probing을 이용하면 거의 대부분의 원소들이 붙어서 저장되어 있으므로 Clustering이 존재하면 수행 시간이 더 오래 걸릴 수 있다.
Quadratic Probing 제곱 탐사
충돌이 발생하는 경우에 1,3,5,..칸만큼 이동하여 값을 저장하는 방식
처음 칸을 기준으로 제곱만큼 이동하는 방식이다.
장점
- linear probing 만큼은 아니지만 Cache hit rate가 높다.
- 바로 옆 칸에 저장하는 것이 아니므로 Clustering을 회피할 수 있다.
단점
- 해시 값이 같으면 계속 동일한 경로를 따라가므로 여전히 Clustering이 존재한다
Double Hashing
충돌이 발생하면 이동할 칸을 새로운 해시 함수로 계산하는 방식
장점
- Clustering을 효과적으로 회피할 수 있다.
단점
- Cache hit rate가 낮다.
STL
unordered_set
원소를 해시 함수로 찾는 정렬되어 있지 않은 집합
unordered_multiset
unordered_set과 동일하지만 원소의 중복을 허용 집합
earse()
인자로 넣은 값을 모두 지우므로 유의해서 사용해야 한다.
erase(2)를 하는 경우 2를 하나만 제거하는 것이 아니라 모든 2가 사라지게 된다.
하나의 2만 지우고 싶다면 erase(s.find(2)) 와 같은 형태로 사용하여 iterator를 넘겨서 지워주어야 한다.
count()
인자로 들어온 수의 개수를 반환한다.
O(원소의 개수)만큼의 시간이 걸린다는 것을 유의해서 사용해야 한다.
unordered_map
키에 대응되는 값을 저장할 수 있는 자료구조
insert()
pair 형식으로 key와 value를 저장한다
insert({key, value})
find()
key에 해당하는 iterator를 반환한다
그래서 포인터로 →second 와 같은 형식으로 value값을 가져와야 한다
