JCF란?
JCF(Java collection Framework)는 Java에서 컬렉션을 표현하고 처리하기위한 자료구조다. JCF의 구조는 아래와 같다.
Set은 Collection을 상속받지 않고 별도의 인터페이스를 가진다.
List
순서가 정해져있고 중복된 값을 가질 수 있는 데이터를 관리할 떄 사용한다.
-
ArrayList: 삽입 순서를 유지하여 메모리에 저장한다. C++의 Vector와 같은 역할이다. -
LinkedList: 양방향 포인터 구조로 되어있어 데이터의 삽입, 삭제가 빈번하게 일어난다면 좋은 성능을 얻을 수 있다.
-
Vector:ArrayList와 비슷하지만만 약간의 차이점이 있다. 벡터는 동기화가 되기때문에 스레드로부터 안전한 구현을 할 수 있다.Vector에는 레거시 메서드가 많기 때문에 스레드로부터 안전한 구현이 필요없다면ArrayList를 쓰는 것이 좋다. -
Stack: last-in-first-out을 구현해둔 데이터 구조다.
Queue
first-in-first-out을 구현해둔 데이터 구조다.
-
LinkedList -
PriorityQueue: Queue를 구현한 것이지만, first-in-first-out으로 작동하지 않는다. 우선순위가 높은 것이 먼저 반환된다.
Deque
컬렉션의 양쪽 끝에서 요소의 삽입 제거를 지원한다. (Double ended queue)
-
ArrayDequeue: Linkedlist 및 Stack보다 빠르기 때문에, 외부 동기화가 없는 경우에는 Stack 대신 사용을 고려해볼 수 있다. -
LinkedList
Set
중복할 수없는 순서가 없는 데이터를 처리하기위한 자료구조다.
-
HashSet: 저장을 위해 해쉬 테이블을 사용한다. 삽입 순서를 유지하지 않는다. -
LinkedHashSet: HashSet을 확장한 클래스로 삽입 순서를 유지한다. -
TreeSet: 저장을 위해 트리를 사용한다. 요소들이 정렬되어 있다. 레드-블랙 트리로 구현되어 있다.
Map
키와 갑을 쌍으로 데어터를 처리하는 자료구조다.
-
HashMap: 저장을 위해 해쉬 테이블을 사용한다. 삽입 순서를 유지하지 않는다. -
LinkedHashMap: HashMap을 상속 받고 삽입 순서를 유지한다. -
TreeMap: 저장을 위해 트리르 사용한다. 요소들이 정렬되어 있다. 레드-블랙 트리로 구현되어 있다.
성능
아래는 구현에 사용되는 자료구조의 성능을 정리해두었다.
- list
| 종류 | Add | Remove | Get | Contains | Data structure |
|---|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(1) | O(n) | Array |
| LinkedList | O(1) | O(1) | O(n) | O(n) | Linked List |
| CopyonWriteArrayList | O(n) | O(n) | O(1) | O(n) | Array |
- Set
| 종류 | Add | Contains | Next | Data structure |
|---|---|---|---|---|
| HashSet | O(1) | O(1) | O(h/n) | Hash Table |
| LinkedHashSet | O(1) | O(1) | O(1) | Hash Table + Linked List |
| EnumSet | O(1) | O(1) | O(1) | Bit Vector |
| TreeSet | O(log n) | O(log n) | O(log n) | Red-black tree |
| CopyonWriteArraySet | O(n) | O(n) | O(1) | Array |
| ConcurrentSkipList | O(log n) | O(log n) | O(1) | Skip List |
- Queue
| 종류 | Offer | Peak | Poll | Size | Data structure |
|---|---|---|---|---|---|
| PriorityQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| LinkedList | O(1) | O(1) | O(1) | O(1) | Array |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) | Linked List |
| ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | Linked List |
| ArrayBlockingQueue | O(1) | O(1) | O(1) | O(1) | Array |
| PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| SynchronousQueue | O(1) | O(1) | O(1) | O(1) | None! |
| DelayQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| LinkedBlockingQueue | O(1) | O(1) | O(1) | O(1) | Linked List |
- Map
| 종류 | Get | ContainsKey | Next | Data structure |
|---|---|---|---|---|
| HashMap | O(1) | O(1) | O(h/n) | Hash Table |
| LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List |
| IdentityHashMap | O(1) | O(1) | O(h / n) | Array |
| WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table |
| EnumMap | O(1) | O(1) | O(1) | Array |
| TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree |
| ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables |
| ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List |
관련 사이트
https://www.javatpoint.com/collections-in-java
https://www.edureka.co/blog/java-collections/
http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
댓글남기기