Map, Stack, Queue

박병욱·2025년 7월 23일

Java

목록 보기

30/38

👀 Map이란?

Map 자료 구조는 키(Key)-값(Value)의 쌍(pair)으로 이루어진 데이터의 집합이다. 파이썬의 딕셔너리와 유사하다. 키값은 중복되서는 안 되고 Map 내에서 유일해야 하며, 그 키를 통해 값을 빠르게 검색할 수 있다. 값은 중복될 수 있다. 추가로, Map 자료 구조는 순서를 유지하지 않는다.

자바는 Map 인터페이스를 구현해서 HashMap, LinkedHashMap, TreeMap 등 다양한 구현체를 제공할 수 있다. Map 인터페이스는 Collection 인터페이스와는 아무 관련이 없다.

<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<>();  // HashMap 사용

        // 학생 성적 데이터 추가
        studentMap.put("학생1", 90);
        studentMap.put("학생2", 80);
        studentMap.put("학생3", 80);
        studentMap.put("학생4", 100);

        System.out.println(studentMap);

        // 특정 학생의 점수 조회
        Integer result = studentMap.get("학생3");
        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>> entrySet = studentMap.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println("key=" + key + ", value=" + value);
        }

        System.out.println("=== values 활용 ===");
        Collection<Integer> values = studentMap.values();  // 중복이 될 수도 있기 때문에 Collection으로 반환
        for (Integer value : values) {
            System.out.println("value = " + value);
        }
    }
}

/*
{학생1=90, 학생2=80, 학생3=80, 학생4=100}
result = 80

=== keySet 활용 ===
key=학생1, value=90
key=학생2, value=80
key=학생3, value=80
key=학생4, value=100

=== entrySet 활용 ===
key=학생1, value=90
key=학생2, value=80
key=학생3, value=80
key=학생4, value=100

=== values 활용 ===
value = 90
value = 80
value = 80
value = 100
*/

Map은 키-값의 쌍을 보관하는 자료 구조이기 때문에 둘을 하나로 묶을 수 있는 방법이 필요하다. 이때 바로 Entry를 사용한다. 쉽게 말해, Map으로 키와 값으로 데이터를 저장하게 되면 Map의 내부에서는 그걸 위의 그림처럼 Entry로 만들어서 보관한다는 말이다.

Collection<Integer> values = studentMap.values(): 앞서 말했다시피 값은 중복이 가능하다. 따라서 Set 타입으로는 받을 수는 없다. 그리고 입력 순서를 보장하지 않기 때문에 List로 받기도 애매한 부분이 있다. 따라서 단순한 값의 모든이라는 상위 인터페이스인 Collection으로 반환한다.

만약 Map에 같은 키로 데이터를 여러 개 저장하면 어떻게 될까? 아래 코드를 보자.

package collection.map;

import java.util.HashMap;
import java.util.Map;

public class MapMain2 {
    public static void main(String[] args) {

        Map<String, Integer> studentMap = new HashMap<>();

        // 학생 성적 데이터 추가
        studentMap.put("학생1", 90);
        System.out.println(studentMap);

        studentMap.put("학생1", 100);
        System.out.println(studentMap);

        // 특정 키값이 있냐?
        boolean containsKey = studentMap.containsKey("학생1");
        System.out.println("containsKey = " + containsKey);

        // 특정 학생 성적 삭제
        studentMap.remove("학생1");
        System.out.println(studentMap);
    }
}

/*
{학생1=90}
{학생1=100}
containsKey = true
{}
*/

보다시피 기존에 저장되어 있는 값이 새로운 값으로 대체되는 것을 볼 수 있다. 학생1이 없는 경우에만 데이터를 추가하도록 리팩토링 하자.

package collection.map;

import java.util.HashMap;
import java.util.Map;

public class MapMain3 {
    public static void main(String[] args) {

        Map<String, Integer> studentMap = new HashMap<>();

        // 학생 성적 데이터 추가
        studentMap.put("학생1", 50);
        System.out.println(studentMap);

        // 학생이 없는 경우에만 추가
        if (!studentMap.containsKey("학생1")) {
            studentMap.put("학생1", 100);
        }

        System.out.println(studentMap);

        // 학생이 없는 경우에만 추가
        studentMap.putIfAbsent("학생1", 100);  // 학생1이라는 key가 없으면 100을 추가
        studentMap.putIfAbsent("학생2", 100);  // 학생2이라는 key가 없으면 100을 추가
        System.out.println(studentMap);
    }
}

/*
{학생1=50}
{학생1=50}
{학생1=50, 학생2=100}
*/

위처럼 putIfAbsent() 메서드를 사용하면 된다. 말 그래도 없으면 집어 넣으라는 뜻이다. 키가 없는 경우에만 데이터를 추가하고 싶을 때 편리하게 사용할 수 있다.

아까 말했다시피 Map 인터페이스는 “인터페이스” 이기 때문에, 직접 인스턴스를 생성할 수는 없고, Map 인터페이스를 구현한 여러 클래스를 통해 사용할 수 있다. 대표적인 것이 바로 HashMap, LinkedHashMap, TreeMap이 있는 것이다.

🧐 Entry를 사용한다고 했는데 왜 Node를 사용하고 있지?

보다시피 Entry가 아닌, Node 클래스를 사용하고 있는 것을 볼 수 있다. 결론부터 말하자면, 여기서 Node는 HashMap 내부에서 데이터를 저장하는 실제 클래스이고, Entry는 Map 인터페이스에서 제공하는 인터페이스다. 따라서 Entry는 HashMap에서 뿐만 아니라 다른 클래스, 예를 들어 TreeMap에서도 구현되어 사용되고 있다.

그래서 사실상 HashMap에서의 table[] 배열은 사실상 Node<K,V> 타입인 것이고,

transient Node<K,V>[] table;

Map.Entry<K,V>를 구현하므로 entrySet()을 통해 외부에서도 Node를 Entry로 사용할 수 있다.

<추가 예시>

Map<String, String> map = new HashMap<>();
map.put("A", "Apple");

// entrySet()으로 얻은 Entry도 사실은 Node
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

위에서 entry의 타입은 Map.Entry지만, 내부적으로는 Node<String, String>의 인스턴스가 리턴되는 것이다.

정리하자면, Node 클래스는 Map.Entry<K, V>를 구현한 "내부(static) 클래스" 이며, 각 키-값 쌍을 저장하는 연결 리스트의 노드로 사용되는 것이다. 즉, 둘은 같은 역할을 하지만 용도와 위치가 다르다고 보면 된다.

🤔 참고 사항

Map의 “Key” 는 Set과 같은 구조다. Map에서는 키가 핵심이다. 값은 단순히 키 옆에 따라다니는 친구인 것이다. 생각해보면, Set 자료 구조에 “Value” 만 추가해주면 Map이 되는 거다. 이런 이유로, 전에 학습했던 HashSet, LinkedHashSet, TreeSet은 HashMap, LinkedHashMap, TreeMap과 거의 같다고 생각하면 된다. 실제로도 HashSet의 구현 코드를 살펴보면 HashMap의 구현을 끌어와 사용한다. 단지 Map에서 Value만 비워두면 Set으로 사용할 수 있다.

결국 Set을 공부하는 것은 Map을 공부하는 것과 같다. 단지 옆에 “Value” 가 붙어 있냐 없냐만 차이인 것이다.

🌱 Map 구현체들의 특징

HashMap: 해시를 사용해서 순서를 보장하지 않은 채 데이터를 저장한다. 키값은 해시 함수를 통해 해시 코드로 반환되고, 이 해시 코드는 데이터를 저장하고 검색하는데 사용된다. 삽입/삭제/검색 작업은 해시 자료 구조를 사용하므로 일반적으로는 O(1)의 복잡도를 가진다.
LinkedHashMap: HashMap과 거의 유사하지만, 연결 리스트를 사용해서 삽입 순서, 최근 접근 순서에 따라 요소를 유지한다. 입력 순서에 따라 순회가 가능하지만 입력 순서를 링크로 유지해야 하기 때문에 HashMap보다 조금 더 무겁다. 대부분의 작업에 O(1)의 시간 복잡도를 가지며, 입력 순서를 보장한다.
TreeMap: 레드-블랙 트리를 기반으로 한 구현으로, 모든 키는 자연 순서, 혹은 생성자에 제공된 Comparator에 의해 정렬된다. get, put, remove와 같은 주요 작업들은 O(log n)의 시간 복잡도를 가진다. 키는 정렬된 순서로 저장된다.

바로 코드로 구현하면서 확인해보자.

package collection.map;

import java.util.*;

public class JavaMapMain {
    public static void main(String[] args) {

        run(new HashMap<>());
        run(new LinkedHashMap<>());
        run(new TreeMap<>());
    }

    private 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의 작동 원리

앞서 말했듯이 HashMap은 HashSet과 아주 유사하다고 했다. 단지 키를 사용해서 해시 코드를 생성하고, 값도 추가로 저장해줘야 하기 때문에 Entry를 사용해서 키-값 쌍들을 하나로 묶어서 관리하는 점만 차이가 있다. 아래 그림을 보자.

이런 식으로 해시를 사용해서 키-값을 저장하는 자료 구조를 해시 테이블이라고 한다. 해시 충돌이 일어났을 때, 5번 인덱스를 보면 알 수 있듯이 충돌이 일어난 2개의 Entry가 삽입되는 구조다. 여기서 전에 살펴봤던 Node<K, V>의 next 필드를 이용한 Separate Chaining 방식으로 HashMap의 해시 충돌을 처리한다. 위에서 "A", 80(1번 노드)과 "K", 80(2번 노드) 노드가 충돌이 일어났는데, 먼저 1번 노드가 저장되고, 2번 노드가 저장된 다음, 1번 노드의 next 필드로 2번 노드를 연결하는 것이다. Java 8부터는 충돌이 너무 많아져서 연결 리스트 길이가 일정 이상이 되면, 성능 향상을 위해 Node 대신 TreeNode(Red-Black Tree 구조)로 바꾸기도 한다.

추가적으로, 여기서 아주 중요하게 생각해야 할 부분은, 어느 버킷에 저장되어야 할지, 그 버킷 안에서 동일한 키가 존재하는지 확인하기 위해, “Key” 로 사용되는 객체는 반드시 hashCode()와 equals() 메서드를 오버라이딩 해줘야 한다는 점이다.

🧱 스택(Stack) 자료 구조

가장 마지막에 넣은 값이 가장 먼저 나오는 “후입 선출(LIFO)” 방식으로 작동하는 스택(Stack)이다. 이제 지겨울 지경이다. 스택에 값을 넣을 때는 push(), 값을 꺼낼 때는 pop() 메서드를 이용하면 된다. 그냥 바로 코드로 구현해보자.

package collection.deque;

import java.util.Stack;

public class StackMain {
    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack);

        // 다음 꺼낼 요소를 확인(꺼내지는 않음)
        System.out.println("stack.peak(): " + stack.peek());

        // 스택 요소를 뽑고 반환
        System.out.println("stack.pop(): " + stack.pop());
        System.out.println("stack.pop(): " + stack.pop());
        System.out.println("stack.pop(): " + stack.pop());
        System.out.println(stack);

    }
}

/*
[1, 2, 3]
stack.peak(): 3
stack.pop(): 3
stack.pop(): 2
stack.pop(): 1
[]
*/

근데 주의해야 할 점이 있다. 위의 코드에서는 대략적인 흐름만 보기 위해 Stack 클래스를 사용했는데, 이는 바람직하지 않다. 왜냐하면, Stack 클래스는 내부에서 Vector라는 자료 구조를 사용하고 있다. Vector는 자바 1.0에 개발되었는데, 지금은 사용되지 않고 하위 호환을 위해서만 존재한다. 이후에 학습할 "Deque를 사용하는 것이 권장" 된다.

🚃 큐(Queue) 자료 구조

먼저 넣은 값이 먼저 나오는 큐(Queue) 자료 구조다. 얘도 이제 지겹다.

Queue 인터페이스는 List, Set과 같이 Collection의 자식이다. Queue의 대표적인 구현체로는 ArrayDeque와 LinkedList가 있다. 이 중 LinkedList는 Deque와 List 인터페이스를 모두 구현한다.

그럼 바로 코드로 구현해보자.

package collection.deque;

import java.util.ArrayDeque;
import java.util.Queue;

public class QueueMain {
    public static void main(String[] args) {

        Queue<Integer> queue = new ArrayDeque<>();  // (권장 방법) 하지만, LinkedList를 사용해도 무방

        // 데이터 추가
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue);

        // 다음 꺼낼 데이터를 확인(꺼내지는 않음)
        System.out.println("queue.peek(): " + queue.peek());

        // 데이터 꺼내기
        System.out.println("queue.poll(): " + queue.poll());
        System.out.println("queue.poll(): " + queue.poll());
        System.out.println("queue.poll(): " + queue.poll());
        System.out.println(queue);
    }
}

/*
[1, 2, 3]
queue.peek(): 1
queue.poll(): 1
queue.poll(): 2
queue.poll(): 3
[]
*/

↔ Deque 자료 구조

“Double Ended Queue” 의 약자로, 말 그대로 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료 구조다. 따라서 Queue와 Stack의 기능을 매우 유연하게 사용할 수 있다.

Deque의 구현체로는 앞서 말했다시피 ArrayDeque와 LinkedList가 대표적이다. 바로 코드로 살펴보자.

package collection.deque;

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

public class DequeMain {
    public static void main(String[] args) {

        Deque<Integer> deque = new ArrayDeque<>();
        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
[]
*/

ArrayDeque와 LinkedList 중에 ArrayDeque가 모든 면에서 더 빠르다. 배열 구조로 되어 있으서 단순하게 데이터를 넣고 뺄 수 있기 때문이다. 추가로 ArrayDeque는 특별한 “원형 큐” 를 사용하는데, 앞부분과 뒷부분 입력 모두 O(1)의 성능을 제공한다. 이론적으로 따지면, LinkedList가 삽입 삭제가 자주 발생할 때 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴이나 CPU 캐시 최적화 등을 고려할 때 배열을 사용하는 ArrayDeque가 더 나은 성능을 보여주는 경우가 많다. 이제 Deque의 ArrayDeque를 사용해서 Queue와 Stack을 구현해보자.

package collection.deque;

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

public class DequeQueueMain {
    public static void main(String[] args) {

        Deque<Integer> deque = new ArrayDeque<>();

        // 데이터 추가
        deque.offer(1);
        deque.offer(2);
        deque.offer(3);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(꺼내지는 않음)
        System.out.println("deque.peek() = " + deque.peek());

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

/*
[1, 2, 3]
deque.peek() = 1
deque.poll() = 1
deque.poll() = 2
deque.poll() = 3
[]
*/

package collection.deque;

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

public class DequeStackMain {
    public static void main(String[] args) {

        Deque<Integer> deque = new ArrayDeque<>();

        // 데이터 추가
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(꺼내지는 않음)
        System.out.println("deque.peek() = " + deque.peek());

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

/*
[3, 2, 1]
deque.peek() = 3
deque.pop() = 3
deque.pop() = 2
deque.pop() = 1
[]
*/