Week3(1/2) Collections
컬렉션
Last updated
컬렉션
Last updated
자바에서 데이터 구조(컬렉션)를 다루기 위한 표준화된 클래스 및 인터페이스의 모음입니다. 배열, 리스트, 스택, 큐, 해시맵 같은 데이터 구조를 효율적으로 사용할 수 있는 방법을 제공합니다.
JCF의 계층 구조는 여러 인터페이스와 그 인터페이스를 구현한 클래스들로 구성되어 있습니다.
Collection 인터페이스 JCF의 최상위 인터페이스로, List, Set, Queue같은 하위 인터페이스들이 이 인터페이스를 상속받습니다. 공통적으로Add, Remove, Size, Iterator 메서드가 있습니다.
List 인터페이스 순서가 있는 데이터의 집합을 나타냅니다. 중복을 허용, 인덱스를 통해 접근 가능
Set 인터페이스 중복을 허용하지 않는 데이터의 집합을 나타냅니다.
Queue 인터페이스 FIFO 방식으로 처리하는 컬렉션입니다.
Map 인터페이스 키:값 쌍으로 데이터를 저장하는 컬렉션입니다.
기타 인터페이스 SortedSet, NavigableSet, SortedMap, NavigableMap 등은 정렬된 순서를 보장하거나 탐색을 지원하는 추가 인터페이스입니다.
List 인터페이스는 순서가 있는 데이터 집합을 나타내며, 중복된 요소를 허용하고 인덱스를 통해 요소에 접근할 수 있는 자바 컬렉션의 핵심 인터페이스 중 하나입니다. 주요 구현체로는 ArrayList, LinkedList, Vector, Stack이 있습니다. ArrayList는 요소 접근이 빠르지만, 요소 추가/삭제가 빈번할 때는 LinkedList를 사용하는 것이 더 효율적입니다.
(Vector는 동기화된 자료구조이고, 상속받는 Stack도 동기화된 자료구조.) 코테에서는 Stack보다는 ArrayDeque가 성능이 더 좋습니다.
ArrayList는 자바에서 동적으로 크기를 조절할 수 있는 배열 기반의 List 구현체입니다. 내부적으로 배열을 사용해 데이터를 저장하며, 배열이 가득 차면 크기를 50%씩 늘려 새로운 배열을 할당하고, 기존 데이터를 복사합니다. 이는 인덱스를 통한 요소 접근이 빠른 장점이 있지만, 중간에서의 삽입/삭제 성능이 떨어질 수 있는 단점이 있습니다.
ArrayList는 기본적으로 크기가 10인 배열로 초기화되며, 배열의 크기가 초과되면 기존 크기의 50%를 더한 새로운 크기의 배열이 생성됩니다. 기존 배열의 요소는 System.arraycopy 메서드를 통해 새로운 배열로 복사되며, 이후 새로운 요소가 추가됩니다. 이 과정은 배열이 커질수록 복사 작업이 많아져 성능에 영향을 미칠 수 있으므로, 상황에 따라 초기 용량을 설정하는 것이 중요합니다.
LinkedList는 List와 Deque 인터페이스를 구현한 양방향 연결 리스트입니다. 각 요소는 노드로 저장되며, 노드는 데이터와 함께 이전 노드와 다음 노드를 가리키는 두 개의 참조를 가집니다. 이 구조 덕분에 요소의 추가와 삭제가 빠르게 이루어지지만, 인덱스 기반의 접근(탐색)은 첫 번째 노드부터 순차적으로 접근해야 하므로 시간이 오래 걸립니다. 또한, LinkedList는 각 노드에 두 개의 참조를 저장하므로 ArrayList에 비해 더 많은 메모리를 사용합니다.
ArrayList는 순차적으로 데이터를 저장하거나, 인덱스를 통해 데이터를 자주 조회해야 할 때 가장 적합합니다. 내부적으로 배열을 사용하므로, 인덱스 접근이 매우 빠르고, 메모리 효율성도 높습니다. 반면, LinkedList는 삽입과 삭제가 빈번하게 발생하는 상황에서 더 효율적입니다. 중간에 데이터를 삽입하거나 삭제하는 작업이 자주 필요할 때, 그리고 큐나 덱과 같은 자료 구조를 구현할 때 LinkedList를 사용하는 것이 적합합니다.
ArrayList와 Vector는 모두 배열 기반의 List 구현체지만, 주요 차이점은 동기화와 성장 방식에 있습니다. Vector는 동기화가 기본적으로 적용되어 있어, 다중 스레드 환경에서 안전하게 사용할 수 있지만, 단일 스레드 환경에서는 성능 저하가 있을 수 있습니다. ArrayList는 동기화되지 않아 단일 스레드 환경에서 더 빠르게 동작하며, 다중 스레드 환경에서는 별도의 동기화가 필요합니다. 또한, Vector는 크기를 두 배로 늘리는 반면, ArrayList는 크기를 50%씩 늘립니다. 현재는 ArrayList가 더 널리 사용됩니다.
스택(Stack)은 LIFO(Last In, First Out) 방식으로 동작하는 자료구조로, 가장 나중에 추가된 요소가 가장 먼저 제거됩니다. 스택은 함수 호출의 순서를 관리하거나, 괄호의 유효성을 검사하는 알고리즘에서 자주 사용됩니다. 큐(Queue)는 FIFO(First In, First Out) 방식으로 동작하는 자료구조로, 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 큐는 작업 대기열이나 너비 우선 탐색(BFS)에서 자주 사용됩니다. 자바에서는 스택을 구현할 때 Stack 클래스 대신 Deque 인터페이스(ArrayDeque, LinkedList)를 사용하는 것이 권장됩니다.
Set은 중복된 요소를 허용하지 않는 데이터 집합을 나타내는 자바 컬렉션 프레임워크의 인터페이스입니다. 주요 구현 클래스에는 HashSet, LinkedHashSet, TreeSet이 있습니다. HashSet은 요소의 순서를 보장하지 않으며 빠른 조회와 삽입 성능을 제공합니다. LinkedHashSet은 삽입 순서를 유지하며, TreeSet은 요소를 정렬된 순서로 저장합니다. 각각의 구현체는 사용 시나리오에 따라 선택될 수 있습니다.
HashSet - 빠른 조회, 성능, 정렬X
TreeSet - 정렬 (우선순위큐와의 차이는 중복허용과, 모든 요소 정렬 / 하나의 원소만 정렬)
LinkedHashSet - 삽입 순서를 정한다.
Set에서 중복 요소를 걸러내는 방식은 구현체에 따라 다릅니다. HashSet은 hashCode()와 equals() 메서드를 사용하여 중복을 확인합니다. 먼저 요소의 해시 코드를 통해 저장 위치를 결정한 후, equals()로 실제 값이 동일한지 비교하여 중복을 걸러냅니다.
Map은 키-값 쌍으로 데이터를 저장하는 자바의 자료구조입니다. 각 키는 고유하며, 이를 통해 매핑된 값을 조회하거나 수정할 수 있습니다. 주요 구현체로는 HashMap, LinkedHashMap, TreeMap이 있습니다. HashMap은 해시 테이블을 사용하여 빠른 접근을 제공하지만 순서를 보장하지 않습니다. LinkedHashMap은 삽입 순서를 유지하며, TreeMap은 키를 정렬된 상태로 유지합니다.
HashMap은 해시 테이블 구조를 사용하여 키-값 쌍을 저장하며, 키의 동일 여부를 판단하기 위해 hashCode()와 equals() 메서드를 사용합니다. 저장할 때, 키의 hashCode()를 통해 해시 코드가 생성되고, 이 해시 코드를 사용해 데이터를 저장할 버킷을 결정합니다. 동일한 버킷에 여러 키가 존재할 경우, equals() 메서드를 통해 키가 동일한지 확인합니다. 만약 동일한 키가 존재하면, 기존 값을 대체합니다.
HashMap의 평균적인 시간 복잡도는 O(1)입니다. 그러나 최악의 경우, 해시 충돌이 많이 발생하면 시간 복잡도는 O(n)까지 증가할 수 있습니다.
HashMap은 키-값 쌍을 저장할 때, 해시 함수를 사용하여 특정 버킷에 키를 매핑합니다. 그러나 여러 키가 동일한 해시 값을 가질 수 있는데, 이를 해시 충돌이라고 합니다. HashMap에서 해시 충돌이 발생하면 같은 버킷에 여러 개의 키-값 쌍이 저장됩니다.
충돌 해결 방식: Java의 HashMap에서는 해시 충돌을 해결하기 위해 버킷 내에서 체이닝(Chaining) 방식과 트리화(Treeing) 방식을 사용합니다.
체이닝(Chaining): 충돌이 발생한 경우, 해당 버킷 내에서 충돌한 키-값 쌍들을 연결 리스트로 관리합니다.
트리화(Treeing): 버킷 내 요소 수가 일정 수(기본적으로 8)를 초과하면, 연결 리스트를 레드-블랙 트리로 변환하여 시간 복잡도를 줄입니다.
최악의 시간 복잡도: 만약 모든 키가 동일한 해시 값을 가지게 되어, 모든 요소가 동일한 버킷에 들어가게 되면, 체이닝 방식에서는 이 버킷의 요소들이 연결 리스트로 연결되며, 탐색, 삽입, 삭제의 시간 복잡도는 O(n)이 됩니다.
이 경우, 해시맵은 사실상 연결 리스트와 유사하게 동작하게 되어, 탐색이나 삽입/삭제 연산의 시간이 O(n)으로 증가합니다.
그러나 트리화가 발생한 경우, 최악의 시간 복잡도는 O(log n)이 됩니다. 이는 레드-블랙 트리의 특성상 균형 잡힌 트리 구조를 유지하기 때문에, 키의 수가 n일 때 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)으로 줄어듭니다.
따라서, 최악의 경우 HashMap의 시간 복잡도는 다음과 같습니다:
탐색, 삽입, 삭제의 최악의 경우: O(n) (체이닝 방식), O(log n) (트리화된 경우)
이와 같은 최악의 경우는 해시 함수가 제대로 작동하지 않거나, 해시 충돌이 극도로 많이 발생할 때 나타날 수 있습니다. 일반적으로 해시 충돌이 적고, 해시 함수가 균일하게 분포된다면 HashMap의 평균 시간 복잡도는 O(1)입니다.
Map 인터페이스는 Collection 인터페이스를 상속받지 않습니다. 이는 두 인터페이스가 서로 다른 개념을 표현하기 때문입니다. Collection은 단일 요소의 집합을 관리하는 반면, Map은 키-값 쌍의 집합을 관리합니다. Collection의 메서드는 단일 요소를 추가하거나 제거하는 데 중점을 두지만, Map은 키와 값을 매핑하고 관리하는 데 중점을 둡니다.
Iterable과 Iterator는 자바에서 컬렉션을 순회하기 위해 사용되는 인터페이스입니다. Iterable은 컬렉션이 반복 가능하다는 것을 나타내며, iterator() 메서드를 통해 Iterator 객체를 제공합니다.
Collection은 자바 컬렉션 프레임워크에서 여러 요소의 집합을 나타내는 기본 인터페이스로, List, Set, Queue와 같은 컬렉션 인터페이스들이 이를 상속받습니다. 반면, Collections는 컬렉션을 조작하기 위한 유틸리티 클래스이며, 컬렉션을 정렬, 검색, 변환하는 등의 다양한 정적 메서드를 제공합니다. 즉, Collection은 컬렉션의 인터페이스를 의미하고, Collections는 그 컬렉션을 다루기 위한 도구를 제공합니다.
