• map

    • map은 키와 값의 쌍으로 이루어진 데이터를 저장하는 자료구조
    • 맵(Map)은 사전(dictionary)과 비슷한 구조
      • “people”: “사람”, “baseball”:”야구”
    • Map은 리스트나 배열처럼 순차적으로(sequential) 해당 요소 값을 구하지 않고 key를 통해 value를 얻는 구조
    • Map 역시 List와 마찬가지로 인터페이스
      • Map 인터페이스를 구현한 Map자료형에는 HashMap, LinkedHashMap, TreeMap 등
      • HashMap이 일반적으로 사용
    • 기본 문법
      • Map<String, String> map = new HashMap<>();
    • 주요특징
      • 키의 유일성. 키는 중복이 안됨
        • 그러나, value의 중복은 상관없음
      • 순서가 없음
        • index로 값을 구할수 없음
        • LinkedHashMap은 삽입된 순서 보장, TreeMap은 키를 가지고 정렬된채 삽입.
          • 그러나, index로 값을 구할수 없다는 것은 동일
      • 빠른 검색의 속도의 원리

        • 리스트에서 검색시 값을 통해 검색을 하게 되면, 모든 sequaltial index를 순차조회해야함

        • 해시테이블

          Untitled

          • 원리
            • map은 key를 일정한 길이를 갖는 임의의 숫자로 변환하는 해시함수를 통해 해시코드라는 정수 값을 반환하고 해시함수를 통해서 반환되는 값은 항상 일정
            • 해시코드를 배열의 크기로 나눈 나머지를 인덱스로 사용
          • 장점
            • map에서는 key를 통해 검색을 하므로, O(1)의 복잡도로 굉장히 효율적이고 빠른 검색이 가능
              • redis등의 key:value기반의 데이터베이스에서 빠른 성능을 보이는것도 비슷한 원리
          • 단점
            • 해시충돌 가능성과 여유있는 배열사이즈 할당을 위한 공간의 비효율 발생
              • 해시충돌 가능성은 같은 주소값을 가리키는 데이터들을 연결 리스트 형태로 저장하고, 연결리스트를 순회하면 key값을 찾는 방식으로 해결
    • 주요 메서드
      • put(key, value);
        • key/value를 map에 추가
        • putIfAbsent : 주어진 키가 아직 맵에 없을 때만 주어진 값을 맵에 추가
      • get(key)
        • key를 통해 value를 return
        • getOrDefault(Object key, V defaultValue) : key가 없으면 deaultValue리턴
      • containsKey : key가 있는지 true/false return
      • remove : key를 통해 삭제 후, 그 value값을 리턴
      • size : Map의 갯수를 리턴
      • isEmpty() : 맵이 비어있으면 true 리턴
      • keySet() : 맵에 있는 모든 키를 Set 형태로 반환
      • values() : 맵에 있는 모든 값을 Collection 형태로 반환
    • map의 출력시에 순서가 없음에 주의

      • index사용불가

      • Enhanced for문

      • iterator

        image.png

        • 자바의 컬렉션 프레임워크는 컬렉션에 저장된 요소를 읽어오는 방법을 Iterator 인터페이스로 표준화
        • Collection 인터페이스에서는 Iterator 인터페이스를 구현한 클래스의 인스턴스를 반환하는 iterator() 메소드를 정의
        • hasNext() : 해당 이터레이션(iteration)이 다음 요소를 가지고 있으면 true를 반환
        • next() : 이터레이션(iteration)의 다음 요소를 반환
    • 순서가 있는 map
      • LinkedHashMap은 입력된 순서대로 데이터를 저장
      • TreeMap은 입력된 key의 오름차순 순서로 정렬된 데이터를 저장

  • set

    • set은 수학에서의 집합과 유사한 성질을 지닌 자료형
    • HashSet이 대표적인 set인터페이스 구현자료형
      • map과 마찬가지로 LinkedHashSet, TreeSet 존재
      • Set<String> set = new HashSet<>();
        • Set<Integer> s1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5, 6));
          • 컬렉션 객체를 인자로 사용가능
    • 주요 특징
      • 중복없음
      • 순서 없음
        • 인덱싱을 통해 자료형의 값을 얻을 수 없음
        • Map과 마찬가지로 Enhanced for문, Iterator 활용
    • 주요 메서드
      • 일반 collection 프레임워크의 메서드 공유
        • add, remove, contains, size, isEmpty, clear
        • 해시테이블을 활용한 검색으로 인해 contains, remove 등의 성능 O(1)
      • retainAll을 통해 교집합
      • addAll을 통해 합집합
      • removeAll을 통해 차집합

  • queue

    Untitled

    • 가장 먼저 저장된(push) 데이터가 가장 먼저 인출(pop)되는 선입선출(FIFO)의 자료 구조
    • Queue<Integer> q = new LinkedList<>();
      • 위와 같이 Queue를 구현한 LinkedList를 통한 선언이 가장 보편적
    • Java에서 큐를 구현할 때 LinkedList를 사용하는 이유
      • LinkedList의 구조가 큐의 기본 동작에 매우 적합
      • LinkedList는 이중 연결 리스트(doubly linked list)로, 각 노드가 이전 및 다음 노드에 대한 참조를 하므로, 큐의 주요 연산인 삽입(offer)과 삭제(poll)에 있어서 효율적인 성능을 제공
      • addLast는 ArrayList도 O(1)이나, ArrayList의 remove(0)의 경우 O(n)발생
      • 큐의 특성상 빈번한 addLast, pollFirst
      • LinkedList의 경우 추가도 O(1), 제거도 O(1) 복잡도. 더불어 조회관련한 메서드는 Queue에는 존재하지 않으므로, 인터페이스와 구현체 구조를 통해 비효율문제 발생차단
    • 주요메서드
    • 먼저 삽입된 데이터를 꺼내서 비교해야 하는 작업일경우 queue 사용
    • 예시
    • 우선순위 큐

  • ArrayList와 LinkedList비교

  • stack

  • deque