Java Collections Framework (JCF)
Java Collections Framework(JCF)는 데이터를 효율적으로 저장하고 처리할 수 있도록 자료구조와 알고리즘을 표준화한 설계도입니다.
1. JCF 개요
Collections는 다수의 데이터를 저장하고 관리하는 자료구조이고,
Framework는 일관된 설계에 따라 미리 정의된 클래스와 인터페이스의 집합으로, 개발자가 표준화된 방식으로 특정 기능을 구현할 수 있게 돕습니다.
Java Collections Framework(JCF)는 List, Set, Map 등 다양한 인터페이스와 구현체를 제공하여 개발자가 직접 자료구조를 구현할 필요 없이 일관된 방식으로 컬렉션을 사용하고 관리할 수 있도록 돕습니다.
이를 통해 코드 재사용성, 성능 최적화, 유지보수 용이성을 제공합니다.
2. JCF의 계층 구조
JCF의 계층 구조는 기본적으로 Collection 인터페이스를 중심으로 List, Set, Queue, / Map으로 분류되며, 각각의 인터페이스에 다양한 구현체가 있습니다.
-
Collection 인터페이스: 데이터의 집합을 표현하는 최상위 인터페이스로, 하위 인터페이스로 List, Set, Queue가 있습니다.
- List 인터페이스: 순서가 있는 데이터 집합으로 중복을 허용합니다. 주요 구현체로 ArrayList, LinkedList 등이 있습니다.
- Set 인터페이스: 순서가 없고, 중복을 허용하지 않는 데이터 집합입니다. 주요 구현체로 HashSet, TreeSet 등이 있습니다.
- Queue 인터페이스: FIFO(First In, First Out) 구조를 가지며 주로 데이터의 순차적인 처리를 위해 사용됩니다. 주요 구현체로 LinkedList, PriorityQueue 등이 있습니다.
-
Map 인터페이스: 키-값 쌍으로 데이터를 저장하며, 키는 중복을 허용하지 않습니다. 주요 구현체로 HashMap, TreeMap 등이 있습니다.
예를 들어, Collection 인터페이스를 통해 학생들의 이름을 관리하는 경우 List 인터페이스를 사용하여 순서대로 저장할 수 있습니다. 또는 학생 고유 번호(ID)를 관리할 때는 Set 인터페이스를 통해 중복 없이 저장할 수 있습니다.
다시 말해, JCF의 계층 구조는 각 자료 구조의 특성을 이해하고, List, Set, Queue, Map 등 요구 사항에 맞는 인터페이스와 구현체를 선택하여 사용하도록 구성되어 있습니다.
List 인터페이스와 구현체
List는 데이터의 순서를 보장하며 중복을 허용하는 인터페이스입니다. 대표적인 구현체로는 ArrayList와 LinkedList가 있습니다.
List 인터페이스는 순서가 있는 데이터 집합을 다루며, 각 요소는 인덱스를 통해 접근할 수 있습니다. 주요 구현체로는 ArrayList (동적 배열 기반), LinkedList (연결 리스트 기반), 그리고 Vector (스레드 안전한 동적 배열 기반) 등이 있습니다.
예를 들어, 학생들의 출석부를 관리할 때 ArrayList를 사용하면 출석 순서대로 저장하고 관리할 수 있습니다. 그리고 특정 학생의 출석 순서를 찾을 때 인덱스로 빠르게 접근할 수 있습니다.
다시 말해, List는 순서가 있는 데이터를 관리할 때 적합하며, 데이터의 순차적 저장과 검색을 위한 다양한 구현체를 제공합니다.
1. ArrayList
ArrayList는 배열 기반의 List 구현체로, 순서를 보장하며 중복을 허용하는 인터페이스입니다.
ArrayList는 빠른 인덱스 접근이 가능하나, 중간 삽입 및 삭제 시 성능 저하가 발생할 수 있습니다.
데이터가 추가되면 내부적으로 저장 공간이 부족할 경우 일정 크기만큼 배열을 늘려주며 동적으로 크기를 조정합니다. 기존의 약 1.5배로 늘립니다.
newCapacity = oldCapacity + (oldCapacity >> 1);ArrayList는 순서가 있는 데이터 저장 및 빠른 인덱스 접근이 필요할 때 유용합니다. 다만 데이터 삽입 및 삭제 빈도가 높은 경우에는 성능 문제가 발생할 수 있습니다.
2. LinkedList
LinkedList는 연결 리스트 기반의 List 구현체로, 요소 간의 연결을 통해 데이터를 저장합니다.
LinkedList는 각 요소가 다음 요소의 주소를 참조하는 노드(Node) 구조를 가집니다. 따라서 데이터 삽입 및 삭제 시 기존 요소를 옮길 필요가 없기 때문에 빠르게 수행할 수 있습니다. 하지만 인덱스로 접근 시 첫 요소부터 순차적으로 탐색해야 하므로 속도가 느립니다.
예를 들어, 학생 명단에서 중간에 새로운 학생을 추가하거나 특정 학생을 삭제해야 할 때 LinkedList를 사용하면 빠르게 삽입 및 삭제 작업을 수행할 수 있습니다.
다시 말해, LinkedList는 데이터의 삽입/삭제가 빈번한 경우 유리하며, 인덱스 접근이 필요하지 않은 경우에 적합한 자료 구조입니다.
3. ArrayList vs LinkedList
ArrayList는 빠른 인덱스 접근이 필요할 때 유리하고, LinkedList는 빈번한 삽입/삭제가 필요할 때 유리합니다.
- ArrayList: 인덱스 기반 접근이 빠르며, 중간 데이터 삽입/삭제 시 배열 이동이 필요하므로 느립니다.
- LinkedList: 빈번한 삽입/삭제에 유리하지만, 순차 접근만 가능하여 인덱스 접근이 느립니다.
예를 들어, 수업 출석부처럼 순서가 중요한 리스트를 관리할 때는 ArrayList를, 대기열처럼 중간 삽입과 삭제가 자주 발생하는 경우에는 LinkedList를 사용합니다.
다시 말해, ArrayList는 인덱스 접근이 필요하고 순서가 중요한 경우에, LinkedList는 빈번한 삽입과 삭제가 필요한 경우에 적합합니다.
4.Vector
Vector는 스레드 안전하게 동기화된 List 구현체입니다. (ArrayList는 동기화되지 않았다.)
Vector는 동기화가 적용되어 멀티스레드 환경에서 안전합니다. 그러나 동기화 처리로 인해 Vector는 단일 스레드 환경에서 성능이 낮아질 수 있습니다. (ArrayList는 멀티스레드 환경에서 안전하지 않다.)
하지만, 요즘은 Vector 클래스를 거의 사용하지 않는 편입니다. Vector는 내부 모든 메서드가 동기화 처리로 인해 성능이 저하될 수 있습니다.
멀티스레드 환경에서 스레드 안전한 컬렉션이 필요할 경우, Collections.synchronizedList 메서드를 통해 동기화된 ArrayList를 사용하거나, Java 5부터 제공된 CopyOnWriteArrayList와 같은 클래스가 더 효율적이고 적합한 선택으로 자리 잡았습니다.
Stack과 Queue
Stack과 Queue는 각각 LIFO, FIFO 구조로 데이터를 관리하는 자료 구조입니다.
-
Stack: Last-In-First-Out (LIFO) 구조로, 나중에 추가된 요소가 먼저 제거됩니다.
Stack은 깊이 우선 탐색(DFS)에서 자주 사용됩니다. DFS는 루트 노드에서 시작하여 가능한 깊이까지 한 방향으로 내려간 뒤, 더 이상 탐색할 곳이 없으면 되돌아가 다른 방향으로 탐색을 진행합니다. 이 과정은 재귀 또는 스택을 활용하여 구현할 수 있습니다.
주요 활용 사례: 경로 탐색, 퍼즐 풀이, 순열 및 조합 생성 등. -
Queue: First-In-First-Out (FIFO) 구조로, 먼저 추가된 요소가 먼저 제거됩니다.
Queue는 너비 우선 탐색(BFS)에서 주로 사용됩니다. BFS는 루트 노드에서 시작하여 인접 노드를 모두 탐색한 뒤, 다음 단계로 넘어가면서 탐색을 이어나갑니다. 이 과정은 큐를 활용하여 구현됩니다.
주요 활용 사례: 최단 경로 탐색, 네트워크 탐색 등.
Set과 구현 클래스
Set은 중복을 허용하지 않는 데이터 집합으로, 대표적인 구현체로는 HashSet, TreeSet이 있습니다.
1. HashSet
HashSet은 해시 기반 저장 방식을 사용하며, hashCode()와 equals() 메서드를 사용하여 중복 여부를 판단합니다.
해시 기반 저장 방식으로 빠른 접근을 제공한다.
-
hashCode() 메서드: 요소가 추가될 때, 먼저 hashCode() 메서드를 호출하여 해시 값을 계산합니다. 이 해시 값이 동일한 경우, 같은 해시 버킷에 저장됩니다.
-
equals() 메서드: 해시 값이 같더라도 실제로 동일한 객체인지 확인하기 위해 equals() 메서드를 호출합니다. equals() 메서드가 true를 반환하면 동일한 객체로 간주하여 중복을 제거하고, 새로운 요소를 추가하지 않습니다.
즉, HashSet에서는 hashCode()가 같고 equals()도 true를 반환하는 경우 중복으로 간주하여 요소를 추가하지 않습니다.
2. TreeSet
TreeSet은 이진 검색 트리 구조를 사용하며, 정렬 기준을 통해 중복 여부를 판단합니다.
-
정렬 기준: TreeSet은 저장된 요소들이 자동으로 정렬됩니다. 기본적으로 요소가 Comparable 인터페이스를 구현한 경우 compareTo() 메서드를 통해 정렬합니다.
-
중복 판단 기준: 새로운 요소를 추가할 때, 기존 요소와 compareTo() 메서드를 통해 비교하여 중복 여부를 결정합니다.
- 두 요소를 비교한 결과가 0이면 동일한 값으로 간주하여 새로운 요소를 추가하지 않습니다.
따라서, TreeSet은 정렬을 위한 비교 기준(compareTo)이 동일한 경우 중복으로 간주하여 추가를 허용하지 않습니다.
Map과 구현 클래스
Map은 키-값 쌍으로 데이터를 저장하는 인터페이스로, 대표적인 구현체로는 HashMap과 TreeMap이 있습니다.
Map은 각 키마다 하나의 값을 매핑하며, 키는 중복을 허용하지 않지만 값은 중복될 수 있습니다. HashMap은 빠른 접근을 위해 해시 기반 저장 방식을 사용하고, TreeMap은 키의 정렬 순서를 유지합니다.
예를 들어, 학생 ID와 성적을 HashMap에 저장하여 ID를 통해 빠르게 성적을 조회할 수 있습니다. TreeMap을 사용하면 ID 순서대로 정렬된 상태로 저장할 수 있습니다.
다시 말해, Map은 키와 값 쌍을 통해 데이터를 관리하며, HashMap은 빠른 데이터 접근에, TreeMap은 정렬된 데이터 관리에 적합합니다.
1. HashMap의 동작 원리
HashMap은 키의 해시 코드를 기반으로 데이터를 저장하며, 충돌 발생 시에는 연결 리스트(Linked list) 또는 트리 구조를 사용하여 충돌을 해결합니다.
HashMap은 해시 함수를 사용하여 각 키의 해시 코드를 계산하고, 해당 해시 코드에 따라 특정 버킷에 값을 저장합니다. 만약 해시 충돌이 발생하면 해당 버킷에 연결 리스트나 트리 구조로 추가적인 데이터를 저장하여 충돌을 해결합니다. Java 8 이후, 충돌이 많은 경우(버킷에 저장된 연결 리스트의 길이가 8개 이상, 해시 테이블의 전체 크기가 64 이상)에는 성능을 개선하기 위해 트리 구조로 변환됩니다.
연결 리스트를 사용해 동일한 버킷에 여러 요소를 저장합니다. 즉, 각 버킷은 연결 리스트로 구현되어 있으며, 같은 해시 코드를 갖는 요소들은 연결 리스트의 노드로 추가됩니다. (하나의 노드에 키,값,해시코드,다음노드에 대한 참조값이 저장되어있다.)
2. HashMap의 최악의 시간 복잡도
HashMap의 최악의 경우 시간 복잡도는 O(n)입니다. 이는 해시 충돌이 많이 발생하여 모든 요소가 동일한 버킷에 저장되는 경우 발생합니다.
HashMap은 평균적으로 O(1)의 시간 복잡도를 가지지만, 해시 충돌이 많이 발생하여 하나의 버킷에 모든 요소가 저장될 경우, 각 요소를 탐색하기 위해 순차적으로 접근해야 하므로 O(n)의 시간 복잡도가 됩니다.
예를 들어, 모든 학생의 ID가 같은 해시 코드를 가지는 경우, HashMap의 성능은 연결 리스트의 순차 검색과 같아져 검색 속도가 느려질 수 있습니다.
Java 8 이후로는 충돌 시 트리 구조를 사용하여 최악의 경우 성능을 O(log n)으로 개선했습니다.
