[Java] Java에서 Map (HashMap, LinkedHashMap, TreeMap), Stack, Queue란?

자바의 컬렉션 프레임워크는 개발자에게 효율적이고 강력한 자료 구조를 제공합니다.

그 중에서도 자주 사용되는 Map, Stack, Queue, Deque에 대해서 각 자료 구조의 특성과 구현체, 그리고 코드 예제를 포함하여 자세하게 살펴보겠습니다.

 

1. Map이란?

Map 인터페이스

Map은 키와 값의 쌍을 저장하는 자료 구조입니다.

키는 중복될 수 없으며, 이를 통해 데이터를 매우 빠르게 검색할 수 있습니다. 자바에서는 Map을 인터페이스로 제공하고 있습니다.

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, TreeMap, LinkedHashMap 등 다양한 Map 구현체를 제공합니다.

Map 인터페이스의 주요 구현체는 다음과 같습니다.

 

 

A. HashMap

HashMap은 다음과 같은 특징을 갖고 있습니다.

1. 내부적으로 해시 테이블을 사용하여 데이터를 저장

해시 테이블이란?

키 값을 해시 함수(hashCode)로 숫자로 바꾼 뒤, 그 숫자를 인덱스로 사용해 배열에 값을 저장한다는 뜻입니다.

"apple"의 hashCode가 12345678이라면,
12345678 % 배열 길이(예: 16) = 14
→ 14번 인덱스에 값을 저장을 한다는 뜻이죠.

 

이론적으로 key → hash → 배열 인덱스 계산 → 바로 접근
즉, 검색, 삽입, 삭제가 배열처럼 한 번에 이뤄지니 시간 복잡도는 O(1)입니다.
(실제로는 충돌이 생기면 linked list 또는 트리로 엮음)

Map<String, String> map = new HashMap<>();
map.put("apple", "사과"); // "apple"의 해시코드로 위치를 찾음
System.out.println(map.get("apple")); // 즉시 검색 O(1)

2. 삽입, 삭제, 검색 작업이 일반적으로 O(1)의 시간 복잡도를 갖는다.

3. 순서를 보장 하지 않음

예시

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Alice", 90);
hashMap.put("Bob", 80);
System.out.println(hashMap); // {Alice=90, Bob=80}
System.out.println(hashMap.get("Alice")); // 90

 

B. LinkedHashMap

1. 내부적으로 HashMap과 연결 리스트를 사용하여 삽입된 순서 유지

2. 입력된 순서대로 데이터를 순회 가능

예시

Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("Alice", 90);
linkedHashMap.put("Bob", 80);
System.out.println(linkedHashMap.keySet()); // [Alice, Bob]

 

C. TreeMap

1. 내부적으로 레드-블랙 트리를 사용하여 키의 자연 순서로 데이터를 정렬

2. 검색, 삽입, 삭제 작업이 O(log n) 시간 복잡도를 가짐

예시

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Charlie", 85);
treeMap.put("Alice", 90);
treeMap.put("Bob", 80);
System.out.println(treeMap.keySet()); // [Alice, Bob, Charlie]

 

 

D. 키 (key)와 값(value) 목록 조회

Map은 키와 값을 보관하는 자료 구조이다. 그러면 키, 값, 키-값을 조회하는 방법이 필요한데 자바에서는 각각 조회할 수 있는 메서드를 제공합니다.

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

 studentMap.put("studentA", 90);
 studentMap.put("studentB", 80);
 studentMap.put("studentC", 80);
 studentMap.put("studentD", 100);

 Set<String> strings = studentMap.keySet(); // key 모음
 Collection<Integer> values = studentMap.values(); // value 모음
 Set<Map.Entry<String, Integer>> entries = studentMap.entrySet(); // key-value 모음

 

1. keySet() 메서드는 왜 Set 인터페이스의 구현체를 리턴할까?

-> Map의 키(key)는 고유하므로 중복을 허용않는 Set 인터페이스의 구현체를 리턴한다.

 

2. values() 메서드는 왜 Collections 인터페이스의 구현체를 리턴할까?

-> Map의 값(value)는 고유하지 않고, 중복을 허용하고 입력 순서를 보장하지 않기 때문에  Collection으로 반환환다.

 

Set, Collection은 인터페이스인데, 저런 메서드가 내부에서 어떤 구현체를 리턴하는지 궁금하지 않나요??

 System.out.println(strings.getClass()); // class java.util.HashMap$KeySet
 System.out.println(values.getClass()); // class java.util.HashMap$Values
 System.out.println(entries.getClass()); // class java.util.HashMap$EntrySet

 

각각 HashMap의 내부 클래스인 KeySet, Values, EntrySet 클래스를 리턴하고 있었습니다.

HashMap에서의 keySet 클래스는 

 

 

 

 

 

 

 

 

 

 

 

 

 

AbstractSet을 상속 하고 있었고, AbstractSet은 Set을 구현한 추상클래스 였기 때문에 IDE가 자동으로 입력해준 참조 클래스는 Set 인터페이스이며, 구현체는 KeySet 클래스를 리턴하고 있었습니다.

 

또한 HashMap의 내부 클래스인 Values 클래스는

AbstarcCollection을 상속 하고 있었고 AbstarcCollection는 Collection 인터페이스를 구현한 추상 클래스 였기 때문에 Collection 인터페이스를 참조 클래스로 할 수 있었습니다.

 

마지막으로, HashMap의 내부 클래스인 EntrySet 클래스는 

AbstaractSet을 상속 하고 있었고 AbstaractSet 는 Set 인터페이스를 구현한 추상 클래스 였기 때문에 Set인터페이스를 참조 클래스로 할 수 있었습니다.

 

여기서 그러면 Map.Entry가 궁금해질 수도 있는데요. Entry 클래스란 키-값을 쌍으로 이루어진 간단한 객체라고 생각하면 됩니다.

Entroy는 Map 내부에서 키와 값을 함게 묶어서 저장할 때 사용합니다. 

 

Map을 사용할 때 equals()와 hashcode()의 중요성

Map이나 Set같은 Hash값을 쓰는 자료구조를 사용하고, 사용자 정의 객체를 Key로 사용할 때 꼭 eqauls()와 hashCode()를 재정의 해야합니다.

HashMap, HashSet등은 객체의 hashCode값으로 저장위치를 찾고 equals로 동등성을 검사하기 때문입니다.

public class Product {
    private String name;
    private int price;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Product)) return false;
        Product p = (Product) o;
        return price == p.price && Objects.equals(name, p.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, price);
    }
}

이렇게 구현하지 않는다면 똑같은 상품인데도 Map에 여러 번 저장된다거나 검색이 안되는 버그가 발생합니다.

 

 

2. Stack

스택(Stack)은 후입선출(LIFO, Last In First Out)의 원칙을 따르는 자료 구조입니다. 마지막에 입력한 데이터가 가장 먼저 출력됩니다.
자바에서는 성능 문제로 인해 Stack 클래스 대신 Deque의 구현체인 ArrayDeque를 권장합니다.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3
System.out.println(stack.peek()); // 2

 

 

 

3. Queue

큐(Queue)는 선입선출(FIFO, First In First Out)의 원칙을 따릅니다. 가장 먼저 입력된 데이터가 가장 먼저 처리됩니다.
자바의 Queue 인터페이스의 대표적인 구현체로는 ArrayDeque와 LinkedList가 있습니다. 성능 면에서는 일반적으로 ArrayDeque가 우월합니다.

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 1
System.out.println(queue.peek()); // 2

 

 

 

4. Deque

Deque(Double Ended Queue)는 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 매우 유연한 자료 구조로, 큐와 스택의 기능을 모두 포함합니다.

Deque를 Stack처럼 사용

Deque<Integer> dequeStack = new ArrayDeque<>();
dequeStack.push(1);
dequeStack.push(2);
System.out.println(dequeStack.pop()); // 2

 

Deque를 Queue처럼 사용

Deque<Integer> dequeQueue = new ArrayDeque<>();
dequeQueue.offer(1);
dequeQueue.offer(2);
System.out.println(dequeQueue.poll()); // 1