9일차 강의 (21강)

해시 (21강)

해시함수 : 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수

 

충돌문제 발생 (해시에 성능에 큰 영향)

 

충돌 회피 1 - Chaining

 

충돌 회피 2 - Open addressing

 

- Linear Probing

충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식

장점 - Cache hit rate가 높다.

단점 - Clustering이 생겨 성능에 영향을 줄 수 있다.

 

- Quadratic probing

충돌 발생 시 오른쪽으로 1,3,5,... 칸씩 이동하는 방식

장점 - Cache hit rate가 나쁘지 않다, Clustering을 어느 정도 회피할 수 있다.

단점 - 해시 값이 같을 경우 여전히 Clustering이 발생한다.

 

- Double Hashing

충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식

장점 - Clustering을 효과적으로 회피할 수 있다.

단점 - Cache hit rate가 낮다

 

unordered_set

원소들이 크기 순서 혹은 삽입한 순서로 위치해있지 않음 (순서 보장X)

 

unordered_multiset

원소들의 중복을 허용

※ 주의 : erase()하면 해당하는 모든 원소가 지워짐(중복된 것들)

→ 하나만 지우려면 ms.erase(ms.find(-10))과 같이 iterator 이용

 

unorderded_map