컬렉션 프레임워크

박기범·2022년 1월 1일

단기간 Java 정복

목록 보기

2/3

Java에서 지원하는 컬렉션 프레임워크를 각 자료구조의 특성을 중심으로 정리한다.

컬렉션 프레임워크?

List

List 인터페이스는 자료의 순서가 존재하고 자료의 중복을 허용하는 컬렉션이다.
Java의 컬렉션 프레임워크에서 List 인터페이스를 제공해주는 자료구조는 총 3가지가 있는데, 각각 ArrayList(배열), Vector, Linked list(링크드리스트)가 그것이다. 우선, List 인터페이스의 메소드는 다음과 같다.

1. ArrayList

ArrayList는 Vector를 개선한것으로, 제공 기능이 Vector와 동일하다.
배열은 원래 그 크기가 고정적이다. 그리고 이는 Java에서도 동일한 대원칙이다.

public class ImsiClass{
    public static void main(String arg[]){
    	int arr = new int[10];
        int arr1[10];
    }
}

따라서, 위 코드와 같이 배열을 특정 크기로 초기화 하면 별도의 메소드를 사용하지 않는이상, 데이터의 저장(참조 메모리 주소의 저장은 생각하지 않는다.)에 40 바이트가 할당된다. 이 이상의 데이터는 저장할 수 없다.

그런데 컬렉션 프레임워크의 ArrayList를 이용하면, 이런 부분을 개선해준다. 배열의 용량이 부족할 시, 동적으로 늘릴수 있게 된다.

List 인터페이스의 메소드를 활용하여 꽉 찬 ArrayList에 데이터를 추가하면 자동으로 배열의 크기가 증가하고 아이템이 추가된다. 다만, 이 배열이 추가되는 과정은 기존의 데이터를 모두 복사하고, 크기를 늘린 새로운 배열에 복사한 데이터를 집어넣는 방식이기 때문에 이러한 과정에서 오버헤드가 발생한다. 그리고 배열의 크기를 증가시키는 기준은, 기존 배열 크기의 절반만큼을 더한것이다. 이는 ArrayList의 구현체를 직접 살펴보면 알 수 있다.

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 이 과정에서 기존 크기를 오른쪽으로 1칸 시프트하므로 절반 크기를 기존 크기에 더해주는 꼴이 된다.
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

그리고 ArrayList는 아이템을 추가하거나 삭제할 때도 배열의 전체복사가 일어날 수 있다. 만약 배열의 끝에서부터 데이터를 삽입, 삭제하는 순차 조작이 아니고 배열의 중간에서부터 데이터를 조작한다면, 그 데이터 이후 인덱스의 데이터들을 모두 한칸씩 밀거나 당겨주어야 하기 때문에 이 과정에서 배열을 복사하게 된다.

배열에서 remove 메소드를 이용해 데이터를 삭제하고 나면 해당 위치에 명시적으로 NULL값을 넣게되는데, 이는 자바 GC의 대상이 되어 특정한 타이밍에 메모리를 반환하게 된다고 한다.

2. LinkedList

앞선 ArrayList에서 데이터의 삽입, 삭제시와 배열 크기 증가시에 일어나는 비효율적인 연산을 볼 수 있었다. LinkedList는 이러한 문제점을 일정부분 해결해준다.

Java의 LinkedList는 이중 연결 리스트로 구현되어 있는데, 그 모식도는 다음과 같다.

하나의 노드가 자신의 앞과 뒤에 오는 노드의 메모리 참조 주소를 갖고있고, 자신의 값 또한 갖고있다. 이 때, 특정 노드를 선택하여 삭제하면 해당 노드를 지우고 그 노드의 양 옆에 있는 노드가 가진 메모리 주소만 수정해주면 된다. 삽입시에도 마찬가지다.

즉, 비순차적인 데이터의 삽입과 삭제가 일어날 경우 LinkedList가 ArrayList에 비해 더 좋은 효율을 가진다.

다만 ArrayList는 존재하는 순서에 대해 index를 이용해서 곧바로 데이터에 접근할 수 있지만, LinkedList는 메모리 주소를 이용해 순회하며 해당 데이터에 접근해야한다는 단점이 있다.

Set

Set은 데이터의 순서를 보장하지 않고 중복도 허용하지 않는 자료구조 인터페이스이다. 이 인터페이스의 메소드는 다음과 같다. 기본적으로 collection 인터페이스의 메소드와 동일하다.

다만 Set은 집합과 관련된 메소드를 추가적으로 지원한다.

Set 인터페이스를 구현한 구현체는 Hashset과 Treeset이 존재한다.

1. Hashset

Hashset은 Set 인터페이스를 구현한 만큼 데이터의 순서가 저장되지 않고, 중복 또한 허용하지 않는다. 이때, 중복 검사를 위해 hashcode와 equals라는 메소드를 이용하게 된다. 즉, Hashset 자료구조에 임의의 객체를 저장하기 위해서는 hashcode, equals 메소드가 해당 객체에 오버라이딩 되어있어야 한다.

다만, 동일 객체에 대해서 hashcode를 호출할때는 그 반환 값이 항상 같아야하며, equals 메소드를 호출하여 true 값이 나오는 같은 객체의 경우 hashcode의 반환값도 같아야한다는 제약 조건이 있다. (equals 메소드의 호출 결과가 false이지만 hashcode가 동일한 경우는 허용한다.)

2. Treeset

Treeset은 이진 검색 트리의 자료구조 형태로 구현된다. 즉, 각 노드가 정렬된 상태를 유지하므로 범위검색과 정렬시 Hashset에 비해 유리하다. 하지만 데이터를 삽입하거나 제거할 때 트리가 재배치되어야 하므로 오버헤드가 발생하여 Hashset에 비해 성능이 낮다.

범위검색과 정렬에 유리한 만큼, Treeset만이 가지는 메소드들이 있다. 따라서, 이에 대한 부분을 정리하고 넘어간다.

Map

Map 인터페이스는 특정 데이터를 저장할 때 (key, value)의 한 쌍을 저장하게 된다. 이 과정에서 데이터의 순서는 저장하지 않으며, 데이터의 중복은 value에 대해서만 허용한다.

Set과 동일하게 Map 인터페이스에도 Hashmap과 Treemap이 존재한다.

1. Hashmap

해싱 기법을 이용하여 데이터를 저장한다. 즉, 특정 데이터의 조회 속도가 빠르다. 키를 이용하여 해쉬 코드를 생성해내고, 해쉬코드에 해당하는 링크드 리스트를 해쉬 테이블에서 조회한다. 그리고 그 링크드리스트에서 조회 시도한 키와 동일한 데이터를 찾는다. (같은 키에 대해서 항상 동일한 해쉬 코드를 반환해야한다.)

2. Treemap

Hashmap과 달리 트리 자료구조를 이용하여 데이터를 저장한다. Treeset의 경우와 동일하게, 범위검색과 정렬의 경우 Hashmap에 비해 유리하다. 다만, 단일 데이터 검색은 Hashmap이 더 빠르다. 이때 트리 자료구조를 구성하기 위해 노드를 정렬할 때는 키값을 기준으로 정렬하고 노드를 배치한다.