자바는 다양한 컬렉션 타입들을 제공한다. 이 컬렉션 타입들은 내부 구현에 따라 다양한 시간 복잡도를 갖는데, 이 특징을 잘 알고 사용해야 불필요한 성능저하를 피할 수 있다.
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 |
LinkedList의 시간복잡도에서 remove 연산의 시간복잡도가 O(1)인 이유는 삭제할 엘리먼트에 대한 레퍼런스를 알고 있다고 가정하기 때문에 얻어진 것이다. 만약 삭제할 대상을 탐색하는 동작(get)까지 감안한다면 O(n)이 맞을 것이다.
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 |
Hash 테이블을 사용하는 곳에서는 O(h/n)의 시간 복잡도를 갖는다. h 는 해시 버킷의 숫자이고 n은 해시 테이블을 사용하는 엘리먼트의 개수다. 이렇게 나오는 이유는 엘리먼트에 비해 해시버킷의 수가 늘어나면 해시버킷으로 사용하는 배열의 대부분은 비어있게 되고, 엘리먼트가 담겨 있는 해시버킷을 찾기 위해 매번 비어있는 해시버킷을 방문해야하기 때문에 h 가 들어갔다. 또한 엘리먼트의 숫자가 늘어나면 해시버킷이 비어있을 가능성이 줄어들게 되고, O(1)에 근접하게 된다. 이런 의미에서 H/N 이라는 시간복잡도를 써 놓은 것 같다.
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 |
위에서 본 시간 복잡도는 Worst Case가 아닌 Amortized Analysis가 적용된 평균적인 값이다. 예를 들어 ArrayList의 add() 연산은 배열이 꽉 찾을 때 두 배 더 큰 새로운 배열에 엘리먼트들을 복사하는 최악의 경우가 있어서 O(n)으로 적어야 한다. 하지만 이 연산을 Amortize 하여 평균적으로 O(1)이라고 할 수 있는 것이다.
Reference
http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
댓글