맵(Map): 키-값 쌍을 저장하는 자료구조

1. 맵이란?

맵(Map)은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조다. 각 키는 고유하며, 이를 통해 해당 값에 빠르게 접근할 수 있다. 자바에서는 HashMap, TreeMap, LinkedHashMap 등 다양한 구현체가 존재하며, 대부분 O(1) 또는 O(log n)의 빠른 조회 성능을 제공한다.

2. 맵의 특징

• 키는 중복 불가, 값은 중복 가능
• 키를 통해 값을 빠르게 조회 가능
• 키의 해시 함수를 기반으로 내부적으로 데이터 저장

3. 맵의 구현 방식

3.1 HashMap (해시 기반)

• 가장 일반적인 Map 구현체
• 빠른 접근: O(1) 평균
• 키의 순서는 보장되지 않음

3.2 TreeMap (이진 탐색 트리 기반)

• 키를 오름차순으로 정렬
• 접근 시간: O(log n)
• 범위 기반 조회에 적합

3.3 LinkedHashMap

• 삽입 순서 유지
• 해시 기반 + 순서 정보 유지

4. 맵의 주요 연산 (Java 예시)

import java.util.HashMap;

public class MapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        map.put("apple", 3);
        map.put("banana", 5);
        map.put("apple", 10); // 기존 키의 값 갱신

        System.out.println(map.get("apple"));  // 10
        System.out.println(map.containsKey("banana"));  // true

        map.remove("banana");
        System.out.println(map);  // {apple=10}
    }
}

5. 맵의 시간 복잡도

연산	HashMap (평균)	TreeMap
삽입	O(1)	O(log n)
삭제	O(1)	O(log n)
검색	O(1)	O(log n)

• HashMap은 충돌이 많을 경우 최악의 경우 O(n)까지 갈 수 있음

6. 맵의 활용 사례

• 딕셔너리 구조 구현
• 빈도수 세기 (문자, 단어, 로그 등)
• 인덱스 매핑
• 캐시 시스템 (LRU, LFU 등)
• 구성 정보 저장 (환경 설정 등)

7. 맵 vs 해시 vs 집합

항목	맵(Map)	해시(Hash) 자료구조	집합(Set)
구조	키-값 쌍	키만 저장	값만 저장
키 중복	불가	불가	불가
값 중복	가능	-	불가
주요 기능	키 기반 조회/저장	빠른 검색	중복 제거/포함 여부

8. 결론

맵(Map)은 키를 통해 값을 빠르게 조회하고 관리할 수 있는 자료구조로, 대부분의 프로그램에서 필수적으로 사용된다. 해시 기반, 트리 기반, 순서 기반 등의 다양한 구현체를 활용하여 상황에 맞는 성능과 기능을 갖춘 자료구조를 선택하는 것이 중요하다.