배고파서 까먹고 만든 블로그 :: C++ Hash와 Map의 차이점 (tistory.com)
C++ Hash와 Map의 차이점
Hash와 Map의 차이점 STL에 보면 Map이라는 컨테이너가 있습니다. 이전에 정리한걸 다시 보면.. map - 특정 키(key)로 데이터를 접근하고 관리할 수 있다. - 키로 값에 접근하며 삽입과 삭제가 빠르다.
wonjayk.tistory.com
특정 키에 대한 값을 찾는 과정에서
* map: 키-값의 컬렉션을 나타내는 추상 데이터 유형
레드블랙트리 알고리즘을 이용함
* hashMap: 이름 그대로 hash table을 이용해서 키-값 관계를 유지하며,
순서는 보장되지 않지만 빠른 조회 및 검색 필요 시 사용됨
<C++에는 hash map이 없음>
그런데 STL 컨테이너를 보면 Hash Map은 없습니다. 이렇게 속도가 빠른데도 말이죠.
단지 자료가 정렬되지 않아서 그런걸까요?
아닙니다. Hash Map은 STL의 공식 컨테이너에는 속하지 않고 따로 구현된 STL 라이브러리를 사용하셔야합니다.
공식 컨테이너에 들어가지 못한 이유는 바로 탐색 성능이 안정적이지 못해서 입니다.
- map, set : 삽입, 삭제, 탐색 모두 O(log n) 보장
- list : 삽입, 삭제 O(1), 탐색, 임의 원소 접근 O(n) 보장
- vector : 삽입, 삭제, 탐색 O(n), 임의 원소 접근 O(1) 보장
Hash Map의 경우 Hashing Key를 이용해 데이터에 접근하는데 이 Hashing Key를 생성하는 방법은 여러가지입니다.
- 예를 들면, 구성하는 모든 자료를 각각의 바이트 별로 더하거나, 자릿수에 가중치를 두는 방법도 생각해 볼 수 있습니다.
- 이렇게 생성된 키를 이용해 배열의 인덱스로 사용하고 접근하기 때문에 접근 속도가 O(1)이 되는 것입니다.
하지만, Hashing Key가 겹쳐서 충돌이 일어나게 된다면 빈 영역을 찾아서 저장해야 합니다.
- 충돌이 한번 일어난 지역에서는 계속 충돌이 일어나기 때문에 그 근처에 자료가 몰리게 됩니다.
따라서, Hash Map에서는 Hashing Key를 얼마나 잘 생성하는가에 따라 성능이 좌우됩니다.
- Hashing Key 값이 랜덤하게 분포되어 있을 때 가장 좋은 성능을 발휘합니다.
출처: https://wonjayk.tistory.com/211 [배고파서 까먹고 만든 블로그:티스토리]
'CS > 자료구조 & 알고리즘' 카테고리의 다른 글
| 우선순위 큐 (0) | 2023.12.16 |
|---|---|
| 레드블랙트리 (0) | 2023.12.16 |
| 자료구조 장단점(C++) (0) | 2023.10.10 |
| 자료구조 장단점 (C# - 유니티) (0) | 2023.10.10 |
| 가장 빠른 정렬 알고리즘과 그렇게 생각하는 이유 (0) | 2023.10.01 |