『Java』 Map, Stack, Queue, Deque

Map

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

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

 

자바는 HashMap, TreeMap, LinkedHashMap 등 다양한 Map 구현체를 제공한다.

이들은 Map 인터페이스의 메서드를 구현하며 각기 다른 특성을 가지고 있다.

 

HashMap

구조

해시를 사용해서 요소를 지정한다.

Key 값은 해시 함수를 통해 해시 코드로 변환되고 해시 코드는 데이터를 저장하고 검색하는 데 사용된다.

 

특징

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

 

순서

순서를 보장하지 않는다.

 

 

LinkedHashMap

구조

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

 

특징

입력 순서에 따라 순회가 가능하다.

HashMap과 같지만 입력 순서를 링크로 유지해야 하므로 조금 더 무겁다.

 

순서

입력 순서를 보장한다.

 

 

TreeMap

구조

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

 

특징

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

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

 

순서

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

 

 

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()	맵이 비어 있는지 여부를 반환한다.

 

 

Stack

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

 

📌 Stack 클래스는 사용하지 말자

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

 

 

Queue

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

 

 

 

Deque 자료구조

"Deque"는 "Double Ended Queue"의 약자로 이름에서 알 수 있듯이 양쪽 끝에서 요소를 추가하거나 제거할 수 있다.

일반적인 큐(Queue)와 스택(Stack)의 기능을 모두 포함하고 있는 유연한 자료 구조다.

 

데크, 덱 등으로 부른다.

 

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 인터페이스의 주요 메서드

메서드	설명
add(E e)	지정된 요소를 덱의 뒤쪽에 삽입한다.
offer(E e)	지정된 요소를 덱의 뒤쪽에 삽입 시도한다. 성공하면 true, 실패하면 false 반환
remove()	덱의 첫 번째 요소를 제거하고 반환한다. 덱이 비어 있으면 NoSuchElementException 발생
poll()	덱의 첫 번째 요소를 제거하고 반환한다.
element()	덱의 첫 번째 요소를 반환한다.
peek()	덱의 첫 번째 요소를 반환한다.
push(E e)	지정된 요소를 덱의 앞쪽에 삽입한다.
pop()	덱의 첫 번째 요소를 제거하고 반환한다.
size()	덱에 있는 요소의 개수를 반환한다.
isEmpty()	덱이 비어 있는지 여부를 반환한다. 비어 있으면 true, 아니면 false 반환
iterator()	덱의 요소를 순방향으로 반복하는 Iterator를 반환한다.
descendingIterator()	덱의 요소를 역방향으로 반복하는 Iterator를 반환한다.
contains(Object o)	덱에 지정된 요소가 포함되어 있는지 여부를 반환한다. 포함하면 true, 아니면 false 반환