언어/Java
[Java] 자바 컬렉션들의 시간 복잡도 (Big O)
쿠큭다스
2021. 11. 23. 16:02
728x90
Java Collection
| 인터페이스 | 특징 | 구현클래스 |
| List | 순서가 있는 데이터의 집합, 데이터의 중복을 허용 | ArrayList, LinkedList, Stack, Vector |
| Set | 객체의 순서가 없으며, 데이터의 중복을 허용하지 않음 | HashSet, TreeSet, EnumSet |
| Queue | 객체를 입력한 순서대로 저장되며, 데이터의 중복을 허용 | PriorityQueue, DelayQueue, LinkedList |
| Map | 키(key)와 값(value)의 쌍으로 이루어진 데이터의 집합 순서가 없으며, 키는 중복을 허용하지 않으며 값은 중복을 허용 |
HashMap, TreeMap, HashTable, Properties |
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) | LinkedList |
| 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 |
| PriorityBlockingQueue | 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 Table |
| ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List |
Reference
728x90