728x90
자바는 다양한 컬렉션(Collection)을 제공한다. 같은 기능을 동작하는 코드여도 어떤 컬렉션을 사용했는지에 따라 성능 차이가 크게 날수있다. 이 차이는 데이터가 많아질수록 커질것이다. 따라서 컬렉션들의 특징과 각 연산의 수행시간을 고려해서 가장 적합한 컬렉션을 정하는것이 중요하다.
다음은 자바 컬렉션의 시간복잡도를 정리한 표이다.
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 |
h : 해쉬 버킷 사이즈, n : 데이터 사이즈
참조
http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
728x90
'개발 > Java' 카테고리의 다른 글
| [Java] Java - 자바 관련 이것저것 (Overriding, Singleton, Serializable, Comparable, Comparator 등등) (0) | 2022.03.22 |
|---|---|
| [Java] 자바 BufferedWriter를 이용한 int형 출력 (0) | 2021.11.27 |
| [Java] 자바 가상 머신 JVM(Java Virtual Machine)이란? (0) | 2021.11.01 |
| [Java] 자바 String, StringBuffer, StringBuilder 차이 (0) | 2021.10.24 |