[컬렉션 프레임워크] Map, Stack, Queue, Deque

JAVA/제네릭(Generic), 컬렉션(Collection Framework)

[컬렉션 프레임워크] Map, Stack, Queue, Deque

jiyoon0000 2025. 4. 14. 05:07

Map

* Map이란?

Key-Value 쌍(key-value pair)으로 데이터를 저장하는 자료구조로, 각 key는 고유해야 하며, 해당 key에 대응되는 value를 저장한다

* Map 특징

중복
- Key : 중복 X
- Value : 중복 O
순서
- HashMap : 순서 보장 X
- LinkedHashMap : 입력 순서 유지
- TreeMap : Key 기준 정렬
검색 성능
- HashMap 기준 : 평균 O(1)
접근 방식
- Key를 통해 Value에 직접 접근

* Map 인터페이스의 주요 메서드

메서드	설명
put(K key, V value)	지정된 키와 값을 맵에 저장한다. (같은 키가 있으면 값을 변경)
putAll(Map<? extends K,? extends V> m)	지정된 맵의 모든 매핑을 현재 맵에 복사한다
putIfAbsent(K key, V value)	지정된 키가 없는 경우에 키와 값을 맵에 저장한다
get(Object key)	지정된 키에 연결된 값을 반환한다
getOrDefault(Object key, V defaultValue)	지정된 키에 연결된 값을 반환한다 키가 없는 경우`defaultValue`로 지정한 값을 대신 반환한다
remove(Object key)	지정된 키와 그에 연결된 값을 맵에서 제거한다
clear()	맵에서 모든 키와 값을 제거한다
containsKey(Object key)	맵이 지정된 키를 포함하고 있는지 여부를 반환한다
containsValue(Object value)	맵이 하나 이상의 키에 지정된 값을 연결하고 있는지 여부를 반환한다
keySet()	맵의 키들을 `Set` 형태로 반환한다
values()	맵의 값들을 `Collection` 형태로 반환한다
entrySet()	맵의 키-값 쌍을 `Set<Map.Entry<K,V>>` 형태로 반환한다
size()	맵에 있는 키-값 쌍의 개수를 반환한다
isEmpty()	맵이 비어 있는지 여부를 반환한다

* HashMap 예시 코드

package collection.map;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapMain1 {

    public static void main(String[] args) {
        Map<String, Integer> studentMap = new HashMap<>();

        // 학생 성적 데이터 추가
        studentMap.put("studentA", 90);
        studentMap.put("studentB", 80);
        studentMap.put("studentC", 80);
        studentMap.put("studentD", 100);
        System.out.println(studentMap);

        // 특정 학생의 값 조회
        Integer result = studentMap.get("studentD");
        System.out.println("result = " + result);

        System.out.println("keySet 활용");
        Set<String> keySet = studentMap.keySet();
        for (String key : keySet) {
            Integer value = studentMap.get(key);
            System.out.println("key=" + key + ", value=" + value);
        }

        System.out.println("entrySet 활용");
        Set<Map.Entry<String, Integer>> entries = studentMap.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println("key= " + key + ", value = " + value);
        }

        System.out.println("values 활용");
        Collection<Integer> values = studentMap.values();
        for (Integer value : values) {
            System.out.println("value = " + value);
        }
    }
}

* Map 구조 - HashMap 기준

내부적으로는 배열 + 해시 함수 + 버킷(LinkedList 또는 Tree 구조) 사용
Key에 hashCode()를 적용하여 배열의 인덱스를 결정
해시 충돌 시 같은 인덱스에 체이닝 방식(리스트나 트리)으로 저장

+ Entry

Entry : Map의 Key-Value 쌍 하나를 표현하는 객체
자바에서는 Map.Entry<K, V> 인터페이스로 정의되어 있으며, Map 내부 구조를 반복하거나 조작할 때 사용
사용
- 보통 Map을 순회할 때 keySet()만 사용하면 Key만 접근 가능하지만, entrySet()을 사용하면 Key와 Value를 한 번에 가져올 수 있어 효율적
메서드(Map.Entry)
- getKey() : 해당 Entry의 Key 반환
- getValue() : 해당 Entry의 Value 반환
- setValue(V value) : 해당 Entry의 Value 변경

+ keySet() vs entrySet() 성능 차이

구분	keySet()	entrySet()
접근 방식	Key만 반환 map.get(key)로 Value 조회	Key와 Value 모두 한 번에 반환
내부 구조	Set<K>	Set<Map.Entry<K,V>>
Value 접근	별도 map.get(key) 호출 필요 -> O(1) 반복 발생	entry.getValue() 직접 사용 -> 성능 ↑
성능	상대적으로 느림 -> get() 반복 호출	상대적으로 빠름 (Key, Value 함께 순회)
사용	Key만 필요할 때	Key + Value 모두 필요할 때

- 데이터 양이 많을 수록 entrySet() 방식이 성능적으로 더 유리

Map 구현체

* Map vs Set

구분	Map	Set / List
저장 방식	Key-Value 쌍	단일 요소
인덱스	없음(Key로 접근)	Set : X / List : O
중복	Key 중복 X	Set : X / List : O

* Map 대표 구현체

1. HashMap

기본 Map 구현체, 가장 많이 사용됨
순서 보장 X
탐색 속도 빠름 -> 평균 O(1)
내부 구조 : 해시 테이블
null : key & value 허용(key 1개, Value 여러 개 가능)
사용 : 빠른 탐색이 필요하고 순서가 중요하지 않은 경우

2. LinkedHashMap

HashMap + 입력 순서 유지
탐색 성능 : HashMap과 유사 -> O(1)
내부 구조 : 해시 테이블 + 이중 연결 리스트
null : key & value 허용
사용 : 순서 유지 + 빠른 탐색이 필요한 경우

3. TreeMap

Key 기준 자동 정렬(기본 오름차순 또는 커스텀 Comparator)
탐색 성능 : O(log n) -> Tree 구조
내부 구조 : 레드-블랙 트리
null : key X(NPE), value O
사용 : 정렬된 출력, 범위 탐색이 필요한 경우(사전, 순위표)

4. 코드

package collection.map;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class JavaMapMain {

    public static void main(String[] args) {
        run(new HashMap<>());
        run(new LinkedHashMap<>());
        run(new TreeMap<>());
    }

    public static void run(Map<String, Integer> map) {
        System.out.println("map = " + map.getClass());
        map.put("C", 10);
        map.put("B", 20);
        map.put("A", 30);
        map.put("1", 40);
        map.put("2", 50);

        Set<String> keySet = map.keySet();
        Iterator<String> iterator = keySet.iterator();
        while (iterator.hasNext()) {
            String key = iterator.next();
            System.out.println(key + "=" + map.get(key) + " ");
        }
        System.out.println();
    }
}

<결과>

map = class java.util.HashMap
A=30
1=40
B=20
2=50
C=10

map = class java.util.LinkedHashMap
C=10
B=20
A=30
1=40
2=50

map = class java.util.TreeMap
1=40
2=50
A=30
B=20
C=10

* 자바의 HashMap 작동 원리 -> HashSet과 작동 원리가 같음

1. 기본 구조

내부적으로는 배열 + 해시 + 버킷 구조 사용
Map.Entry 배열 (Node<K,V>[ ] table)을 기반으로 동작
하나의 인덱스(bucket)에 여러 값이 들어올 수 있음 → 체이닝 구조

2. 저장 과정(put(K key, V value))

Key의 hashCode() 호출 → 객체의 고유 해시값을 생성
해시값을 나머지 연산 or 비트 연산으로 index 결정 → 배열에서 사용할 인덱스 선택
버킷에 데이터 저장
- 비어 있으면 바로 저장
- 이미 있다면 → equals()로 중복 확인
  - 중복이면 Value만 덮어씀
  - 중복이 아니면 LinkedList 또는 TreeNode로 연결

3. 검색 과정(get(Object key))

hashCode()로 인덱스 찾음
해당 버킷의 연결 리스트 또는 트리에서 equals()로 key를 비교하며 찾음

* Map을 언제 사용하는가?

키를 기반으로 빠르게 값을 찾고 싶을 때
중복되지 않는 고유 식별자(ID, 코드 등)를 기준으로 값을 저장할 때
데이터를 짝지어서 저장할 때(유저명 + 정보, 상품ID + 객체)

Stack
스택

* 스택이란?

후입선출(LIFO, Last In First Out) 자료구조

가장 나중에 넣은 데이터가 가장 먼저 나오는 구조의 자료구조

* 주요 연산

연산	설명
push()	데이터를 스택에 추가 -> O(1)
pop()	스택에서 가장 위에 있는 데이터를 꺼내고 제거 -> O(1)
peek()	스택의 맨 위 데이터를 꺼내기만 하고 제거하지 않음 -> 단순 조회, O(1)
isEmpty()	스택이 비었는지 확인
size()	스택의 요소 개수 반환

* 대표적 사용 예

웹 브라우저 뒤로 가기
재귀 함수 호출 스택
DFS(깊이 우선 탐색)
문자열 뒤집기

* 자바에서의 Stack

내부적으로 Vector를 상속 -> 동기화 처리로 성능 저하
실무에서 비추천
Deque로 스택을 구현하는 것을 권장
- ArrayDeque 사용
  - 성능이 뛰어나고 비동기 환경에서 안전
  - null을 저장할 수 없어 안정성 확보
  - 내부적으로 배열 기반의 원형 큐 구조

Queue
큐

* Queue란?

선입선출(FIFO, First In First Out) 자료구조

먼저 들어온 데이터가 먼저 나가는 구조

* 주요 연산

연산	설명
offer()	데이터를 큐에 추가 -> O(1)
poll()	큐의 맨 앞 데이터를 꺼내고 제거 -> O(1)
peek()	큐의 맨 앞 데이터를 꺼내기만 하고 제거하지 않음 -> 단순 조회, O(1)
isEmpty()	큐가 비었는지 확인
size()	큐의 요소 개수 반환

* 대표적인 사용 예

프린터 작업 대기열
네트워크 요청 처리
시뮬레이션(은행 창구, CPU 스케줄링)
BFS(너비 우선 탐색)

* 자바에서 Queue 구현

Queue는 인터페이스
주요 구현체
- LinkedList : 가장 전통적인 큐 구현체
- ArrayDeque : 배열 기반 원형 큐 -> 빠르고 효율적
- PriorityQueue : 우선순위 큐(작거나 큰 값 우선)

Deque
덱, Double Ended Queue

* Deque란?

양쪽 끝에서 삽입과 삭제가 모두 가능한 큐

즉, Queue + Stack의 성격을 모두 가진 자료구조

* Deque 특징

양방향 처리 : 앞(front)와 뒤(rear) 양쪽에서 삽입/삭제 가능
유연한 구조 : 큐, 스택의 성격을 모두 가짐
효율적 구현 : ArrayDeque로 구현 시 모든 연산이 O(1)

* 주요 연산

연산	설명
addFirst(e) / addLast(e)	앞 또는 뒤에 요소 추가
removeFirst() / removeLast()	앞 또는 뒤에서 요소 제거
peekFirst() / peekLast()	앞 또는 뒤 요소 조회
offerFirst(e) / offerLast(e)	요소 추가(예외 대신 false 반환)

+ add() vs offer()

항목	add(E e)	offer(E e)
반환값	성공 시 true, 실패 시 예외(Exception) 발생	성공 시 true, 실패 시 false
예외 처리	큐의 용량이 가득 찼을 경우 -> IllegalStateException 발생	큐의 용량이 가득 찼을 경우 -> false 반환
안정성	예외가 발생할 수 있음	예외 없이 안전하게 실패를 처리
용도	크기 제한 없는 큐에서 사용해도 무방	크기 제한 큐나 안정성 고려 시 사용

package collection.deque;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class DequeMain {

    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
//        Deque<Integer> deque = new LinkedList<>();

        // 데이터 추가
        deque.offerFirst(1);
        System.out.println(deque);

        deque.offerFirst(2);
        System.out.println(deque);

        deque.offerLast(3);
        System.out.println(deque);

        deque.offerLast(4);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(꺼내지 않고 단순 조회만)
        System.out.println("deque.peekFirst() = " + deque.peekFirst());
        System.out.println("deque.peekLast() = " + deque.peekLast());

        // 데이터 꺼내기
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println(deque);
    }
}

<실행 결과>

[1]
[2, 1]
[2, 1, 3]
[2, 1, 3, 4]
deque.peekFirst() = 2
deque.peekLast() = 4
deque.pollFirst() = 2
deque.pollFirst() = 1
deque.pollLast() = 4
deque.pollLast() = 3
[]

* Deque는 Stack + Queue의 기능을 모두 지원

<Stack처럼 사용 LIFO>

Deque<String> stack = new ArrayDeque<>();

stack.push("a"); 
stack.push("b");
System.out.println(stack.pop());

push() -> addFirst()
pop() -> removeFirst()
peek() -> peekFirst()

<Queue처럼 사용 FIFO>

Deque<String> queue = new ArrayDeque<>();

queue.offer("a");       
queue.offer("b");
System.out.println(queue.poll());

offer() -> addLast()
poll() -> removeFirst()

ArrayDeque는 성능이 뛰어나 Stack 대신 사용을 권장

총 정리

Map
- Key-Value 쌍으로 데이터를 저장
- Key는 중복 불가, Value는 중복 가능
- get(key), put(key, value)로 빠른 조회/삽입 가능
- 대표 구현체
  - HashMap : 순서 없음, 빠른 탐색(O(1))
  - LinkedHashMap : 입력 순서 유지 + HashMap의 성능 유지
  - TreeMap : key 기준 정렬, 내부적으로 레드-블랙 트리 사용
Stack(LIFO)
- 후입선출(Last In First Out)
- 마지막에 넣은 데이터가 먼저 나감
- 주요 연산 : push, pop, peek
Queue(FIFO)
- 선입선출(First In First Out)
- 먼저 들어온 데이터가 먼저 나감
- 주요 연산 : offer, poll, peek
Deque(Double-Ended Queue)
- 양쪽에서 삽입/삭제 모두 가능
- Stack + Queue의 연산을 모두 지원
- addFirst, addLast, removeFirst, removeLast

<참고> - 김영한의 실전 자바 중급2편 강의 섹션 10. 컬렉션 프레임워크 Map, Stack, Queue