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

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

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

- 키는 맵 내에서 유일해야 한다. 그리고 키를 통해 값을 빠르게 검색할 수 있다.

- 키는 중복될 수 없지만, 값은 중복될 수 있다.

- Map은 순서를 유지하지 않는다.

 

 

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

 

Map인터페이스의 주요 메서드는 다음과 같다.

 

 

이중에 HashMap을 가장 많이 사용한다.

코드와 결과를 보며 확인해보자.

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(); //set 자료구조로 반환.(중복되면 X, 순서 보장 X)
        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);
        }


    }
}

 

실행결과는 다음과 같다.

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

 

Set<String> keySet = studentMap.keySet()

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

 

 

키와 값 목록 조회

Map은 키와 값을 보관하는 자료 구조이다. 따라서 키와 값을 하나로 묶을 수 있는 방법이 필요하다. 이때 Entry를 사용한다. Entry는 키-값 쌍으로 이루어진 간단한 객체이다. Entry는 Map내부에서 키와 값을 함께 묶어서 저장할 때 사용한다.

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

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

 

 

Collection<Integer> values = studentMap.values();

Map의 값 목록은 중복을 허용한다. 따라서 중복을 허용하지 않는 Set으로 반환할 수는 없다. 그리고 입력 순서를 보장하지 않기 때문에 List로 반환하기도 애매하다. 따라서 단순히 모음이라는 의미의 상위 인터페이스인 Collection으로 반환한다.

 

 

 

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

만약 Map에 같은 키로 다른 값을 저장하면 어떻게 될까?

public class MapMain2 {
    public static void main(String[] args) {
        HashMap<String, Integer> studentMap = new HashMap<>();
        studentMap.put("studentA", 90);
//        System.out.println(studentMap);

        studentMap.put("studentA", 100); //같은 키에 저장시 기존 값 교체
        System.out.println(studentMap);

        boolean containsKey = studentMap.containsKey("studentA");
        System.out.println("containsKey = " + containsKey);

        //특정 학생의 값 삭제
        studentMap.remove("studentA");
        System.out.println(studentMap);

    }
}

Map에 값을 저장할 때 같은 키에 다른 값을 저장하면 기존 값을 교체한다.

studentA=90에서 studentA=100으로 변경된 것을 확인할 수 있다.

 

만약 같은 학생이 Map에 없는 경우에만 데이터를 저장하려면 어떻게 해야할까?

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("studenB",100);
        System.out.println(studentMap);

    }
}

실행 결과는 다음과 같다.

{studentA=50}
{studentA=50}
{studentA=50, studenB=100}

 

putIfAbsent()는 영어 그대로 없는 경우에만 입력하라는 뜻이다. 이 메서드를 사용하면 키가 없는 경우에만 데이터를 저장하고 싶을 때 코드 한줄로 편리하게 처리할 수 있다.

 

 

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

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

 

 

Map vs Set

그런데 Map을 어디서 많이 본 것 같지 않은가? Map의 키는 중복을 허용하지 않고, 순서를 보장하지 않는다.

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으로 사용할 수 있다.

 

1. HashMap

- 구조 : HashMap은 해시를 사용해서 요소를 저장한다. 키(Key)값은 해시 함수를 통해 해시 코드로 변환되고, 이 해시 코드는 데이터를 저장하고 검색하는 데 사용된다.

- 특징 : 삽입, 삭제, 검색 작업은 해시 자료 구조를 사용하므로 일반적으로 상수 시간(O(1))의 복잡도를 가진다.

- 순서 : 순서를 보장하지 않는다.

 

2. LinkedHashMap

- 구조 : LinkedHashMap은 HashMap과 유사하지만, 연결 리스트를 사용하여 삽입 순서 또는 최근 접근 순서에 따라 요소를 유지한다.

- 특징 : 입력 순서에 따라 순회가 가능하다. HashMap과 같지만 입력 순서를 링크로 유지해야하므로 조금 더 무겁다.

- 성능 : HashMap과 유사하게 대부분의 작업은 O(1)의 시간 복잡도를 가진다.

- 순서 : 순서를 보장한다.

 

3. TreeMap

- 구조 :TreeMap은 레드-블랙 트리를 기반으로 한 구현이다.

- 특징 : 모든 키는 자연 순서 또는 생성자에 제공된 Comparator에 의해 정렬된다.

- 성능 : get, put, remove와 같은 주요 작업들은 O(log n)의 시간 복잡도를 가진다.

- 순서 : 키는 정렬된 순서로 저장된다.

 

 

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);
        map.put("C",10);
        map.put("B",10);
        map.put("A",10);
        map.put("1",10);
        map.put("2",10);

        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 = {}
A=10 
1=10 
B=10 
2=10 
C=10 

map = {}
C=10 
B=10 
A=10 
1=10 
2=10 

map = {}
1=10 
2=10 
A=10 
B=10 
C=10 

 

HashMap : 입력한 순서를 보장하지 않는다.

LinkedHashMap : 키를 기준으로 입력한 순서를 보장한다.

TreeMap : 키 자체의 데이터 값을 기준으로 정렬한다.

 

 

자바 HashMap 작동 원리

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

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

- Key를 사용해서 햇 ㅣ코드를 생성한다.

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

 

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

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

 

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

 

 

스택 자료 구조

스택(Stack)구조

다음과 같은 1, 2, 3 이름표가 붙은 블록이 있다고 가정하자.

이 블록을 다음과 같이 아래쪽은 막혀있고, 위쪽만 열려 있는 통에 넣는다고 생각해보자. 위쪽만 열려있기 때문에 위쪽으로 블록을 넣고, 위쪽으로 블록을 빼야한다. 쉽게 이야기해서 넣는 곳과 빼는 곳이 같다.

이번에는 넣은 블록을 뺀다고 가정하자.

블록을 빼려면 위에서부터 순서대로 빼야한다.

블록은 3 -> 2 -> 1 순서로 빠질 것이다.

 

정리하면 다음과 같다.

1(넣기) -> 2(넣기) -> 3(넣기) -> 3(빼기) -> 2(빼기) -> 1(빼기)

 

이런 구호즐 후입 선출이라 한다

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

 

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

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
[]

 

실행 결과를 보면, 1,2,3으로 입력하면 3,2,1로 출력되는 것을 확인할 수 있다. 나중에 입력한 값이 가장 먼저 나온다.

 

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

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

 

 

 

큐 자료 구조

큐 자료구조는 선입선출(FIFO, First In First Out)으로 후입 선출과 반대로 가장 먼저 넣은 것이 가장 먼저 나오는 것을 선입선출이라 한다.

정리하면 다음과 같다

1(넣기) -> 2(넣기) -> 3(넣기) -> 1(빼기) -> 2(빼기) -> 3(빼기)

 

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

 

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

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

- Deque는 조금 뒤에 설명한다.

 

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

 

public class QueueMain {

    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();

        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println("queue = " + 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 = " + queue);

    }
}

queue = [1, 2, 3]
queue.peek() = 1
queue.poll() = 1
queue.poll() = 2
queue.poll() = 3
queue = []

 

선입선출 구조(FIFO)의 구조가 이뤄지는것을 확인할 수 있다. 가장 먼저 입력한 값이 가장 먼저 나온다.

 

 

 Deque 자료 구조

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

데크, 덱 등으로 부른다.

- offerFirst() : 앞에 추가한다.

- offerLast() : 뒤에 추가한다.

- pollFirst() : 앞에서 꺼낸다.

- pollLast() : 뒤에서 꺼낸다.

 

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

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 = " + 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 = []

 

 

입력순서는 다음과 같다

- 앞으로 1을 추가한다.

- 앞으로 2를 추가한다.(앞에 추가했으므로 1이 뒤로 밀려난다. [2, 1])

- 뒤로 3을 추가한다. [2, 1, 3]

- 뒤로 4를 추가한다. [2, 1, 3, 4]

 

앞에서 2번 꺼내면 2, 1이 꺼내진다 이후 뒤에서 두번 꺼내면 4, 3이 꺼내진다.

 

Deque 구현체와 성능 테스트

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

 

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

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

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

 

 

Deque와 Stack, Queue

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

Deque를 Stack과 Queue로 사용하기 위한 메서드를 이름까지 제공한다(push, pop, offer, poll

 

public class DequeStackMain {

    public static void main(String[] args) {
        ArrayDeque<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 = " + deque);

    }
}

실행결과는 다음과 같다.

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

 

 

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

public class DequeQueueMain {

    public static void main(String[] args) {
        ArrayDeque<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
[]

 

Deque에서 Queue를 위한 메서드 이름까지 제공하는 것을 확인할 수 있다. Deque 인터페이스는 Queue 인터페이스의 자식이기 때문에, 단순이 Queue의 기능만 필요하면 Queue인터페이스를 사용하고 더많은 기능이 필요하면 Deque 인터페이스를 사용하면 된다.(Stack은 안된다) 그리고 구현체로 성능이 빠른 ArrayDeque를 사용하자