컬렉션 프레임워크 - Map, Stack, Queue

컬렉션 프레임워크 - Map 소개 1

Map 은 키-값의 쌍을 저장하는 자료 구조이다.

• 키는 맵 내에서 유일해야 한다. 그리고 키를 통해 값을 빠르게 검색할 수 있다.
• 키는 중복될 수 없지만, 값은 중복될 수 있다.
• Map은 순서를 유지하지 않는다.

 

자바는 HashMap, TreeMap, LinkedHashMap 등 다양한 Map 구현체를 제공한다. 이들은 Map 인터페이스의 메서드를 구현하며, 각기 다른 특성과 성능 특징을 가지고 있다.

 

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

메서드	설명
put(K key, V value)	지정된 키와 값을 맵에 저장한다. (같은 키가 있으면 값을 변경)
putAll(Map<? extends K, ? extends V> m)	지정된 맵의 모든 매핑을 현재 맵에 복사한다.
putIfAbsent(K key, V value)	지정된 키가 없는 경우에 키와 값을 맵에 저장한다.
get(Objet 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()	맵에 비어 있는지 여부를 반환한다.

 

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);
        }
    }
}

 

실행 결과

{studentB=80, studentA=90, studentD=100, studentC=80}
result = 100

KeySet 활용
key = studentB, value= 80
key = studentA, value= 90
key = studentD, value= 100
key = studentC, value= 80

entrySet 활용
key= studentB, value= 80
key= studentA, value= 90
key= studentD, value= 100
key= studentC, value= 80

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

 

키와 값 목록 조회

Entry Key-Value Pair

Map은 키와 값을 보관하는 자료 구조이다. 따라서 키와 값을 하나로 묶을 수 있는 방법이 필요하다. 이때 Entry를 사용하낟.

Entry는 키 0 값의 쌍으로 이루어진 간단한 객체이다. Entry는 Map 내부에서 키와 값을 함께 묶어서 저장할 때 사용한다

쉽게 이야기해서 우리가 Map에 키와 값으로 데이터를 저장하면 Map은 내부에서 키와 값을 하나로 묶는 Entry 객체를 만들어서 보관한다. 참고로 하나의 Map에 여러 Entry가 저장될 수 있다.

참고로 Entry는 Map 내부에 있는 인터페이스이다. 우리는 구현체보다는 이 인터페이스를 사용하면 된다.

 

---

컬렉션 프레임워크 - Map 소개 2

package collection.map;

import java.util.HashMap;

public class MapMain3 {

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

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

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

        // 학생이 없는 경우에만 추가2
        studentMap.putIfAbsent("studentA", 100);
        studentMap.putIfAbsent("studentB", 100);
        System.out.println(studentMap);

    }
}

 

---

컬렉션 프레임워크 - Map 구현체

자바의 Map 인터페이스는 키-값 쌍을 저장하는 자료 구조이다. Map은 인터페이스이기 때문에, 직접 인스턴스를 생성하 ㄹ수는 없고, 대신 Map 인터페이스를 구현한 여러 클래스를 통해 사용할 수 있다. 대표적으로 HashMap, TreeMap, LinkedHashMap 이 있다.

 

Map vs Set

Set에 Value가 있냐 없냐 차이. 

 

1. HashMap:

• 구조: HashMap은 해시를 사용해서 요소를 저장한다. 키(Key) 같은 해시 함수를 통해 해시 코드로 반환되고, 이 해시 코드는 데이터를 저장하고 검색하는 데 사용된다.
• 특징: 삽입, 삭제, 검색 작업은 해시 자료 구조를 사용하므로 일반적으로 상수 시간(O(1))의 복잡도를 가진다.
• 순서:순서를 보장하지 않는다.

 

2. LinkedHashMap:

• 구조: LinkedHashMap 은 HashMap과 유사하지만, 연결 리스트를 사용하여 삽입 순서 또는 최근 접근 순서에 따라 요소를 유지한다.
• 특징: 입력 순서에 따라 순회가 가능하다. HashMap과 같지만 입력 순서를 링크로 유지해야 하므로 조금 더 무겁다.
• 성능: HashMap과 유사하게 대부분의 작업은 O(1)의 시간 복잡도를 가진다.
• 순서: 입력 순서를 보장한다.

 

3. TreeMap:

• 구조: 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);

        Iterator<String> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            String key = iterator.next();
            System.out.print(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: 입력한 순서를 보장하지 않는다.
• LinkedHashMap: 키를 기준으로 입력한 순서를 보장한다.
• TreeMap: 키 자체의 데이터 값을 기준으로 정렬한다.

 

자바 HashMap 작동 원리

자바의 HashMap은 HashSet과 작동 원리가 같다.

Set과 비교하면 다음과 같은 차이가 있다.

Key를 사용해서 해시 코드를 생성한다.

Key 뿐만 아니라 값(value)을 추가로 저장해야 하기 때문에 Entry를 사용해서 Key, Value를 하나로 묶어서 저장한다.

 

이렇게 해시를 사용해서 키와 값을 저장하는 자료 구조를 일반적으로 해시 테이블이라 한다.

앞서 학습한 HashSet은 해시 테이블의 주요 원리를 사용하지만, 키-값 저장 방식 대신 키만 저장하는 특수한 형태의 해시 테이블로 이해하면 된다.

 

주의!

Nap의 Key로 사용되는 객체는 hashCode(), equals()를 반드시 구현해야 한다.

 

정리

실무에서는 Map이 필요한 경우 HashMap을 많이 사용한다. 그리고 순서 유지, 정렬의 필요에 따라서 LinkedHashMap, TreeMap을 선택하면 된다.

---

스택 자료 구조

후입 선출(LIFO, Last In First Out)

 

전통적으로 스택에 값을 넣는 것을 push라 하고, 스택에서 값을 꺼내는 것을 pop이라 한다.

package collection.deque;


import java.util.Stack;

//Stack은 사용하면 안됨 -> Deque를 대신 사용
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.peek() = " + 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.peek() = 3
stack.pop() = 3
stack.pop() = 2
stack.pop() = 1
[]

 

 

주의! - Stack 클래스는 사용하지 말자

자바의 Stack 클래스는 내부에서 Vector라는 자료 구조를 사용한다. 이 자료 구조는 자바 1.0에 개발되었는데, 지금은 사용되지 않고 하위 호환을 위해 존재한다. 지금은 더 빠른 좋은 자료 구조가 많다. 따라서 Vector를 사용하는 Stack도 사용하지 않는 것을 권장한다. 대신에 Deque를 사용한다.

 

---

큐 자료 구조

선입 선출(FIFO, First In First Out)

 

전통적으로 큐에 값을 넣는 것을 offer라 하고, 큐에서 값을 꺼내는 것을 poll이라 한다.

 

 

Queue 인터페이스는 List, Set과 같이 Collection의 자식이다.

Queue의 대표적인 구현체는 ArrayDeque, LinkedList가 있다.

 

참고로 LinkedList는 Deque와 List 인터페이스를 모두 구현한다.

 

package collection.deque;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class QueueMain {

    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
//        Queue<Integer> queue = new 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 자료 구조

"Deque"는 "Double Ended Queue"의 약자로, 이 이름에서 알 수 있듯이, Deque는 양쪽 끝에서 요소를 추가하거나 제거할 수 있다. Deque는 일반적은 큐(Queue)와 스택(Stack)의 기능을 모두 포함하고 있어, 매우 유연한 자료 구조이다.

데크, 덱 등으로 불린다.

• offerFirst(): 앞에 추가한다
• offerLast(): 뒤에 추가한다.
• pollFirst(): 앞에서 꺼낸다.
• pollLast(): 뒤에서 꺼낸다.

Deque의 대표적인 구현체는 ArrayDeque, LinkedList가 있다.

 

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 구현체와 성능 테스트

• Deque의 대표적인 구현체는 ArrayDeque, LinkedList가 있다. 이 둘 중에 ArrayDeque가 모든 면에서 더 빠르다.
• 둘의 차이는 ArrayList vs LinkedList의 차이와 비슷한데, 작동 원리가 하나는 배열을 하나는 동적노드 링크를 사용하기 때문이다.
• 이론적으로 LinkedList가 삽입 삭제가 자주 발생할 때 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPUU 캐시 최적화 등을 고려했을 때 배열을 사용하는 ArrayDeque가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

 

---

Deque와 Stack, Queue

Deque는 양쪽으로 데이터를 입력하고 출력할 수 있으므로, 스택과 큐의 역할 모두 수행할 수 있다.

 

---

 

 

출처 - 김영한의 실전 자바 중급 2편