[Java] 올바른 Collection 선택하기

🙋 들어가며

물건을 담을 수 있는 그릇의 종류는 다양합니다.

데이터 세계에서 그릇을 자료 구조(Data Structure)라고 표현합니다.

자바에서도 다양한 자료 구조를 제공합니다. 이번 글을 통해서 상황에 맞게 사용하는 방법을 알아보겠습니다.

---

🗂️ Java Collection Framework

자바에서 제공하는 다양한 자료 구조들의 모음을 Collection이라고 부릅니다.

다양한 인터페이스와 클래스들의 집합이며, 자바에서는 Collection 외에도 배열이라는 구조도 제공합니다.

Collection 인터페이스를 상속받는 주요 인터페이스는 다음과 같습니다.

1. List 인터페이스
2. Set 인터페이스
3. Queue 인터페이스

 

Map 인터페이스는 구조상의 차이로 별도로 정의되지만 동일하게 Java Collection Framework에 포함됩니다.

구성하고 있는 인터페이 간의 상속 관계는 다음 그림과 같습니다.

그림 1: Collection Framework의 상속 관계

😁 주요 특징

우리의 편의를 위해서 제공하는 이 프레임워크는 몇 가지 특징이 존재합니다.

1. 인터페이스 기반 : 다형성을 통해서 유연함을 제공합니다.
2. 제네릭 사용 : 제네릭을 통해서 타입 안전성을 제공합니다.
3. 유연한 크기 변화 : 동적으로 크기를 조정할 수 있습니다.
4. 표준 라이브러리 : 별도의 설치 없이도 편하게 사용할 수 있습니다.

🤜 vs Collections

자바에서는 Object를 보다 편하게 사용하기 위해서 Objects라는 유틸리티 클래스를 제공합니다.

Collection에서도 편의를 제공해주는 유틸리티 클래스인 Collections가 존재합니다.

Collection을 다루는 메서드나 특수한 형태의 Collection을 제공합니다.

// 특수한 형태의 Collcetion 제공
Collections.singletonMap(키, 값); // 싱글톤 맵
Collections.unmodifiableList(리스트); // 불변 리스트

// Collection을 다루는 메서드
Collections.sort(컬렉션 객체); // 컬렉션 정렬
Collections.reverse(리스트); // 리스트 뒤집기

---

🚃 List

리스트 자료 구조를 구현한 인터페이스입니다. 순서를 보장한다는 특징이 존재합니다.

대표적인 구현체는 ArrayList, LinkedList, Vector, Stack이 있습니다.

그림 2 : List의 구현체

이 중에서 Vector는 호환성을 위해서만 남아있는 레거시 코드(Legacy Code)입니다.

비슷한 이유로 Stack도 빼고 ArrayList와 LinkedList에 대해서 알아보겠습니다.

🚈 ArrayList

이름에서 예상할 수 있듯이 내부적으로 배열을 사용하는 리스트입니다.

그림 3 : 배열

내부적으로 어떻게 초기화되고 크기를 변경하는걸까요?

 

생성자로 만들게 되면 다음과 같이 초기화가 됩니다.

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 

이후 add()를 통해서 추가할 때마다 내부적으로 grow()를 호출해서 크기를 늘립니다.

배열의 크기는 다음과 같은 공식을 따르고 있습니다.

확장 크기 = 현재 크기 + Math.max(최소 성장치, 적정 성장치)

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

 

반대로 remove()를 통해서 삭제할 때마다 내부적으로 fashRemove()를 호출해서 크기를 줄입니다.

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

 

배열은 인덱스를 사용하므로 값을 찾을 때는 O(1) 만큼 걸립니다.

추가/삭제할 때는 새로운 배열로 복사하기 때문에 O(N) 만큼 걸립니다.

단, 순차적으로 추가/삭제한다면 O(1) 만큼 걸립니다.

🚟 LinkedList

ArrayList가 배열을 사용하는 단점을 극복하기 위해서 만들어졌습니다.

자바의 LinkedList는 이중 연결 리스트 구조를 사용하고 있습니다.

그림 4 : LinkedList의 구조

Deque 자료 구조와 성질이 매우 비슷한데, 내부적으로 상속하고 있습니다.

그림 5 : Deque 인터페이스를 상속받는 LinkedList

값을 찾을 때는 하나하나 확인해야 하므로 O(N) 만큼 걸립니다.

하지만 추가/삭제할 때는 단순하게 참조를 바꿔주면 되므로 O(1) 만큼 걸립니다.

👆 선택하기

추가/삭제가 빈번하다면 LinkedList, 자주 꺼낸다면 ArrayList를 사용하면 됩니다 😋

하지만 메모리 관점에서 LinkedList는 주소를 저장해서 더 많은 공간을 사용하고

ArrayList는 연속된 공간을 사용해서 낭비되는 공간이 없다는 점까지 고려해서 사용하시기 바랍니다.

---

🗺️ Map

키(key)와 값(value)으로 이루어진 한 쌍을 저장하는 자료구조입니다.

값은 중복이 존재하지만, 키는 중복이 존재할 수 없습니다. 그리고 순서를 보장하지 않습니다.

그림 6 : Map의 구현체

HashTable과의 비교는 이전 글에서 다루었습니다.

따라서 이번 글에서는 HashMap, TreeMap 그리고 LinkedHashMap에 대해서 알아보겠습니다.

🍟 HashMap

키의 중복을 Hash를 사용해서 해결하는 자료 구조입니다.

키와 값을 저장하는 Node 배열을 내부적으로 사용하고 있습니다.

이 외에 해시 충돌을 피하기 위해서 추가적인 공간을 사용하기도 합니다.

transient Node<K,V>[] table;

 

해시 함수로 생성된 값을 인덱스로 사용하기 때문에 모든 연산이 평균적으로 O(1) 만큼 걸립니다.

하지만 해시 충돌이 발생하는 최악의 경우 O(N) 만큼 걸릴 수도 있습니다.

🌲 TreeMap

트리를 사용하는 Map 자료 구조로, 키를 기준으로 정렬되어 있습니다.

사용자가 기준을 정의해서 정렬 순서를 조정할 수 있습니다.

private final Comparator<? super K> comparator; // 조정에 사용되는 Comparator

final int compare(Object k1, Object k2) { // 비교에 사용되는 메서드
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

Red-Black 트리를 사용합니다. 모든 연산이 평균적으로 O(logN) 만큼 걸립니다.

🚂 LinkedHashMap

HashMap과 내부적으로 동일하지만 순서를 보장하는 자료 구조입니다.

내부적으로 LinkedList를 사용하기 때문에 추가적인 메모리를 요구합니다.

그림 7 : LinkedHashMap의 구조

LinkedHashMap을 생성할 때 HashMap의 생성자를 호출합니다.

여기서 눈여겨봐야 할 것은 accessOrder입니다.

public LinkedHashMap() {
    super();
    accessOrder = false;
}

 

LinkedHashMap은 afterNodeInsertion(), afterNodeRemoval()로 내부 LinkedList를 관리합니다.

accessOrder를 true로 설정하면 어떤 현상이 나타날까요?

Map<Object, Object> linkedHashMap = new LinkedHashMap<>(3, 0.75F, true);

for (int i = 0; i < 3; i++) {
    linkedHashMap.put("key" + i, "value" + i);
}

linkedHashMap.get("key2");
linkedHashMap.forEach((key, value) -> System.out.println("key : " + key + " value : " + value));

우리의 예상과 다르게 입력 순서가 달라진 것을 확인할 수 있습니다. accessOrder는 어떤 것일까요?

그림 8 : 순서가 달라진 LinkedHashMap

 

크기와 accessOrder를 true로 설정하면 LRU 캐시를 구현하는 것과 동일합니다.

어떤 값에 꺼내오면 해당 값을 LinkedList 마지막으로 이동시킵니다.

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
                // accessOrder가 참이고 값이 마지막이 아니라면, 마지막으로 이동시킨다.            
    }
}

 

내부적으로 HashMap을 동일하게 사용하므로 모든 연산이 평균적으로 O(1) 만큼 걸립니다.

하지만 순서를 보장하기 위해서 추가적인 공간을 사용한다는 특징이 있습니다.

👆 선택하기

특별한 이유가 없다면 HashMap을 사용하는 게 좋습니다. 속도가 가장 빠르기 때문입니다.

하지만 데이터가 정렬된 상태로 있어야 하거나 범위 검색을 해야 한다면 TreeMap을 사용하고,

입력된 순서가 필요하거나 캐시를 만들 특별한 일이 존재한다면 LinkedHashMap을 사용하면 되겠습니다. 😋

---

☝️ Set

중복을 허용하지 않고 저장 순서가 유지되지 않는 자료 구조입니다.

자바에서 Set 자료 구조는 Map 자료 구조와 밀접한 관련이 있습니다.

그림 9 : Set의 구현체

LinkedHashSet이라는 구조도 있는데 LinkedHashMap과 거의 동일해서 나머지 두 개만 비교하겠습니다.

🍠 HashSet

해시를 사용해서 중복을 확인하는 Set 자료 구조입니다.

내부 구현은 HashMap과 동일합니다. 값은 dummy를 넣어서 사용합니다.

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

 

HashMap과 거의 동일하므로 모든 연산이 평균적으로 O(1) 만큼 걸립니다.

마찬가지로 해시 충돌이 발생하는 최악의 경우에는 O(N) 만큼 걸립니다.

🍃 TreeSet

트리를 사용하는 Set 자료 구조입니다.

내부적으로 TreeMap을 사용합니다. 값은 HashSet과 동일하게 dummy를 넣어서 사용합니다.

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public TreeSet() {
    this(new TreeMap<>());
}

 

TreeMap과 동일한 시간복잡도를 가집니다. 모든 연산이 평균적으로 O(logN) 만큼 걸립니다.

👆 선택하기

앞서 언급한 것처럼 Set은 Map과 밀접한 관련이 있습니다.

따라서, Map의 기준과 동일하게 특별한 이유가 없다면 HashSet을 쓰는 게 좋습니다.

하지만 데이터의 정렬 여부와 범위 검색까지 고려한다면 TreeSet을 사용하면 됩니다. 😋

---

😋 정리

• Java Collection Framework는 자료 구조의 집합이다.
• List은 순서를 보장하는 자료 구조이다.
  • 자주 검색 한다면 ArrrayList
  • 추가/삭제가 빈번하다면 LinkedList
• Map은 <Key, Value> 쌍을 저장하는 자료 구조이다.
  • 특별한 이유가 없다면 HashMap
  • 정렬된 데이터나 범위 검색을 해야 한다면 TreeMap
  • 입력 순서가 필요하거나 캐시로 만든다면 LinkedHashMap
• Set은 중복된 값이 없는 자료 구조. Map과 밀접한 관계이다.
  • 특별한 이유가 없다면 HashSet
  • 정렬된 데이터나 범위 검색을 해야한다면 TreeSet

---

😋 지극히 개인적인 블로그지만 댓글과 조언은 제 성장에 도움이 됩니다 😋