맵(map)과 unordered_map의 개념과 차이

 

 

1. 맵(map)

맵(map)은 각 키가 고유한 키-값 쌍의 모음을 저장하는 데이터 구조입니다. 연관 배열, 사전 또는 해시 맵이라고도 합니다. 맵의 기본 아이디어는 고유 키를 사용하여 해당 값을 효율적으로 검색하는 것입니다.

맵(map)에서 키는 요소를 구성하고 특정 요소를 빠르게 검색하는 방법을 제공하는 데 사용됩니다. 키는 일반적으로 정수 또는 문자열이지만 동일한지 비교할 수 있는 모든 데이터 유형이 될 수 있습니다. 값은 모든 데이터 유형이 될 수 있습니다.

맵(map)의 구현은 프로그래밍 언어와 특정 사용 사례에 따라 달라질 수 있습니다. 예를 들어 C++에서 std::map 클래스는 효율적인 삽입, 삭제 및 검색 작업을 허용하는 균형 잡힌 트리로 구현됩니다.

맵(map)에서 제공하는 기본 작업은 다음과 같습니다.
삽입(Insertion) : 새 키-값 쌍을 맵에 추가합니다.
검색(Search) : 주어진 키에 해당하는 값을 찾습니다.
삭제(Delete) : 맵에서 키-값 쌍을 제거합니다.
반복(Iteration) : 맵의 모든 키-값 쌍을 반복합니다.

또한 일부 맵(map)는 다음과 같은 추가 작업을 제공할 수도 있습니다.
찾기(Find) : 키가 발견되면 키-값 쌍에 대한 반복자를 반환하고, 그렇지 않으면 맵의 끝에 반복자를 반환합니다.
모두 삭제(Clear) : 맵에서 모든 키-값 쌍을 제거합니다.
크기(Size) : 맵에서 키-값 쌍의 수를 반환합니다.

맵은 일반적으로 구성 설정 저장, 캐시 유지, 컴파일러에 기호 테이블 저장 등과 같은 많은 응용 프로그램에서 널리 사용됩니다. 맵은 키-값 쌍의 형태로 데이터를 저장하고 싶을 때 사용할 수 있는 효율적인 데이터 구조입니다. 키로 값을 조회해야 합니다.

 

 

---

 

 

2. unordered_map

unordered_map은 해시 테이블을 사용하여 키-값 쌍을 구현하는 맵(map)의 변형입니다. 정렬되지 않은 연관 배열, 정렬되지 않은 사전 또는 해시 맵이라고도 합니다. 맵(map)과 마찬가지로 unordered_map은 각 키가 고유한 키-값 쌍의 컬렉션을 저장합니다.

unordered_map에서 키는 요소를 구성하고 특정 요소를 빠르게 검색하는 방법을 제공하는 데 사용되지만 맵(map)과 달리 키는 특정 순서로 저장되지 않습니다. 대신 키가 해시되고 결과 해시 값은 해시 테이블에서 각 키-값 쌍을 저장할 위치를 결정하는 데 사용됩니다.

unordered_map에서 제공하는 기본 작업은 다음과 같습니다.
삽입(Insertion) : unordered_map에 새 키-값 쌍을 추가합니다.
검색(Search) : 주어진 키에 해당하는 값을 찾습니다.
삭제(Delete) : unordered_map에서 키-값 쌍을 제거합니다.
반복(Iteration) : unordered_map의 모든 키-값 쌍을 반복합니다.

 

또한 일부 unordered_maps는 다음과 같은 추가 작업을 제공할 수도 있습니다.
찾기(Find) : 키가 발견되면 키-값 쌍에 대한 이터레이터를 반환하고, 그렇지 않으면 unordered_map의 끝에 이터레이터를 반환합니다.
모두 삭제(Clear) : unordered_map에서 모든 키-값 쌍을 제거합니다.
크기(Size) : unordered_map에서 키-값 쌍의 수를 반환합니다.

Unordered_map은 검색 작업과 관련하여 맵(map)보다 빠르며 검색 및 삽입 작업에 대해 평균적으로 O(1)의 일정한 시간 복잡도를 가지므로 검색 및 삽입 작업이 반복 또는 삭제보다 더 빈번한 상황에서 유용할 수 있습니다. 그러나 키를 저장하는 임의의 특성으로 인해 캐시 위치가 좋지 않을 수 있습니다.

Unordered_map은 구성 설정 저장, 캐시 유지, 컴파일러에 심볼 테이블 저장 등과 같은 많은 응용 프로그램에서 널리 사용됩니다. 맵(map)과 마찬가지로 키-값 쌍의 형태로 데이터를 저장하고 싶을 때 사용할 수 있는 효율적인 데이터 구조입니다. 키로 값을 조회해야 합니다.

 

 

---

 

 

3. 맵(map)과 unordered_map의 차이

맵(map)과 unordered_map의 주요 차이점은 키-값 쌍을 구성하고 검색하는 방식입니다.

맵(map)은 특정 순서로 키-값 쌍을 저장하는 정렬된 데이터 구조입니다. 균형 트리(예: Red-Black 트리 또는 AVL 트리)를 사용하여 키-값 쌍을 구현합니다. 키는 정렬된 순서로 저장되어 대수 시간 복잡성으로 효율적인 검색, 삽입 및 삭제 작업을 수행할 수 있습니다. 요소는 사전순으로 또는 비교 함수를 기반으로 특정 순서로 저장됩니다.

반면에 unordered_map은 특정 순서 없이 키-값 쌍을 저장하는 정렬되지 않은 데이터 구조입니다. 키-값 쌍을 구현하기 위해 해시 테이블을 사용합니다. 키는 해시되고 결과 해시 값은 해시 테이블에서 각 키-값 쌍을 저장할 위치를 결정하는 데 사용됩니다. unordered_map은 요소의 순서를 보장하지 않지만 일정한 시간 복잡성으로 더 빠르고 효율적인 검색 및 삽입 방법을 제공합니다.

요약하면 맵(map)과 unordered_map의 주요 차이점은 다음과 같습니다.

1. 맵(map)은 정렬된 데이터 구조이고 unordered_map은 정렬되지 않은 데이터 구조입니다.
2. 맵(map)은 Red-Black 트리 또는 AVL 트리와 같은 균형 트리를 사용하여 키-값 쌍을 구현하는 반면 unordered_map은 해시 테이블을 사용합니다.
3. 맵(map)은 검색, 삽입 및 삭제 작업에 대수적 시간 복잡도를 갖는 반면 unordered_map은 일정한 시간 복잡도를 가집니다.
4. 맵(map)은 요소의 순서를 보장하지만 unordered_map은 요소의 순서를 보장하지 않습니다.

 

애플리케이션의 요구 사항 및 다양한 사례, 다양한 데이터 크기에 따라 데이터 구조를 사용할 시기가 달라집니다. 만약 요소의 순서가 중요하고 빈번한 검색 및 삽입 작업이 필요하지 않은 경우 맵(map)이 더 나은 선택입니다. 반면 요소의 순서가 중요하지 않고 빈번한 검색 및 삽입 작업이 필요한 경우 unordered_map이 더 나은 선택입니다.

 

 

---

 

 

출처 1.

https://blockdmask.tistory.com/87

[C++] map container 정리 및 사용법

 

출처 2.

https://doctorson0309.tistory.com/810

Map과 해시맵(HashMap)의 차이점은 무엇일까?

 

출처 3.

https://math-coding.tistory.com/31

[Data Structure] unordered_map 사용법

 

출처 4.

https://blog.naver.com/PostView.naver?blogId=do9562&logNo=221754890348 

[C++] STL unordered_map