[Set, Map / Hash] C++ Set / Map / Hash

 

 

Set, Map, HashSet, HashMap

이번 챕터에서는 알고리즘 테스트에서 자주 등장하는 Set, Map, HashSet, HashMap에 대해 알아보겠습니다.

특히 HashMap은 알고리즘 문제뿐만 아니라 실제 개발 업무에서도 매우 자주 사용되는 컨테이너이므로, 동작 원리와 특징을 정확하게 이해하고 넘어가는 것이 중요합니다.

이번 챕터에서는 다음과 같은 내용을 학습합니다.

1. Set과 Map

• Set과 Map의 기본 개념
• 내부 자료구조와 동작 방식
• 왜 O(log N)의 시간 복잡도를 가지는지

2. HashSet과 HashMap

• HashSet과 HashMap의 기본 개념
• 해시(Hash)를 이용한 데이터 저장 방식
• 평균적으로 O(1)의 시간 복잡도를 가지는 이유

3. 사용 시 주의할 점

• 해시 충돌(Hash Collision)이 발생하는 이유
• HashSet과 HashMap을 사용할 때 성능에 영향을 주는 요소
• 상황에 맞는 컨테이너 선택 방법

 

 

 

간단한 개념 정리

Set

• 중복을 허용하지 않는 데이터를 저장하는 컨테이너입니다.
• C++의 std::set은 일반적으로 균형 이진 탐색 트리(Red-Black Tree)로 구현됩니다.
• 데이터는 자동으로 정렬되며, 탐색·삽입·삭제의 시간 복잡도는 O(log N)입니다.

Map

• Key와 Value를 한 쌍으로 저장하는 컨테이너입니다.
• Key는 중복될 수 없으며, Key를 기준으로 자동 정렬됩니다.
• std::map 역시 균형 이진 탐색 트리로 구현되며, 탐색·삽입·삭제는 O(log N)입니다.

HashSet

• Set과 동일하게 중복을 허용하지 않는 데이터를 저장하지만, 내부적으로 해시 테이블(Hash Table)을 사용합니다.
• 평균적으로 탐색·삽입·삭제가 O(1)에 수행됩니다.
• C++에서는 std::unordered_set으로 제공됩니다.

HashMap

• Key와 Value를 저장하는 컨테이너로, 내부적으로 해시 테이블을 사용합니다.
• 평균적으로 탐색·삽입·삭제가 O(1)에 수행됩니다.
• C++에서는 std::unordered_map으로 제공됩니다.
• 알고리즘 문제와 실무에서 가장 많이 사용되는 STL 컨테이너 중 하나입니다.

 

 

 

이러한 컨테이너들의 내부 동작 원리와 시간 복잡도를 이해하고, 상황에 따라 어떤 컨테이너를 선택해야 하는지까지 알아보겠습니다.