[자료 구조] 자바 컬렉션(Collection)에 대해 알아보자 - Java

⏳ 들어가며 -  컬렉션(Collection)이란?

자바에서 컬렉션 프레임워크는 데이터를 저장,관리 및 조작하기 위한 자료구조의 집합을 말합니다.
컬렉션은 자바의 java.util 패키지에 포함되어 있습니다.

 

⏳ 자바 컬렉션 프레임워크 주요 인터페이스

컬렉션 인터페이스는 List, Queue, Set 3가지의 상위 인터페이스로 분류된다.
Map은 컬렉션에 포함되지 않지만 Collecion으로 보통 분류하는 편입니다.

 

⏳ List 인터페이스

리스트는 순서가 있는 데이터의 집합으로, 데이터의 중복을 허용합니다.

ArrayList

- 데이터에 대한 인덱스를 가지고 있어 조회 기능에 성능이 뛰어납니다.
- 가변크기의 배열로 구현되며 빈공간이 생기면 요소 위치가 자동 이동됩니다.
- List 컬렉션을 여러 스레드에서 공유해야 한다면 Thread safe 하지 않습니다.

LinkedList

- 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정하면 되기에 유용합니다.
- 스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰입니다.

Vector

- 과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화 처리가 일어나 비교적 성능이 좋지 않고 무거워 잘 쓰이지않습니다.
- 기존 코드와의 호환을 위해 아직도 남아 있습니다. 하지만 기존에 사용하던 컬렉션 클래스를 사용하는 것보다는 새로 추가된 ArrayList나 HashMap 클래스를 사용하는 것이 성능 면에서도 더 나은 결과를 얻을 수 있습니다.

Copy On Write ArrayList

- ArrayList를 구현한 클래스
- 내부를 변경하는 작업은 항상 깨끗한 복사본을 만들어서 수행하도록 구현되어 있습니다.
- 내부의 배열은 절대 변경할 수 없으므로 순회할 때 락이 필요 없어서 속도면에서 매우 빠릅니다.
- 데이터 수정이나 삭제등의 용도로 쓰일 경우에는 속도가 느려지기 때문에 주로 순회가 일어나는 용도로 사용합니다.
- ArrayList는 스레드에 안전하게 설계되지 않았기 때문에 자바 1.5 이전에는 synchronized와 함께 사용하여 동시성 제어를 해주었습니다. 그러나 각각 스레드가 필요 이상으로 작동하여 성능적인 문제나 교착문제로 안전한 스레드 처리를 위해 CopyOnwriteArrayList가 등장했습니다.

 

⏳Queue 인터페이스

큐는 일반적으로 먼저 들어온 데이터가 먼저 처리되는 구조인 FIFO(First-In-First-Out) 원칙을 따릅니다.
주로 작업 스케줄링, 탐색, 패킷, 멀티스레드 환경의 작업처리 등 다양한 상황에서 활용됩니다.

일상 생활에서 주문 처리를 할때 주문이 먼저 들어온 순서대로 처리되고, 공평하게 주문이 배달되는 구조를 유지하는 것처럼,
큐는 순서를 관리하고 조직화해서 공정한 처리를 가능케 합니다.

Priority Queue

- 우선 순위에 따라 객체를 처리해야 할 때 사용됩니다
- 우선 순위에 따라 먼저 처리해야할 것이 있다면 우선 순위 힙을 기반으로 처리합니다.

 

⏳Queue 인터페이스

큐 데이터 구조의 변형입니다.
양방향 큐라고도 불리고 양쪽 끝에서 요소를 추가하고 제거할 수 있는 구조입니다.

Array Deque

- 크기가 조절되는 배열이고 양쪽 끝에서 요소를 추가하고 제거하는 구조입니다.

 

⏳Set 인터페이스

Set는 순서를 유지하지 않는 데이터의 집합이지만 데이터의 중복을 허용하지 않습니다.
(LinkedHashSet은 순서를 보장합니다.)

Hash Set

- 가장 빠른 임의 접근 속도
- 키는 중복될 수 없으며, 순서를 보장하지 않습니다.
- 일반적으로 빠른 검색 속도를 제공하지만, 순서를 예측할 수 없습니다.
- Thread safe 하지 않습니다.

Tree Set

- 정렬방법을 지정할 수 있습니다.(기본- 오름차순 정렬)
- Thread safe 하지 않습니다.

Linked Hash Set

- 입력된 순서대로 저장합니다.
- Thread safe 하지 않습니다.

⏳Map 인터페이스

Map은 자바 프레임워크에서 컬렉션과 유사형 형태의 자료구조입니다.
엄밀하게 Map은 컬렉션의 일종이긴하지만 인터페이스를 직접 구현한것은 아닙니다.
Map은 키-값의 쌍으로 데이터를 저장하고 관리하는 자료구조입니다.

일상 생활에서 비슷한 예제로 주소록은 사람들의 이름과 전화번호를 매핑하는 역할을 합니다. 여기서 이름은 키(key)이며 전화번호는 값(Value)입니다.

 

Hash Table

- 오래된 자바 컬렉션 클래스 중 하나로, 이제는 거의 사용되지 않는 추세입니다. 대신 HashMap 사용을 권장합니다.
- 해시맵과 비슷한 원리로 동작하지만, 동기화를 지원하여 멀티스레드 환경에서 안전하게 사용할 수 있습니다.
- 동기화로 인해 성능이 저하되며, 자바5이후에는 ConcurrentHashMap 등의 동시성을 지원하는 맵 클레스들이 등장하면서 대체되는 경향이 있습니다.

Hash Map

- 가장 일반적으로 사용되는 맵 구현 클래스
- 키-값 쌍을 해시 테이블에 저장하며, 해시 함수를 사용하여 데이터를 빠르게 검색합니다.
- 키는 중복될 수 없으며, 순서를 보장하지 않습니다.
- 일반적으로 빠른 검색 속도를 제공하지만, 순서가 중요한 경우에는 사용하지 않는 것이 좋습니다.

Linked Hash Map

- 키-값 쌍을 해시 테이블에 저장하면서 입력된 순서를 유지합니다.
- 해시맵의 기능을 유지하면서도 순서를 보장받을 수 있는 특징을 가집니다.
- 내부적으로는 이중 연결 리스트를 사용하여 순서를 유지합니다. 

Tree Map

- 키를 기반으로 정렬된 순서로 데이터를 저장하는 맵입니다.
- 이진 검색 트리(binary search tree)를 사용하여 데이터를 저장하므로, 데이터를 삽입하거나 검색할 때 O(log n)시간이 소요됩니다.
- 키의 순서또는 사용자 지정 비교자에 따라 정렬 됩니다.

⏳정리하며

ArrayList는 포인터 구조?

ArrayList가 일반적인 배열과 같은 단방향 포인터 구조 라고 알고있었지만, 공부해보니
ArrayList는 배열을 List 프레임워크에 맞춰서 쓸 수 있게 만들어둔 자료구조 라는것을 알게 되었고 ArrayList를 파보았습니다.

 

ArrayList를 타고 들어가면 List 인터페이스를 확장합니다.

내부적으로 이곳에 직렬화를 제외하는 배열 형태의 자료를 담아둡니다.

add()함수에서 배열에 요소가 추가가 될때 길이를 늘리기 위해 grow() 함수가 실행되는데 늘려진 배열크기에 기존 배열을 전부 복사해넣는식으로 구현되어 있습니다.

ArraysSupport.newLength() 함수가 최소 성장량과 선호 성장량을 고려하여 배열의 크기를 늘리는데,
내부적으로 oldCapacity >> 1 에서 쓰인 시프트 연산을 통해 2로 나누는 효과를 가집니다.
newLength() 기존 배열의 크기 나누기 시프트된 배열크기의 절반만큼을 선호 성장량으로 사용하게 됩니다.
결국 grow() 함수는 배열의 기존 크기를 1.5배로 늘립니다. 

결론적으로 ArrayList가 List 프레임워크에 맞춰서 쓸 수 있게 만들어둔 자료구조라는 사실을 알게되었습니다.

 

Iterable & Generic 다음 기회에 ..

컬렉션을 파보니 아래와 같이 Iterable<E>을 확장하여 구현한다는 것을 알게 되었습니다.
Collection을 구현한 클래스의 ArrayList, HashSet, LinkedList 등은 모두 iterator() 메서드를 가지고 있습니다.
이러한 클래스들은 내부적으로 컬렉션에 저장된 요소들을 순회할 수 있는 반복자(iterator)를 반환하여 개발자가 컬렉션을 다루기 편하게 도와준다는 것을 알게되었습니다.

<E>는 Java에서 제네릭(Generic)을 사용할 때 많이 보이는 표현 중 하나인데 제네릭은 클래스나 인터페이스를 정의할 때 타입(Type)을 파라미터화하여 코드의 재사용성과 안정성을 높이는 방법을 제공합니다.

<E>는 제네릭에서 타입 파라미터(Type Parameter)를 나타내는데, 이는 실제 사용될 떄 실제 타입으로 대체됩니다.
제네릭의 경우에 <T>, <K, V>, <N>, <R> 등과같이 쓰이는데 다음기회에 다뤄보면 좋겠다고 생각했습니다. 

마지막으로 여러가지 파서 들어가다보니, 컬렉션 프레임워크 설계와 구현에 큰 기여를 한 "Effective Java" 저자 "조슈아 블로흐(Joshua Bloch)", "닐 게이퍼(Neal Gafter)" 형님에게 감사드리며 잘못되거나 틀린부분으로 피드백을 주신 모든분들께 감사드리며 글을 마무리해보도록 하겠습니다.