자바 컬렉션 정리 (Collection)

 

프레젠테이션1.pptx

0.04MB

 

 

 

 

1. Set

 - 중복을 허용하지 않는다.

 - 순서를 보장하지 않는다.

 - index접근이 불가하고 iterator를 사용해야 한다.

 

2. Map

 - key와 value의 쌍으로 이루어짐.

 - key의 중복은 허용하지 않지만 value의 중복은 허용한다.

 

3. List

 - 중복을 허용한다.

 - 순서를 보장한다.

 

Stack - https://walon-h.tistory.com/17?category=971067

 

4. Queue

 - 먼저 들어간 값이 먼저 나오는 구조

 - 삽입과 삭제 연산만 한다.

 

Queue / Deque - https://walon-h.tistory.com/16

Prioirty Queue - https://walon-h.tistory.com/20

 

 

 

 

=== 시간복잡도 ===

※ 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
CopyonWrite ArrayList	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
CopyonWrite ArraySet	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
Concurrent LinkedQueue	O(1)	O(1)	O(1)	O(1)	Linked List
ArrayBlocking Queue	O(1)	O(1)	O(1)	O(n)	Array
Prioririty BlockingQueue	O(log n)	O(1)	O(log n)	O(1)	Priority Heap
Synchronous Queue	O(1)	O(1)	O(1)	O(1)	None!
DelayQueue	O(log n)	O(1)	O(log n)	O(1)	Priority Heap
Linked BlockingQueue	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
Concurrent HashMap	O(1)	O(1)	O(h / n)	Hash Tables
ConcurrentSkip ListMap	O(log n)	O(log n)	O(1)	Skip List

 

출처 : http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html