맵(Map)

Map 자료구조 완전 가이드

1. Map의 정의

Map은 키(Key)와 값(Value)의 쌍을 저장하는 연관 컨테이너(Associative Container) 자료구조입니다. 각 키는 고유하며, 하나의 키에는 하나의 값만 대응됩니다. 이러한 특성으로 인해 Map은 사전(Dictionary) 또는 **연관 배열(Associative Array)**이라고도 불립니다.

핵심 특징

• 키의 유일성: 동일한 키가 두 번 이상 존재할 수 없음
• 키-값 매핑: 각 키는 정확히 하나의 값과 연결됨
• 동적 크기: 런타임에 크기가 변경 가능
• 효율적인 검색: 키를 통한 빠른 데이터 접근

2. Map의 ADT (Abstract Data Type)

Map의 추상 데이터 타입은 다음과 같은 연산들을 정의합니다:

기본 연산

삽입 연산 (Insert)

insert(key, value) → boolean

• 새로운 키-값 쌍을 Map에 추가
• 키가 이미 존재하면 실패하거나 값을 업데이트

검색 연산 (Search/Find)

find(key) → value | null

• 주어진 키에 대응하는 값을 반환
• 키가 존재하지 않으면 null 또는 예외 발생

삭제 연산 (Delete)

remove(key) → boolean

• 주어진 키와 그에 대응하는 값을 제거
• 성공 시 true, 키가 없으면 false 반환

업데이트 연산 (Update)

update(key, new_value) → boolean

• 기존 키의 값을 새로운 값으로 변경

부가 연산

크기 연산

size() → integer
empty() → boolean

순회 연산

keys() → iterator
values() → iterator
entries() → iterator

존재 확인

contains(key) → boolean

3. Map의 종류

3.1 Ordered Map (정렬된 맵)

키가 정렬된 순서로 유지되는 Map입니다.

구현 방식

• 이진 검색 트리(Binary Search Tree)
• 레드-블랙 트리(Red-Black Tree)
• AVL 트리

대표적인 구현체

• C++: std::map
• Java: TreeMap
• Python: collections.OrderedDict (삽입 순서 기준)

시간 복잡도

연산 시간 복잡도

연산	시간 복잡도
검색	O(log n)
삽입	O(log n)
삭제	O(log n)

3.2 Unordered Map (해시 맵)

키의 순서를 유지하지 않고 해시 테이블을 기반으로 구현된 Map입니다.

구현 방식

• 해시 테이블(Hash Table)
• 해시 함수를 사용하여 키를 인덱스로 변환
• 충돌 해결 기법 필요 (체이닝, 개방 주소법)

대표적인 구현체

• C++: std::unordered_map
• Java: HashMap
• Python: dict

시간 복잡도

연산 평균 최악

연산	평균	최악
검색	O(1)	O(n)
삽입	O(1)	O(n)
삭제	O(1)	O(n)

4. 특징 및 장단점 비교

4.1 Ordered Map

장점

• 정렬된 순회: 키가 정렬된 순서로 순회 가능
• 범위 검색: 특정 범위의 키들을 효율적으로 검색
• 예측 가능한 성능: 항상 O(log n)의 안정적인 성능
• 순서 보장: 키의 순서가 일관성 있게 유지됨

단점

• 상대적으로 느린 성능: 해시 맵보다 검색/삽입이 느림
• 메모리 오버헤드: 트리 구조 유지를 위한 추가 메모리 필요
• 복잡한 구현: 균형 트리 유지 로직이 복잡

적합한 사용 사례

• 키의 순서가 중요한 경우
• 범위 검색이 필요한 경우
• 정렬된 데이터 출력이 필요한 경우
• 최소/최대값 검색이 빈번한 경우

4.2 Unordered Map (해시 맵)

장점

• 빠른 성능: 평균 O(1)의 매우 빠른 검색/삽입/삭제
• 메모리 효율적: 트리 구조보다 메모리 사용량이 적음
• 단순한 사용법: 직관적이고 사용하기 쉬움

단점

• 순서 없음: 키의 순서가 예측 불가능하고 일관성 없음
• 최악의 경우 성능 저하: 해시 충돌이 많을 때 O(n) 성능
• 해시 함수 의존성: 좋은 해시 함수 설계가 중요
• 범위 검색 불가: 키의 범위 기반 검색이 비효율적

적합한 사용 사례

• 빠른 검색/삽입이 중요한 경우
• 키의 순서가 중요하지 않은 경우
• 캐시 구현
• 데이터베이스 인덱싱
• 중복 제거

5. 동작 과정 예시

5.1 Unordered Map (해시 맵) 프로세스

학생 정보를 저장하는 Map 예시

초기 상태

Map: {}
해시 테이블 크기: 8

1단계: 데이터 삽입

insert("Alice", 95)
- 해시 함수: hash("Alice") = 3
- 인덱스 3에 ("Alice", 95) 저장

insert("Bob", 87)  
- 해시 함수: hash("Bob") = 1
- 인덱스 1에 ("Bob", 87) 저장

insert("Charlie", 92)
- 해시 함수: hash("Charlie") = 3
- 충돌 발생! 체이닝으로 해결
- 인덱스 3: [("Alice", 95) → ("Charlie", 92)]

2단계: 데이터 검색

find("Bob")
- 해시 함수: hash("Bob") = 1
- 인덱스 1 확인 → "Bob" 발견
- 결과: 87 (시간복잡도: O(1))

find("Charlie")  
- 해시 함수: hash("Charlie") = 3
- 인덱스 3 확인 → 체인을 따라 검색
- 결과: 92 (시간복잡도: O(1) ~ O(n))

5.2 Ordered Map (트리 맵) 프로세스

동일한 학생 정보를 트리로 저장

1단계: 데이터 삽입 (이진 검색 트리)

insert("Bob", 87)
트리:      Bob(87)

insert("Alice", 95)  
트리:      Bob(87)
          /
    Alice(95)

insert("Charlie", 92)
트리:      Bob(87)
          /       \
    Alice(95)   Charlie(92)

2단계: 데이터 검색

find("Charlie")
1. 루트 "Bob"와 비교 → "Charlie" > "Bob" (오른쪽으로)
2. "Charlie" 노드 발견
결과: 92 (시간복잡도: O(log n))

find("Alice")
1. 루트 "Bob"와 비교 → "Alice" < "Bob" (왼쪽으로)  
2. "Alice" 노드 발견
결과: 95 (시간복잡도: O(log n))

3단계: 정렬된 순회

중위 순회 결과: Alice(95) → Bob(87) → Charlie(92)
키가 알파벳 순으로 정렬되어 출력됨

프로세스 비교 요약

동작 Unordered Map Ordered Map

동작	Unordered Map	Ordered Map
삽입 과정	해시 함수 계산 → 직접 저장	트리 구조 유지하며 적절한 위치에 삽입
검색 과정	해시 함수 계산 → 직접 접근	루트부터 비교하며 트리 탐색
충돌 처리	체이닝/개방주소법 사용	트리 균형 유지
순회 결과	순서 보장 없음	키 기준 정렬된 순서

6. 선택 기준

Ordered Map을 선택해야 하는 경우

• 키의 정렬된 순회가 필요
• 범위 검색 기능이 필요
• 최소/최대값 검색이 빈번
• 일관된 성능이 중요

Unordered Map을 선택해야 하는 경우

• 최고 성능이 중요
• 키의 순서가 중요하지 않음
• 단순한 키-값 매핑만 필요
• 메모리 사용량을 최소화하려는 경우

결론

Map은 프로그래밍에서 가장 중요한 자료구조 중 하나로, 키-값 쌍을 효율적으로 관리할 수 있게 해줍니다. Ordered Map과 Unordered Map은 각각 고유한 장단점을 가지고 있으므로, 사용하는 상황과 요구사항에 따라 적절한 구현을 선택하는 것이 중요합니다.

 

일반적으로 순서가 중요하지 않고 빠른 성능이 필요한 경우에는 Unordered Map을, 키의 순서나 범위 검색이 중요한 경우에는 Ordered Map을 사용하는 것이 좋습니다.