[인프런 김영한 실전 자바 - 중급편] 컬렉션 프레임워크 - Map, Stack, Queue

Map

• Map : 키(key) - 값(value)의 쌍으로 저장하는 자료 구조이다.
  
  • 키는 맵 내에서 유일해야 하지만 값은 중복될 수 있다.
  • 키를 통해 값을 빠르게 검색할 수 있다.
  • 순서를 유지하지 않는다.
• Map에서의 키(key)는 유일하며 순서가 보장되지 않기에 Set 자료 구조에 저장되고 반환된다.
• 값은 순서는 보장하지 않지만 중복되어도 상관 없기에 Collection으로 반환된다.
  • 중복을 허용하기에 Set으로 반환하기에도 애매하고 순서를 보장하지 않기에 List로 반환하기도 애매하기에 상위 인터페이스인 Collection으로 반환한다.
• Map의 내부 인터페이스로 Entry가 존재하며 키와 값의 쌍으로 이루어진 객체이다.
  • Map에 키와 값으로 데이터를 저장하면 Entry 객체를 만들어서 키와 값을 묶어서 저장한다.

• entrySet()로 Map 내부의 Entry 객체 목록을 반환 받을 수 있다.
• values(), keySet()으로 값 / 키의 목록을 반환 받을 수 있다.

 

HashMap<String, Integer> studentMap = new HashMap<>();

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

• Map에 값을 저장할 때 같은 키에 다른 값을 저장하게 되면 기존 값을 교체한다.
  
  • studentA라는 키에 90이라는 값이 들어갔다가 이후에 같은 키에 저장을 하게 되면서 100이라는 값이 들어가게 된다.

 

• Map의 키는 Set과 같은 구조이며 Map과 Set의 구현은 거의 동일하다.
  • Map에서 value를 비워두면 Set으로 사용할 수 있다.
  • 자바에서 HashSet의 구현은 HashMap의 구현을 가져다 사용한다.
  • HashSet과 HashMap의 구현은 동일하지만 HashMap에 해시 인덱스로 저장할 때는 Entry 객체 단위로 키 - 값을 쌍으로 저장한다.

 

---

HashMap

• HashMap
  
  • 해시를 사용해서 요소를 저장하며 키는 해시 함수를 통해 해시 코드로 변환되고 해시 코드는 데이터를 저장하고 검색하는데 사용한다.
  • 해시 자료 구조를 사용하기에 주요 연산에 O(1) 소요된다.
  • 순서를 보장하지 않는다.

 

• 해시를 사용해서 키와 값을 저장하는 자료 구조를 해시 테이블이라 한다.
  
  • HashSet도 해시 테이블의 주요 원리를 사용하지만 키 - 값 쌍을 저장하는 대신 키만 저장한다.
• HashMap의 키로 사용되는 객체는 equals(), hashCode()를 반드시 오버라이딩 해줘야 한다.
• HashMap은 가장 많이 사용하는 Map 구현체.

---

LinkedHashMap

• LinkedHashMap
  • HashMap과 유사하지만 LinkedList를 사용해여 삽입 순서 / 최근 접근 순서에 따라 요소를 유지한다.
  • 주요 연산에 O(1) 소요된다.
  • 입력 순서를 보장한다.

---

TreeMap

• TreeMap
  
  • 레드-블랙 트리를 기반으로 구현했다.
  • 모든 키는 자연 순서 / 생성자에 제공된 Comparator에 의해 정렬된다.
  • 주요 연산에 O(log n) 소요된다.
  • 키는 정렬된 순서로 저장된다.

---

Stack

• Stack : 후입 선출(LIFO) 구조를 가지는 자료 구조.
  
  • 가장 먼저 넣은 데이터가 가장 나중에 나오는 구조 = 가장 나중에 넣은 데이터가 가장 먼저 나오는 구조
• 히스토리를 관리하는 용도로 사용하기 좋다.
• 데이터를 추가할 때는 push(), 데이터를 꺼낼 때는 pop()을 사용한다.

 

• Stack 클래스
  • Stack 클래스 내부에서는 Vector 자료 구조를 사용하는데 지금은 사용되지 않고 하위 호환만을 위해 존재한다.
    Stack 클래스를 사용해서는 안된다. 대신 Deque의 ArrayDeque를 사용하는 것이 좋다.

---

Queue

• Queue : 선입 선출(FIFO) 구조를 가지는 자료 구조.
  
  • 가장 먼저 넣은 데이터가 가장 먼저 나오는 구조 = 가장 나중에 넣은 데이터가 가장 나중에 나오는 구조.
• Queue는 예약 시스템 같이 순서대로 작업을 해놓고 나중에 실행할 때 사용하기 좋다.
• LinkedList는 Deque와 List 인터페이스를 모두 구현한다.

 

• 데이터를 추가할 때는 offer(), 꺼낼 때는 poll()을 사용한다.

---

Deque

• Deque : "Double Ended Queue"의 약자로 양 끝에서 요소를 추가하거나 제거할 수 있으며 Queue와 Stack의 기능을 모두 포함하고 있는 자료 구조.
  
  • 데크 / 덱 등으로 불린다.
  • Deque는 양쪽으로 데이터를 입력, 출력할 수 있으므로 Stack과 Queue의 역할을 모두 수행할 수 있다.
    • Stack, Queue와 같은 메소드 명도 제공한다.

 

• Deque의 구현체로는 ArrayDeque와 LinkedList가 있다.
  
  • 모든 면에서 ArrayDeque가 성능이 더 좋다.
  • 둘의 차이는 ArrayDeque는 배열을 사용하고 LinkedList는 동적 노드 링크를 사용하기 때문에 성능 차이가 난다.
  • ArrayDeque는 원형 큐 자료 구조를 사용한다.
  • Stack, Queue를 구현할 때 ArrayDeque를 사용하는 것이 좋다.

---

출처: [인프런 김영한 실전 자바 - 중급편]

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2/dashboard

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