[Java/김영한] Map, Stack, Queue

https://inf.run/sDjcZ

김영한의 실전 자바 - 중급 2편| 김영한 - 인프런 강의

이 링크를 통해 구매하시면 제가 수익을 받을 수 있어요.

 

Map

Map 이란?

 

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

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

 

자바는 `HashMap`, `TreeMap`, `LinkedHashMap` 등 다양한 `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()`	맵이 비어 있는지 여부를 반환한다.

 

 

 

키 목록 조회

Set<String> keySet = studentMap.keySet()

`Map`의 키는 중복을 허용하지 않는다. 따라서 `Map`의 모든 키 목록을 조회하는 `keySet()`을 호출하면, 중복을 허용하지 않는 자료 구조인 `Set`을 반환한다.

 

 

 

키와 값 목록 조회

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

 

`Entry`는 `Map` 내부에 있는 인터페이스로 키-값 쌍으로 이루어진 간단한 객체이다. `Map` 내부에서 키와 값을 함께 묶어서 저장할 때 사용한다.

 

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

 

 

값 목록 조회

Collection<Integer> values = studentMap.values()

`Map`의 값 목록은 중복을 허용한다. 따라서 중복을 허용하지 않는 `Set`으로는 반환할 수 없다. 그리고 입력 순서를 보장하지 않기 때문에 순서를 보장하는 `List`로 반환하기도 애매하다. 

 

따라서 단순히 값의 모음이라는 의미의 상위 인터페이스인 `Collection`으로 반환한다.

---

Map 구현체

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

 

대표적으로 `HashMap`, `TreeMap`, `LinkedHashMap`이 있다.

 

 

Map vs Set

`Map`의 키는 `Set`과 같은 구조이다. 그리고 `Map`의 모든 것이 `Key`를 중심으로 동작한다. `Value`는 단순히 `Key` 옆에 따라 붙은 것 뿐이다. `Key` 옆에 `Value`만 하나 추가해주면 `Map`이 되는 것이다. 

 

`Map`과 `Set`은 거의 같다. 단지 옆에 `Value`를 가지고 있는가 없는가의 차이가 있을 뿐이다.

이런 이유로 `Set`과 `Map`의 구현체는 거의 같다.

• `HashSet → HashMap`
• `LinkedHashSet → LinkedHashMap`
• `TreeSet → TreeMap`

실제로 자바 `HashSet`의 구현은 대부분 `HashMap`의 구현을 가져다 사용한다. `Map`에서 `Value`만 비워두면 `Set`으로 사용할 수 있다.

 

 

 

HashMap

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

 

LinkedHashMap

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

 

TreeMap

• 구조: 레드-블랙 트리를 기반으로 한 구현이다.
• 특징: 모든 키는 자연 순서 또는 생성자에 제공된 `Comparator`에 의해 정렬된다.
• 성능: `get`, `put`, `remove`와 같은 주요 작업들은 `O(log n)`의 시간 복잡도를 가진다.
• 순서: 키는 정렬된 순서로 저장된다.

 

 

 

자바 HashMap 작동 원리

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

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

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

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

 

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

---

스택 자료 구조

 

 

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

나중에 넣은 것이 가장 먼저 나오는 것을 후입 선출이라 하고, 이런 자료 구조를 스택이라 한다.

 

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

 

예시

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

 

 

Stack 클래스는 사용하지 말자

자바의 `Stack` 클래스는 내부에서 `Vector`라는 자료 구조를 사용한다. 이 자료 구조는 자바 1.0에 개발되었는데, 지금은 사용되지 않고 하위 호환을 위해 존재한다.

 

지금은 더 빠른 좋은 자료 구조가 많다. 따라서 `Vector`를 사용하는 `Stack` 대신에 `Deque`를 사용하는 것이 좋다.

---

큐 자료 구조

 

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

후입 선출과 반대로 가장 먼저 넣은 것이 가장 먼저 나오는 것을 선입 선출이라 한다. 이런 자료 구조를 큐(Queue)라 한다.

 

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

 

 

• `Queue` 인터페이스는 `List`, `Set`과 같이 `Collection`의 자식이다.
• `Queue`의 대표적인 구현체는 `ArrayDeque`, `LinkedList`가 있다.

 

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

public class LinkedList<E> extends AbstractSequentialList<E>
      implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

 

 

예시 - `ArrayDeque`를 통해 `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("poll = " + queue.poll());
        System.out.println("poll = " + queue.poll());
        System.out.println("poll = " + queue.poll());
    }
}

---

Deque 자료 구조

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

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

 

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("pollFirst = " + deque.pollFirst());
        System.out.println("pollFirst = " + deque.pollFirst());
        System.out.println("pollLast = " + deque.pollLast());
        System.out.println("pollLast = " + deque.pollLast());
        System.out.println(deque);
    }
}

 

 

 

Deque 구현체와 성능 테스트

`Deque`의 대표적인 구현체는 `ArrayDeque`, `LinkedList`가 있다. 이 둘 중에 `ArrayDeque`가 모든 면에서 빠르다. 

 

100만 건 입력(앞, 뒤 평균)

• `ArrayDeque`: 110ms
• `LinkedList`: 480ms

100만 건 조회(앞, 뒤 평균)

• `ArrayDeque`: 9ms
• `LinkedList`: 20ms

 

둘의 차이는 `ArrayList` vs `LinkedList`의 차이와 비슷한데, 작동 원리가 하나는 배열을 하나는 동적 노드 링크를 사용하기 때문이다.

 

`ArrayDeque`는 추가로 특별한 원형 큐 자료 구조를 사용하는데, 덕분에 앞 뒤 입력 모두 `O(1)`의 성능을 제공한다. 물론 `LinkedList`도 앞 뒤 입력 모두 `O(1)`의 성능을 제공한다.

 

이론적으로 `LinkedList`가 삽입 삭제가 자주 발생할 때 더 효율적일 수 잇지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화 등을 고려할 때 배열을 사용하는 `ArrayDeque`가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

---

Deque와 Stack, Queue

`Deque`는 양쪽으로 데이터를 입력하고 출력할 수 있으므로, 스택과 큐의 역할을 모두 수행할 수 있다. `Deque`를 `Stack`과 `Queue`로 사용하기 위한 메서드 이름까지 제공한다. 

 

Deque 기본 메서드

 

• `push()`: 앞에서 입력한다.
• `pop()`: 앞에서 꺼낸다.

public class DequeStackMain {

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

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

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

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

 

`Deque`에서 `Stack`을 위한 메서드 이름까지 제공하는 것을 확인할 수 있다. 자바의 `Stack` 클래스는 성능이 좋지 않고 하위 호환을 위해 남겨져있다. `Stack` 자료 구조가 필요하면 `Deque`의 `ArrayDeque` 구현체를 사용하자.

 

 

 

 

 

• `offer()`: 뒤에서 입력한다.
• `poll()`: 앞에서 꺼낸다.

public class DequeQueueMain {

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

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

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

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

 

`Deque`는 `Queue`를 위한 메서드 이름까지 제공하는 것을 확인할 수 있다. `Deque` 인터페이스는 `Queue` 인터페이스의 자식이기 때문에, 단순히 `Queue`의 기능만 필요하면 `Queue` 인터페이스를 사용하고, 더 많은 기능이 필요하다면 `Deque` 인터페이스를 사용하면 된다. 

 

그리고 구현체로 성능이 빠른 `ArrayDeque`를 사용하자.