컬렉션 프레임워크

💡

정의

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

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

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

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

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)
- 값을 찾기 위해 맨 앞부터 순차적으로 검색해야 하기 때문

{% endcolumns %}

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 을 지원하는 더 하위 수준의 잠금을 통해 더 많은 스레드가 병렬로 작업할 수 있음
- 읽기 작업은 대부분 잠금을 사용하지 않거나 최소한의 잠금을 사용하여 높은 효율성 제공

성능