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

황상익·2024년 7월 1일

Inflearn JAVA

목록 보기
39/61

컬렉션 프레임워크 - Map

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

  • 키는 맵 내에서 유일해야 한다. 키를 통해 값을 빠르게 검색 가능
  • 키는 중복X, 값은 중복 될 수 있음
  • 순서 유지 X


HashMap , TreeMap , LinkedHashMap 등 다양한 Map 구현체를 제공


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 = " + studentMap);

        Integer rst = studentMap.get("studentD");
        System.out.println("rst = " + rst);

        System.out.println("KeySet 활용");
        Set<String> keySet = studentMap.keySet();
        //key를 반환 (Set) 자료구조로 반환
        //순서를 보장X, 중복X -> Set 자료구조 형태
        for (String key : keySet) {
            Integer val = studentMap.get(key);
            System.out.println("key = " + key + "val = " + val);
        }

        System.out.println("Values 활용");
        //중복이 될 수 있기 때문에 Collection
        //List로 나오지는 않는다. (순서를 보장 X)
        Collection<Integer> values = studentMap.values(); // collection을 반환
        for (Integer value : values) {
            System.out.println("value = " + value);
        }

        System.out.println("entrySet 활용");
        //Key값, Value을 묶어서 활용
        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);
            System.out.println("value = " + value);
        }

    }
}

키와 값 목록 조회

키와 값을 하나로 묶을 수 있는 방법이 필요, 이때 Entry를 사용
Entry는 키 값의 쌍으로 이루어진 간단한 객체, Entry는 Map 내부에서 키와 값을 함께 묶어서 저장할때 사용
Map에 키와 값으로 데이터 저장, Map은 내부에서 키와 값을 하나로 묶는 Entry 객체를 만들어서 보관.

값 목록 조회 

Collection<Integer> values = studentMap.values(

Map의 값 목록을 중복 허용, 중복을 허용하지 않는 Set으로 반환X
입력 순서를 보장X, List로 반환도 애매.

컬렉션 프레임워크 - Map 2

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

        //학생 성적 데이처 추가
        studentMap.put("studentA", 90);
        System.out.println("studentMap = " + studentMap);

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

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

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


    }
}

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

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

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

        System.out.println("studentMap = " + studentMap);

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

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

Map 인터페이스를 구현한 여러 클래스를 통해 사용할 수 있다. 대표적으로 HashMap, TreeMap, LinkedHashMap 이 있다.

Map vs Set
Map의 키는 중복을 허용하지 않고, 순서를 보장하지 않는다. Map 키가 바로 바로 Set과 같은 구조, 그리고 Map은 모든 것이 Key를 중심으로 동작.
Value는 단순히 Key 여펭 따라 붙은 것. Key 옆에 Value 하나만 추가해주면 Map

  1. HashMap:
  • 구조 : HashMap 은 해시를 사용해서 요소를 저장한다. 키( Key ) 값은 해시 함수를 통해 해시 코드로 변환되고, 해시 코드는 데이터를 저장하고 검색하는 데 사용된다.
  • 특징 : 삽입, 삭제, 검색 작업은 해시 자료 구조를 사용하므로 일반적으로 상수 시간(O(1))의 복잡도
  • 순서: 순서를 보장하지 않는다
  1. LinkedHashMap:
  • 구조 : 연결 리스트를 사용하여 삽입 순서 또는 최근 접근 순서에 따라 요소를 유지한다.
  • 특징 : HashMap 과 같지만 입력 순서를 링크로 유지해야 하므로 조금 더 무겁다.
  • 성능 : HashMap 과 유사하게 대부분의 작업은 O(1) 의 시간 복잡도
  • 순서 : 입력 순서를 보장한다
  1. 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<>());
    }

    public static void run(Map<String, Integer> map) {
        System.out.println("map.getClass() = " + 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 next = iterator.next();
            System.out.println("next = " + next);
            System.out.println("map = " + map.get(next));
        }
        System.out.println();
    }
}

자바 HashMap 작동 원리

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

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


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

Stack 자료 구조

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

public class StackMain {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println("stack = " + 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);
    }
}

큐 자료구조

선입 선출(FIFO, First In First Out)
가장 먼저 넣은 것이 가장 먼저 나오는 것

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

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

Deque 자료구조

public class DequeMain {
    public static void main(String[] args) {
        Deque<Integer> dq = new ArrayDeque<>();

        dq.offerFirst(1);
        System.out.println("dq = " + dq);
        dq.offerFirst(2);
        System.out.println("dq = " + dq);
        dq.offerLast(3);
        System.out.println("dq = " + dq);
        dq.offerLast(4);
        System.out.println("dq = " + dq);

        System.out.println("dq.peekFirst() = " + dq.peekFirst());
        System.out.println("dq.peekLast() = " + dq.peekLast());

        System.out.println("dq.pollFirst() = " + dq.pollFirst());
        System.out.println("dq.pollFirst() = " + dq.pollFirst());
        System.out.println("dq.pollLast() = " + dq.pollLast());
        System.out.println("dq.pollLast() = " + dq.pollLast());
        System.out.println("dq = " + dq);
    }
}

Deque 구현체와 성능 테스트

대표적인 구현체는 ArrayDeque , LinkedList

ArrayList Vs LinkedList 차이 비슷
작동 원리가 하나는 배열을 하나는 동적 노드 링크 사용
ArrayDeque는 추가로 특별한 원형 큐 자료구조 사요으 앞 뒤 입력 모두 O(1)의 성능을 제공
LinkedList 가 삽입 삭제가 자주 발생할 때 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화 등을 고려할 때 배열을 사용하는 ArrayDeque 가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

Deque와 Stack, Queue


양쪽으로 데이터를 입력 출력, 스택과 큐의 역할을 모두 수행 가능

Deque - Stack

  • push 앞에서 입력
  • pop 앞에서 호출

Deque - Queue

  • offer() 를 호출하면 뒤에서 입력한다.
  • poll() 을 호출하면 앞에서 꺼낸다.
public class DequeStackMain {
    public static void main(String[] args) {
        Deque<Integer> dq = new ArrayDeque<>();

        dq.push(1);
        dq.push(2);
        dq.push(3);
        System.out.println("dq = " + dq);

        //꺼낼 요소 확인 (꺼내지 않고 단순 조회만)
        System.out.println("dq.peek() = " + dq.peek());

        //스택 요소 뽑기
        System.out.println("dq.pop() = " + dq.pop());
        System.out.println("dq.pop() = " + dq.pop());
        System.out.println("dq.pop() = " + dq.pop());
        System.out.println("dq = " + dq);
    }
}

public class DequeQueueMain {
    public static void main(String[] args) {
        Deque<Integer> dq = new ArrayDeque<>();


        dq.offer(1);
        dq.offer(2);
        dq.offer(3);
        System.out.println("dq = " + dq);

        System.out.println("dq.peek() = " + dq.peek());

        System.out.println("dq.poll() = " + dq.poll());
        System.out.println("dq.poll() = " + dq.poll());
        System.out.println("dq.poll() = " + dq.poll());
        System.out.println("dq.poll() = " + dq.poll());
        System.out.println("dq = " + dq);
    }
}
profile
황상익
개발자를 향해 가는 중입니다~! 항상 겸손
이전 포스트

Set

다음 포스트

컬렉션 프레임워크 - 순회, 정렬, 전체 정리

0개의 댓글