[Java] Collection
- [ Languages ]/Java
- 2024. 8. 10.
개요
자바에는 데이터의 그룹(자료구조)을 나타내기 위한 Collection 인터페이스가 존재한다. Collection 인터페이스에는 List, Set, Queue가 존재하며, 해당 인터페이스들을 구현하는 다양한 구현체들이 존재한다.
+ Collections라는 클래스도 존재하는데, 여기에는 Collection과 그 하위 클래스들을 조작하기 위한 static 메서드들이 존재한다.
다양한 컬렉션 인터페이스들(+Map)을 살펴보고, 각 인터페이스를 구현하는 구현체의 특징과 자료구조, 시간복잡도 등에 대해서 정리해보겠다.
1. List
List는 순서를 보장하는 컬렉션 인터페이스이며, 중복을 허용한다.
1-1. ArrayList - [배열 기반의 리스트]
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
transient Object[] elementData; // non-private to simplify nested class access
ArrayList는 가변 크기의 배열로 구성된 리스트이다. 클래스를 보면 Object[] 형태로 데이터를 저장하고 있음을 알 수 있다.
가변 크기의 배열이라고 하지만, 실제로는 리스트에 데이터를 삽입할 때 배열이 다 차있다면 더 큰 배열에 복사하는 방식으로 동작한다.
- 기본 배열 capacity는 10이다.
- 배열이 다 찬 상태에서 데이터를 삽입하려고 하면, 크기가 1.5배 큰 배열에 복사한다.
사용
import java.util.*;
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(element); //O(1)
list.remove(idx); //O(n)
list.get(idx); //O(1)
list.contains(element); //O(n)
list.size(); //O(1)
- 조회: O(1) -> 배열을 이용하기 때문에 인덱스 번호를 이용하여 데이터에 직접 접근 가능하다. 단, 인덱스가 아닌 값으로 조회할 경우는 여전히 O(N)이 든다. (정렬된 자료구조가 아니므로 순차 탐색만 사용 가능하다.)
- 삽입: O(1) -> 데이터의 삽입은 일반적으로 O(1)이다. 배열이 다 찼다면 크기의 재조정이 필요할 수 있으나, 크게 시간복잡도에 영향을 끼치지 않았다.
- 삭제: O(N) -> 배열의 중간 원소에 접근하여 삭제하기 위해서는 배열 요소의 재조정이 필요하므로 느리다.
Object[] arr = new String[3]; // 실수
arr[0] = 1L; // 컴파일 에러 X
ArrayList<Object> list = new ArrayList<String>(); // 컴파일 에러
ArrayList는 조회에 이점을 가지는 List 자료구조이다. 직접 배열을 선언하여 구현할 수도 있지만, 사용하지 않는 데이터의 참조를 해제해 줌으로써 메모리 관리 측면에서 이득이 있다. 또한 배열을 사용할 때와 다르게 제네릭을 사용하여 컴파일 시점에 에러를 잡아낼 수 있다.
1-2. LinkedList - [노드 기반의 리스트]
LinkedList는 노드로 이루어진 리스트이다. 흔히 링크드 리스트에는 Singly Linked List와 Doubly Linked List가 존재하는데, 자바에서는 아래와 같이 양쪽에 포인터를 가지는 Doubly Linked List 형태를 사용하여 역순으로 탐색이 가능하게 하여 조회 성능을 조금이라도 높이고 있다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
...
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
자바에서 링크드리스트 구현체는 List뿐 아니라, 후술할 Stack이나 Queue에서도 사용되기 때문에 이를 위한 다양한 메서드들이 존재한다.
- 초기 크기가 지정되어 있지 않고, 동적으로 노드가 추가/삭제된다.
사용
import java.util.*;
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(element); //O(1)
list.remove(); //O(1)
list.get(index); //O(n)
list.contains(element); //O(n)
- 조회: O(N) -> Node의 포인터를 따라 탐색하면서 데이터를 찾아야 하므로, 이동 과정에 O(N)만큼의 시간복잡도가 소요된다.
- 삽입: O(1) -> 새로운 Node를 기존 Node의 Pointer로 연결해주기만 하면 된다.
- 삭제: O(N) -> 타겟 Node를 제거하고, 앞뒤 노드의 포인터만 조정해주면 되므로 삭제 자체는 O(1)의 시간복잡도를 갖는다. 다만 중간에 있는 데이터의 경우 조회+삭제의 과정을 필요로 하므로 O(N)이라고 하는 것이 옳다.
삽입과 삭제가 ArrayList보다 빠르고, 인덱스를 이용한 조회는 느리므로 데이터의 변경이 잦은 데이터로 리스트를 구성하고 싶을 때 사용하면 좋다.
1-3. SynchronizedList - [락을 사용하는 리스트 + 동시성 제어]
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
final Collection<E> c; // Backing Collection
@SuppressWarnings("serial") // Conditionally serializable
final Object mutex;public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
Collections 클래스에 구현되어 있는 inner static class로, 메서드 자체에 synchronized 락이 걸려있다. 단순히 메서드에 synchronized 키워드를 걸었기 때문에 모든 읽기/쓰기 동작에 락이 걸린다.
하지만 후술할 CopyOnWriteLinkedList는 쓰기 작업시 배열을 복제하기 때문에, 쓰기 작업이 많은 경우 SynchronizedList를 쓰는 것도 나쁘지 않은 선택일 수 있다.
1-4. CopyOnWriteArrayList - [배열 기반의 리스트 + 동시성 제어]
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
SynchronizedList와 비슷하게 동시성 제어를 위한 ArrayList 기반 리스트인 CopyOnWriteArrayList도 존재한다.
public E get(int index) {
return elementAt(getArray(), index);
}
public void add(int index, E element) {
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
}
}
CopyOnWriteArrayList에서 내부를 변경하는 메서드에서는 synchronized 블록을 사용하여 복사본을 만들어서 수행하도록 되어 있다. 대신 get()과 같이 읽기 작업에는 락이 걸리지 않기 때문에 읽기 작업이 많이 필요한 경우에 좋은 성능을 낼 수 있다.
2. Map
Map 인터페이스는 Key-Vaue 형태로 데이터를 저장하는 자료구조이다. Key는 중복을 허용하지 않고(중복된 Key를 넣을 경우 value가 갱신된다), Value의 경우 중복을 허용한다. key와 value 모두 null을 허용한다.
Collection 인터페이스를 직접 상속받는 인터페이스는 아니지만, 후술할 Set이 Map을 기반으로 구현되는 등 Collection과 밀접한 관계를 가지고 있다.
2-1. HashMap - [해시함수를 이용]
HashMap은 순서에 상관없이 데이터를 Key-Value 형태로 저장하는 자료구조이며, Key값으로 해시함수를 실행하여 반환된 결과를 통해 저장위치를 결정한다.
그렇다고 단순히 해시 함수만으로 value의 저장될 위치를 결정하는 단순한 구조는 아니다. HashMap은 Bucket이라고 불리는 원소들로 구성된 배열을 기반으로 저장되는데, 해시 함수를 이용하여 Key를 해싱하고, 그 값을 인덱스로 하여 버킷에 접근한다.
따라서 버킷 배열의 크기(CAPACITY)를 관리하기 위해서 동적으로 배열 크기를 조절한다. 이를 위해 부하율(LOAD_FACTOR)라는 개념을 사용하는데, 이것은 배열의 resize를 위한 상한선을 의미한다.
- 버킷의 기본 크기는 16이다.
- Load Factor가 0.75 이상이 되면, 버킷의 크기를 두 배로 늘린다.
또한 해시 함수를 이용하는 만큼, 다른 키의 해시값이 같은 '해시 충돌'이 발생할 수 있다. 따라서 각 버킷을 연결리스트로 구성하여, 충돌이 발생하면 버킷 연결리스트에 새로운 (key-value)쌍을 추가한다.
사용
import java.util.*;
HashMap<String, String> map = new HashMap<>();
map.put(key, value); //O(1)
map.get(key); //O(1)
map.containsKey(key); //O(1)
map.remove(key); //O(1)
map.size(); //O(1)
map.keySet(); //O(1) - key들로 이루어진 Set을 생성한다.
map.values(); //O(1) - value들로 이루어진 Collection을 생성한다.
map.getEntry(); //O(1) - Map<key, values>로 이루어진 Set을 생성한다.
- 조회/삽입/삭제: O(1) -> 해시함수를 이용해서 데이터를 저장/삽입/삭제할 버킷을 찾기 때문에 O(1)이다.
- keySet(): O(1) -> key들로 이루어진 Set을 반환하는데, 이 Set은 HashMap 객체의 복제본이 아니라, HashMap에 대한 Wrapper에 대한 뷰를 제공한다. 따라서 keySet().clear()를 하면 기존 hashMap의 데이터가 모두 삭제되므로 유의하자
- values(): O(1) -> value들로 이루어진 Collection을 생성해주는 함수인데, 이 또한 keySet()과 같이 복제본이 아닌 뷰를 제공한다.
- getEntry(): O(1) -> Key-Value로 이루어진 Map의 집합(Set<Map<Key, Value>>)을 반환하는데, 이 메서드도 복제본이 아닌 뷰를 제공한다.
2-2. LinkedHashMap - [삽입 순서에 따른 정렬을 보장]
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
앞서 설명한 HashMap은 순서를 보장하지 않는다. 별도의 정렬을 지원하지 않을 뿐 아니라, 로직상으로 들어간 순서대로 정렬되지도 않는다. 이를 해결하려면 LinkedHashMap을 사용하여 데이터의 삽입 순서를 보장할 수 있다.
공식 문서를 보면
This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.
라고 나와있는 것을 확인할 수 있는데, 내부적으로는 Doubly-linked list를 사용하고 있다고 한다. 버킷을 정렬할 때 리스트를 이용해서 정렬을 하는 것으로 추정된다.
+ LinkedHashMap 또한 List처럼 Comparator 등을 이용한 자유로운 정렬 기준을 보장하지는 않는 것처럼 보인다(대신 생성자 파라미터로 accessOrder를 지정해주면 접근 순서에 따라서 정렬(LRU)할 수는 있다). 대신 삽입한 순서대로 데이터가 정렬되기에 List<Entry<K, V>>로 변환하여 정렬한 후 Map에 삽입하는 두 번의 과정을 거치면 원하는 순서대로 정렬된 Map을 얻을 수 있다.
LinkedHashMap을 사용하여 정렬하기
public static void main(String[] args) {
Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("some type of love", 5);
linkedMap.put("dangerously", 10);
linkedMap.put("up all night", 2);
linkedMap.put("that's not how this works", 7);
System.out.println("Before Sorting: " + linkedMap);
// LinkedHashMap을 List로 변환
List<Map.Entry<String, Integer>> list = new ArrayList<>(linkedMap.entrySet());
// List를 키(key) 기준으로 정렬
list.sort(Map.Entry.comparingByKey());
// 정렬된 List를 LinkedHashMap에 다시 삽입
LinkedHashMap<String, Integer> sortedMap = new LinkedHashMap<>();
for (Map.Entry<String, Integer> entry : list) {
sortedMap.put(entry.getKey(), entry.getValue());
}
System.out.println("After Sorting by Key: " + sortedMap);
}
2-3. TreeMap - [데이터의 정렬을 보장]
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
TreeMap은 LinkedHashMap과 같이 데이터의 순서를 보장할 수 있는 또 다른 Map이다. TreeMap은 삽입 순서가 아니라, key 기준 오름차순 정렬된다. 정렬 기준을 바꾸기 위해서는 Comparator 인터페이스를 구현하여 생성자에 파라미터로 넘기거나, Comparable을 이용하여 객체의 정렬 기준을 커스텀할 수 있다.
// key 내림차순 정렬 예시
public static void main(String[] args) throws InterruptedException {
Map<String, Integer> treeMap = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s2.compareTo(s1);
}
});
treeMap.put("some type of love", 5);
treeMap.put("dangerously", 10);
treeMap.put("up all night", 2);
treeMap.put("that's not how this works", 7);
System.out.println("TreeMap: " + treeMap);
}
이렇게 정렬을 보장하기 때문에 HashMap보다 삽입, 삭제의 시간복잡도가 크다. 대신 정렬을 이용한 조회의 경우 HashMap보다 성능이 좋을 수 있다.
TreeMap은 이진트리의 일종인 Red-Black 트리로 되어 있는데, 이것은 트리가 skewed되지 않고 일정한 depth를 가지도록 보장하는 트리로, 최악의 경우에도 O(log N)의 시간복잡도를 보장한다.
사용
import java.util.*;
TreeMap<String, String> map = new TreeMap<>();
map.put(key, value); //O(logN)
map.get(key); //O(logN)
map.containsKey(key); //O(logN)
map.remove(key); //O(logN)
map.size(); //O(1)
2-4. ConcurrentHashMap [블록 단위 락 + 동시성 제어]
Map 자료구조에서 동시성을 제어하고 싶을 때 사용할 수 있는 대표적인 자료구조가 ConcurrentHashMap이다. ConcurrentHashMap은 메서드 내부에서 필요한 부분에 블록 단위 락을 걸고, 조회 메서드에는 락을 사용하지 않기 때문에 성능이 비교적 좋다.
기존의 HashTable도 동시성 제어를 지원하지만, 모든 메서드에 synchronized 키워드를 걸어서 동시성을 제어하며, 읽기 작업에는 락을 사용하지 않기 때문에 ConcurrentHashMap보다 좋지 않은 성능을 보인다.
위 함수는 HashTable의 데이터 삽입을 맡는 put과 get 메서드이다. 메서드 레벨에서 synchronized 키워드를 통해 락을 걸고 있으며, get 메서드에도 synchronized 키워드가 적용되어 있음을 확인할 수 있다. 이러한 불필요한 설계들로 인해 현재 HashTable 클래스는 사용을 권장하지 않고 있다.
반면 아래는 ConcurrentHashMap에서 데이터의 삽입을 관리하는 putVal 메서드이다. 동시성 제어가 필요한 부분은 중간에 있는 synchronized 블록을 통해서 처리하고 있는 모습을 볼 수 있다. 또한 get 메서드에는 별도의 락이 적용되어 있지 않다.
final V putVal(K key, V value, boolean onlyIfAbsent) {
...
synchronized (f) {
...
}
3. Set
Set은 null값을 허용하지만, 데이터의 중복은 허용하지 않는 자료구조이다.
위 사진처럼 Set은 Map과 유사한 클래스 구조를 가지고 있는데, 이는 실제로 Set 내부에서 Map을 사용하여 구현하고 있기 때문이기도 하다. HashSet을 예로 들어서 보자.
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();public boolean add(E e) {
return this.map.put(e, PRESENT) == null;
}
HashSet의 add 메서드인데, 내부에 존재하는 HashMap에 값(e)을 넣고 있음을 알 수 있다. HashMap의 value에 저장되는 값은 사실상 의미를 갖지는 않으며, 공간을 채우기 위해 Object타입 final 더미 객체를 하나 만들어서 넣어주는 것을 확인할 수 있다.
따라서 HashSet을 비롯한 대부분의 Set 구현 클래스들은 유사한 Map 구현 클래스를 이용하고 있으며, 따라서 사용하는 Map 구현체의 특징을 그대로 가진다.
4. Queue
마지막으로 큐 자료구조를 사용하기 위한 Queue 인터페이스이다. Stack과 다르게 Queue는 별도의 전용 구체 클래스를 제공하지는 않는데, 대신 상황에 맞게 우선순위 정렬이 필요한 경우에는 PriorityQueue를, 단순 FIFO 큐가 필요할 경우에는 LinkedList나 ArrayQueue를 선택할 수 있다.
4-1. LinkedList [연결 리스트로 큐 사용]
앞서 설명한 LinkedList를 Queue의 구현체로 사용할 수 있다. 앞서 설명했으므로 설명을 반복하지는 않겠다.
4-2. ArrayDeque [원형 배열 기반의 Deque 구현체]
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
transient Object[] elements;
transient int head;
transient int tail;
그런데 자바는 ArrayList 대신, 큐(덱)의 사용을 위한 ArrayDeque 이라는 덱 구현체를 별도로 제공하고 있다. 이는 ArrayList의 삽입/삭제의 비효율성을 극복하고, 원형 배열을 사용하여 더 나은 성능을 제공한다.
4-3. PriorityQueue [우선순위 큐]
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private final Comparator<? super E> comparator;
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
if (initialCapacity < 1) {
throw new IllegalArgumentException();
} else {
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
}
우선순위 큐는 배열 기반의 힙 자료구조를 사용하여 구현된다. 기본적으로는 오름차순 정렬(최소 힙)이며, Comparator 인터페이스의 compareTo()를 구현하여 매개변수로 넘기거나, Comparable을 사용하여 객체의 정렬 기준을 조작함으로써 우선순위를 정의할 수 있다.
사용
import java.util.*;
PriorityQueue<Integer> queue = new PriorityQueue<>(); //오름차순
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder()); //내림차순
queue.add(n); //O(logn) - 힙 재배열 필요
queue.peek(); //O(1)
queue.poll(); //O(logn) - 힙 재배열 필요
queue.size(); //O(1)
PriorityQueue는 완전 이진 트리 형태를 갖는 힙 기반으로 동작하기 때문에, O(logN)의 비선형 시간복잡도를 가진다.
4-4. BlockingQueue [큐 + 동시성 제어]
public interface BlockingQueue<E> extends Queue<E> {
boolean offer(E var1);
void put(E var1) throws InterruptedException;
E take() throws InterruptedException;
E poll(long var1, TimeUnit var3) throws InterruptedException;
...
}
BlockingQueue는 멀티스레드 환경에서도 동시성 문제가 발생하지 않도록 하는 큐 인터페이스의 일종으로, Producer-Consumer 패턴에서 유용하게 사용될 수 있다. 구현체로는 ArrayBlockingQueue, LinkedBlockingQueue 등이 존재하는데, 이름에서 알 수 있듯이 각각 배열 기반의 고정 크기 큐, 연결 리스트 기반 큐라는 특징을 갖는다.
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (count == 0) ? null : dequeue();
} finally {
lock.unlock();
}
}
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0)
notEmpty.await();
return dequeue();
} finally {
lock.unlock();
}
}
ArrayBlockingQueue의 poll, take 메서드를 보면 ReentrantLock이라는 락을 사용하는 것을 볼 수 있다. 이것은 synchronized에 기능이 추가된 락이라고 할 수 있는데, 이것을 통해서 동시성을 제어하는 것으로 보인다.
테스트
public static void main(String[] args) {
// 크기가 5인 ArrayBlockingQueue 생성
BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(5);
// 생산자 스레드
Thread producer = new Thread(() -> {
try {
for (int i=0; i<10; i++) {
System.out.println("[Produce]: " + i);
queue.put(i); // 큐가 가득 차면 대기
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
});
// 소비자 스레드
Thread consumer = new Thread(() -> {
try {
for (int i=0; i<10; i++) {
Integer value = queue.take(); // 큐가 비어 있으면 대기
System.out.println("[Consumed]: " + value);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
});
producer.start();
consumer.start();
}
ArrayBlockingQueue를 사용하여 간단하게 Producer-Consumer 패턴을 구현한 예시이다. 두 개의 스레드를 생성하고, 하나의 스레드에서는 queue.put()을 실행하고, 다른 하나의 스레드에서는 queue.take()를 실행한다. ArrayBlockingQueue이기 때문에 큐에 size의 제한이 있으므로, 큐가 가득 찬 상태에서 queue.put()을 통해서 데이터를 넣으려고 시도할 경우 더 이상 데이터를 추가하지 못하고 대기하게 된다.
실행 결과이다. Producer가 0~6까지 7개가 들어간 것 처럼 보일 수 있지만, 출력 시점의 차이일 뿐 큐에 들어가 있는 데이터의 수는 5를 넘지 않음을 확인할 수 있다.
간단하게 put() 시점에 queue.size()를 찍어보아도 알 수 있고, ArrayBlockingQueue 대신 capacity 제한이 없는 LinkedBlockingQueue를 사용해보면 데이터 10개로는 Produce와 Consumer의 출력이 겹치지 않는 것을 확인할 수 있다. Array먼저 시작된 Producer 스레드가 시작되고 나서 Consumer 스레드가 시작되는 텀 사이에 10개의 put()메서드는 실행을 마칠 정도로 빠른 작업이지만, ArrayBlockingQueue의 capacity로 인해서 put() 작업이 블록된 것이다.
실습 github: https://github.com/eckrin/various-tests
'[ Languages ] > Java' 카테고리의 다른 글
| [Java] Thread-safe하게 변수 관리하는 방법들 (0) | 2023.11.03 |
|---|---|
| [Java] 자바의 예외(Exception) 처리 (0) | 2023.02.12 |
| [Java] 람다식 이해하기 (0) | 2023.02.07 |
| [Java] stream (0) | 2022.08.07 |
| [Java] 자바의 동작 원리와 특징 (0) | 2022.07.08 |