[Java] JCF(Java Collection Framework)

Java 뿐 아니라 모든 언어마다 개발하는 과정에서 자료구조는 필수적으로 인지하고 있어야한다.

이 글에서는 List, Set, Queue, Map 등이 내장된 Java Collection Framework 에 대해 간단히 정리한다.

JCF 구조

https://pierrchen.blogspot.com/2014/03/java-collections-framework-cheat-sheet.html

Collection은 collection hiearchy에서 모든 객체의 root interface에 해당한다.

List, Queue, Set 3가지로 분류되고, Map은 이를 상속받지 않지만 Collection으로 분류된다.

각 자료구조의 특징을 먼저 설명하고 사용 예시는 추후 포스팅으로 정리하겠다.

각 인터페이스&클래스 별 분류/특징

Collection	List	- 선형 자료구조로 순서유지 (index) - 중복 허용	- ArrayList - LinkedList - Vector - Stack
	Queue	- 선형 FIFO 구조	- PriorityQueue - ArrayDeque
	Set	- 순서없이 저장 - 중복 불가	- HashSet - LinkedHashSet - TreeSet
Map		- Key:Value 구조로 데이터 저장 - Key는 중복 불가	- HashMap - HashTable - TreeMap - Properties

[ List ]

대표적인 선형 자료구조로, 데이터를 index로 순차적으로 자동부여하고 각 index에 객체 주소를 참조하여 저장한다.

ArrayList

객체 저장시 용량이 초과하면 자동적으로 index를 증가시켜 저장용량이 늘어난다.
단방향 포인터 구조로 순차적으로 저장하기 때문에 검색/조회에 있어 이점이 있다.
데이터 추가, 삭제 시 다른 index 데이터까지 수정해야 하기 때문에 시간복잡도가 높다.

LinkedList

List, Deque를 implement 한 자료구조로, 양방향 포인터로 인접 참조를 링크해서 체인 형태로 데이터를 관리한다.
양방향 포인터 구조로 데이터 삽입, 삭제 시 앞 뒤 링크에 대한 변경만 일어나기 때문에 데이터 삽입/삭제에서 효율적이다.
Stack, Queue, Deque를 만들기 위한 용도

Vector

대용량 처리를 위해 사용했던 자료구조.
내부에서 동기화처리가 되어 thread-safe한 자료구조이다. 다만 ArrayList와 비교하였을 때, 안정성은 좋으나 성능이 좋지 않아 자주 사용되지 않음

Stack

LIFO(Last In First Out) 형태의 자료구조
Interrupt 처리, sub-routine의 복귀 주소 번지를 저장할 때 쓰인다.
DFS 혹은 재귀함수(recursion) 호출 시 사용된다.

[ Queue ]

선형 자료구조로 FIFO(First In First Out) 형태로 순차적으로 데이터를 저장한다.

PriorityQueue

들어온 순서대로 나가는 FIFO 형태가 아닌 데이터마다 우선순위를 결정하고 그 순위에 맞게 나가는 자료구조
Heap으로 구성된 이진트리 구조로 시간복잡도는 O(NlogN) 을 가진다.
우선순위가 필요한 작업에서 쓰인다.

Deque(ArrayDeque)

Queue에서 개념이 확장되어 Queue 양쪽 모두 입출력이 가능한 자료구조이다.
Stack 혹은 Queue로 사용가능하며, Stack 자료구조보다 빠르다. (Stack은 Vector를 상속받아 동기처리 가능)
짧은설명: Deque는 interface, Stack은 class 이기 때문에 확장성에서도 유리.
참고 링크: https://www.baeldung.com/java-deque-vs-stack

[ Set ]

순차적으로 데이터를 유지하지 않고, 데이터의 중복을 허용하지 않는 자료구조이다.

HashSet

순서 없이 저장하며, 가장 빠른 임의 접근 속도를 가지는 구조이다.
일정하게 유지되지 않으며 null 요소도 허용된다.
순서를 관리하지 않아 출력시 다른 순서대로 출력된다.
hashCode() 로 동일한 객체 해시코드를 가지는지 비교 후, equals()로 동일한 객체 여부를 판단하여 중복저장을 피한다.
cf. String 객체를 HashSet에 저장하게 될 경우, String가 hashCode(), equals()를 재정의하여 비교하기 때문에
동일한 객체로 간주되는데 다른 문자열을 가진 경우 서로 다른 객체로 간주한다.

LinkedHashSet

HashSet과 동일한 구조지만 삽입된 요소 순서대로 출력한다.
다른 특징은 HashSet과 동일

SortedSet

각 요소가 정렬된 Set이기 때문에 객체 간 대소비교가 가능한 상태를 유지해줘야한다.
1. Comparable interface를 구현하고 있는 클래스 객체를 원소로 넣을 경우
2. Comparator interface를 구현하고 대소판단을 위한 로직을 SortedSet 객체 생성시 명시해주는 경우
참고 링크: https://cornswrold.tistory.com/203

NavigableSet

SortedSet은 index 접근 개념이 없어 역방향으로 순회하기 어려운 구조이기에 이를 보완한 자료구조
역방향 Iterator가 제공되며, 처음/마지막 원소를 조회/삭제할 수 있다.

TreeSet

BST(Binary Search Tree) 구조 중 RBT(Red Black Tree) 구조로 이루어진 자료구조이다.
HashSet보다 추가/삭제 과정은 시간복잡도에서 좀 더 불리하다.
RBT 특성상 편향되게 데이터를 저장하지 않고, 부모노드보다 작은값은 좌측, 큰값은 우측으로 균형을 맞춰 정렬하기 때문에
조회/검색 성능에서 높은 효율을 보여준다.

[ Map ]

Key-Value 형태로 객체를 저장하며, Key는 중복을 허용하지 않는다. 중복된 키로 저장시 새로운 값이 이전 값을 덮어쓴다.

HashMap

Key와 Value 모두 객체이며, Key는 중복될 수 없다. Map에 Hashing을 사용하기 때문에 대용량의 데이터를 검색하는데 있어 높은 성능을 보여준다.
Hashing을 통해 Key-Value가 저장되는 위치가 결정되기 때문에, 저장 위치의 일관성, 삽입 순서는 알 수 없다.
null 입력이 가능하다.

HashTable

HashMap과 구조가 비슷하며, Key-Value가 1:1 형태로 저장된다.
동기화가 이루어지며, thread-safe한 구조이다. (HashMap/HashTable은 ArrayList/Vector 관계와 유사하다)
null 입력이 불가하다.

Properties

파일 입출력을 지원하며, key=value 형태로 저장된 파일을 Key-Value 로 나누어 저장할 때 유용하다.
Key-Value가 String 형태로 가지고 있어, 보통 프로그램의 설정 정보등을 불러와 코드에 정보를 넣을 때 사용할 수 있다.
옵션정보 / 다국어 정보 등을 저장한다.

TreeMap

이진트리 구조를 한 Map이며, TreeSet과 같은 구조이다. (부모기준 작은값 좌측, 큰값 우측)
TreeSet은 값만 저장하지만, TreeMap은 Key-Value가 저장된 Map.Entry를 저장한다.
객체를 저장하면 오름차순으로 자동정렬하며, String인 경우 Unicode로, Number인 경우 값으로 정렬한다.
성능은 HashMap보다 추가/삭제 등 일반적인 처리에서는 성능이 떨어지지만, 정렬된 상태에서는 데이터 조회/검색은 더 높은 효율을 보여준다.

Summarized general purpose of Collection Classes (Oracle)

각 자료구조마다 특징과 장단점이 뚜렷한만큼 문제해결에 적합한 클래스와 메소드를 인지하고 사용해야 한다.

각 자료구조마다 특징, 코드 예제는 하나씩 추가하여 링크를 걸어둘 예정이다.

위 특징은 추후 시트로 정리하여 내용을 다시 작성할 예정.

Reference

Image
- https://pierrchen.blogspot.com/2014/03/java-collections-framework-cheat-sheet.html
- https://medium.com/@itskevinchandra_15262/java-collections-e77e00392fb4

https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html
https://www3.ntu.edu.sg/home/ehchua/programming/java/J5c_Collection.html#:~:text=In%20Java%2C%20dynamically%20allocated%20data,behaviors%20of%20all%20the%20classes.
https://postitforhooney.tistory.com/entry/JavaCollection-Java-Collection-Framework%EC%97%90-%EB%8C%80%ED%95%9C-%EC%9D%B4%ED%95%B4%EB%A5%BC-%ED%86%B5%ED%95%B4-Data-Structure-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

'Java' 카테고리의 다른 글

[Java] OOP & DI & IoC & SOLID (0)	2022.07.10

memento

[Java] JCF(Java Collection Framework)