컬렉션 프레임워크

자바에서 효율적인 자료구조를 사용할 수 있는 컬렉션들을 알아보자

컬렉션 프레임워크

정의

컬렉션 프레임워크는 자바에서 효율적으로 만들어 둔 자료구조이다.

소프트웨어를 개발하는 데 "항상" 필요한 자료구조를 사용해야 하는 경우 아래 두 가지 방법으로 사용할 수 있다.

직접 개발하는 경우
검증된 것을 재사용하는 경우

직접 개발하는 경우 개발자의 역량에 따라 검증된 자료구조에 비해 성능이 떨어질 수 있기 때문에 실무에서는 검증된 자료구조를 사용하며, 자바에서는 이를 컬렉션 프레임워크로 제공한다.

List

ArrayList

정의

ArrayList는 내부적으로 정적 배열을 사용하여 데이터를 관리하는 List 구현체이며, 순차적으로 데이터를 저장하는 선형 자료구조이다.

특징

배열을 쓰지만, 데이터가 꽉 차면 자동으로 더 큰 배열을 만들어 복사함으로써 동적으로 크기가 조절되는 것처럼 동작한다.
- 일반적으로 정적 배열을 사용하는 경우 데이터의 크기를 고정해야 하기 때문에 동적으로 관리하기 불편함을 개선한 자료구조이다.
동기화를 지원하지 않는다.

성능

장점 - O(1)

인덱스 기반 조회: get(index)
인덱스 기반 수정: set(index, value) (데이터를 바꾸기만 함, 밀어내기 없음)
맨 끝에 추가/삭제: add(value) / remove(size - 1)
- 데이터의 크기가 변경되는 작업으로 인해 만약 배열 크기 증가 작업이 수행되면 O(N) 이 소요된다.

단점 - O(N)

중간/맨 앞에 삽입/삭제: add(index, value) / remove(index)
- 해당 인덱스 뒤의 모든 데이터를 한 칸씩 밀거나 당겨야 하기 때문
값으로 검색 하는 탐색 과정: contains(value) / remove(value)
- 값을 찾기 위해 맨 앞부터 순차적으로 검색해야 하기 때문

ArrayList 의 맨 앞 또는 중간 인덱스에 값을 추가 하는 과정

ArrayList 는 내부적으로 정적 배열을 사용한다고 이해 했기 때문에, 이 과정에서 비용이 많이 든다는 것도 알 수 있다.

맨 앞이나 중간에 값을 추가 하게 되면 추가되는 데이터 만큼 크기가 증가한 배열을 새로 생성한다.

기존 ArrayList 에 저장 되어있는 데이터를 크기가 증가한 새로운 배열에 값을 복사한다.

원하는 인덱스에 새로운 값을 추가한다.

이 과정이 발생하고, 만약 배열의 크기가 크다면 훨씬 더 많은 비용이 발생할 수 밖에 없다.

ArrayList 는 언제 써야할까?

데이터 삽입/삭제는 주로 맨 뒤에서만 일어나고, 인덱스로 데이터를 자주 조회할 때

데이터 조회가 압도적으로 많은 경우

만약, 데이터의 중간 삽입/삭제가 빈번하게 발생하는 경우는 LinkedList 가 더 유리함

LinkedList

정의

LinkedList 는 Node(객체) 를 이용하여 객체 간 참조 주소 값을 연결하여 데이터를 관리하는 컬렉션이다.

특징

데이터를 삽입, 삭제 과정에서 ArrayList 의 배열 복사 행위가 없고 노드가 가르키고 있는 포인터만 변경하기 때문에 상대적으로 빠른 특징을 갖고 있다.
head, tail 값을 갖고 있는 노드 객체의 연결 덕분에 스택, 큐 같은 자료구조에 구현체로 사용된다.

성능

데이터를 삽입, 삭제하는 과정이 빠르며 최선(맨앞, 맨뒤 -> head, tail 을 저장하고 있음)은 O(1) 이지만, 탐색 과정 때문에 O(N) 의 시간복잡도를 갖고있다.

ArrayList 와 반대로 데이터를 조회하는 과정에서 노드의 순차적 접근으로 포인터가 가르키고 있는 값을 계속 타고 들어가서 조회하기 때문에 O(N) 이 된다.

임의의 데이터를 위치 기반으로 조회할 때 순차적 탐색 과정을 거치기 때문에 ArrayList 보다 성능이 좋지 않다.

LinkedList 는 언제 써야할까?

컬렉션에 있는 데이터를 중간 앞에서 삭제하거나 추가하는 경우 ArrayList 에 비해 성능이 훨씬 뛰어나기 때문에, 맨 끝이 아닌 다른 공간에 신규 데이터를 자주 추가하는 상황에 사용하기 좋다.

LinkedList 와 ArrayList 의 차이는 무엇일까?

이렇게 이론적으로 성능의 차이가 나타나는 두 컬렉션이지만, 조슈아 블로치가 X 에 게시한 글에 따르면 설계는 그러하지만 본인은 LinkedList 를 전혀 사용하지 않는다고 밝혔다.

이러한 성능의 차이는 ms 기준으로 나타내어 표현되는 숫자상 차이가 보이지만 개발자가 체감하기엔 굉장히 내부적으로 최적화가 잘 되어있다고 한다.

많은 영상에서 이 주제를 다루고는 있지만 결론적으로 ArrayList 를 기본적으로 사용하고 정말 특수한 환경이 아니라면 LinkedList 를 사용하지 않는다고 한다.

더이상 사용되지 않는 Vector

정의

ArrayList 와 동일하지만 syncrhonized 키워드가 적용되어 스레드 안정적으로 컬렉션의 기능을 지원한다.

Vector 는 동기화를 지원하기 때문에 성능이 굉장히 느린 컬렉션으로 실무에서는 적합하지 않아 사용되지 않는다.

자바에서는 Legacy 로 등록 해두었으며, 구 버전과 호환을 위해 남겨둔 상황이다.

동기화 지원 방법

아래 코드처럼 Vector 를 사용하지 않고, syncrhonizedList 를 사용하여 동기화를 지원 받을 수 있다.

List<String> list = Collections.synchronizedList(new ArrayList<String>());

Queue

PriorityQueue

정의

큐는 보통 FI-FO 에 의해 선형 자료구조에 속하지만, 우선 순위 큐는 일반적인 큐와 다르게 우선 순위를 부여하여 정렬되는 특징으로 비선형 자료구조에 속한다.

특징

Comparable 인터페이스를 필수로 구현하여 반환 값에 의해 우선순위를 결정한다.
null 을 허용하지 않는다.
동시성을 지원하지 않는다.
heap 자료구조를 사용하여 최대힙 또는 최소힙으로 정렬한다.

동기화 지원 방법

PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();

성능

Heap 의 정렬 기준 값에 따라 루트 노드에 배치되는 특성으로 인해 우선순위가 높은 데이터에 접근할 때 O(1) 로 처리된다.
삽입, 루트 노드에 있는 값 삭제는 데이터 처리 후 힙 재정렬 과정으로 인해 O(log N) 으로 처리된다.
특정 값 삭제, 특정 값 조회는 전체를 탐색하기 때문에 O(N) 이 소요된다.

우선순위 큐는 언제 사용할까?

이론적으로 우선 순위를 순서대로 수행할 때 사용한다.

예를 들어, TODO List 를 만들고 있다고하자.

사용자는 오늘 해야 할 일을 기록하고, 가장 먼저 해야 할 일에 중요도를 표시한다.

그럼, 중요도에 따라 가장 먼저 처리해야 할 일을 사용자에게 알려주면 어떨까?

Set

Set 은 비선형 자료구조의 인터페이스로 높은 검색 성능이 필요할 때 주로 선택되는 자료구조이다.

HashSet

정의

Hashtable 기반으로 동작하는 자료구조이며 hash 가 갖고 있는 특징을 띄고 있고, HashMap 을 내부적으로 사용하고 있다.

특징

hashCode() 로 반환되는 해시 함수의 결과 값을 통해 저장될 배열의 인덱스를 결정한다.
equals() 를 통해 값이 중복 되는지 결정한다.
null 을 허용한다.
동시성을 지원하지 않는다.

동기화 지원 방법

Set s = Collections.synchronizedSet(new HashSet(...));

성능

O(1) 시간복잡도로 단일 데이터의 삽입, 삭제, 조회할 수 있다.

HashSet은 언제 사용할까?

이론적으로 순서에 관계 없고 중복을 허용하지 않는 상황에서 자료구조로 선택할 수 있다.

예를 들어, 기술 블로그를 운영하고 있는데 사용자가 매일 몇 명씩 들어오는지 확인하고 싶다. 여기서 사용자는 하루에 N 번 접근이 가능하지만, 중복 제거로 인해 1번으로 측정이 가능하기 때문에, 일별 사용자 접속량을 조회하고 자정이 넘어갈 때 DB에 저장하고, 컬렉션을 새로 생성하면 어떨까?

LinkedHashSet

정의

중복은 허용하지 않지만 순서는 보장되어야 하는 비선형 자료구조에서 사용할 수 있는 컬렉션이다.

HashSet 과 LinkedList 를 조합하여 사용한다.

특징

HashSet 을 상속 받고 있기 때문에 데이터 조회에는 빠른 성능을 나타낸다.
순서를 보장하기 위해 LinkedHashMap 을 내부적으로 사용하며, Entry 의 before, after 를 기억하고 있어 순서를 보장한다.
동시성을 지원하지 않는다.

ListHashMap

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements SequencedMap<K,V>
{

    /*
     * Implementation note.  A previous version of this class was
     * internally structured a little differently. Because superclass
     * HashMap now uses trees for some of its nodes, class
     * LinkedHashMap.Entry is now treated as intermediary node class
     * that can also be converted to tree form. The name of this
     * class, LinkedHashMap.Entry, is confusing in several ways in its
     * current context, but cannot be changed.  Otherwise, even though
     * it is not exported outside this package, some existing source
     * code is known to have relied on a symbol resolution corner case
     * rule in calls to removeEldestEntry that suppressed compilation
     * errors due to ambiguous usages. So, we keep the name to
     * preserve unmodified compilability.
     *
     * The changes in node classes also require using two fields
     * (head, tail) rather than a pointer to a header node to maintain
     * the doubly-linked before/after list. This class also
     * previously used a different style of callback methods upon
     * access, insertion, and removal.
     */

    /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    @java.io.Serial
    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

동기화 지원 방법

Set s = Collections.synchronizedSet(new LinkedHashSet(...));

성능

조회, 삽입, 삭제는 HashSet 을 상속 받은 덕분에 O(1) 로 처리한다.

LinkedHashSet은 언제 사용할까?

이론적으로 순서를 보장하며 중복을 허용하지 않는 상황에서 자료구조로 선택할 수 있다.

예를 들어, 스포티파이 같은 음악 스트리밍 사이트를 클로닝하고 있다고 가정해보자.

사용자가 최신 들은 노래 목록을 제공하는데, 어느 날 사용자가 노래가 너무 좋아서 연속으로 100번을 재생했다.

그럼, 최신 재생 목록에 같은 노래 100개를 제공할 것이 아니라면 이러한 자료구조에 도움을 받을 수 있다고 생각한다. 다만, 과거에 들었다가 오늘 다시 듣는 경우 같이 논리적인 문제를 삼는 부분은 나름의 최적화가 필요하지 않을까?

TreeSet

정의

HashSet 처럼 순서를 보장하지 않고 중복을 허용하지 않는 자료구조이며, 내부적으로 RedBlackTree로 관리하며 데이터를 정렬하여 저장한다.

RedBlackTree 는 BinarySearchTree 에서 트리가 한 쪽으로 편향되어 치우치지 않도록 보완한 트리구조이다.

특징

다른 Set 자료형과 달리 null 을 허용하지 않는다.
Comparator 를 활용하여 사용자가 직접 정의한 정렬 방식을 지원한다.
동시성을 지원하지 않는다.

동기화 지원 방법

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

성능

데이터 조회, 삽입, 삭제에 O(log N) 이 소요된다.

언제 사용할까?

중복, null, 입력 순서가 허용되지 않지만 저장한 데이터에 의해 정렬이 필요한 경우 사용할 수 있다.

예를 들어, 랭킹을 표시해야 한다고 한다.

이 랭킹은 신규 유저가 맨 마지막에 오리란 법이 없으며, 유저가 새로운 기록에만 집중하며 이 유저는 모두 고유하다.

그럼 유저가 갖고 있는 스코어 정보를 기준으로 정렬하여 사용한다면 괜찮을 것 같다.

Map

Map 인터페이스는 Key 와 Value 를 이용하고, Key 는 항상 고유해야한다.

HashMap

정의

Map 형태를 따르며 Hashtable 기반 구현으로 내부적으로 배열, LinkedList, RedBlackTree 와 같은 여러 자료구조를 활용하여 유한하지 않는 해시의 값이 충돌했을 때 방지하도록 설계된 자료구조이다.

보조 해시 함수를 사용하여 Hashtable 보다 해시 충돌을 덜 발생 시켜 성능상 이점이 있다.
- hash = key.hashCode() ^ (hash >>> 16);

특징

hashCode() 의 결과 값을 통해 저장하게 될 배열의 인덱스를 결정하게 된다.
equals() 를 통해 중복 값을 검증하고, 중복이 발생했을 때 LinkedList 와 RedBlackTree 를 사용하며 빠른 검색 성능을 위해 최적화한다.
입력 순서를 보장하지 않는다.
Key 와 Value 모두 다 null 을 허용한다.
동시성을 지원하지 않는다.

동기화 지원 방법

Map m = Collections.synchronizedMap(new HashMap(...));
ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap();

synchronizedMap 과 ConcurrentHashMap 의 차이

두 방식 모두 멀티 스레드 환경에서 동시성을 보장받기 위해 사용하는 방식이다.

synchronizedMap: Collections 의 메서드로 인자로 받는 컬렉션을 래핑하여 해당 객체에 접근하기 전 락을 먼저 획득하는 객체 수준 잠금을 통해 동시성을 지원한다.
- 즉, 내부적으로 모든 접근에 대해 동기화를 사용하여 모든 쓰기 작업과 대부분의 읽기 작업에서 전체 맵 잠금이 발생하여 성능 저하가 발생
ConcurrentHashMap: 객체 접근 할 때 락을 걸고 회수하는 방식이 아닌, Hashtable 이 갖고 있는 버킷에 대한 Lock 을 지원하는 더 하위 수준의 잠금을 통해 더 많은 스레드가 병렬로 작업할 수 있음
- 읽기 작업은 대부분 잠금을 사용하지 않거나 최소한의 잠금을 사용하여 높은 효율성 제공

성능