Collections 시간복잡도 정리

시간복잡도 대표 표현식 위일수록 빠르다.

빠른 순서 ↑

상수 시간 O(1)

로그시간 O(log N)

직선형 시간 O(N)

2차 시간 O(n^2)

지수 시간 O(C^n)

느린 순서 ↓

 

LIST

#ArrayList

시간복잡도
add             : O(1)
remove          : O(n)
get             : O(1)
Contains        : O(n)
iterator.remove : O(n)
java 1.2에 추가, thread-safe 보장 안함
 특징 :  데이터 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사
   - 대량의 자료를 추가/삭제시 복사가 일어 나게 되어 성능 저하를 일이킴
   - 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름

 

#LinkedList

시간복잡도
add             : O(1)
remove          : O(1)
get             : O(n)
Contains        : O(n)
iterator.remove : O(1)
java 1.2에 추가, thread-safe 보장 안함
특징 : 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다.
   - 데이터 추가/삭제시 빠름
   - 데이터 검색시 처음부터 노드를 순화해야 되기 때문에 느림

 

#CopyOnWriteArrayList

시간복잡도
add             : O(n)
remove          : O(n)
get             : O(1)
Contains        : O(n)
iterator.remove : O(n)
java 1.5 추가 thread-safe 보장, 병렬처리
특징 : 처리에 여분의 오버로드를 가져오지만 순회 작업의 수에 비해 수정 횟수가 최소일때 효과적 이다.
    - add는 ArrayList, LinkedList 보다 느리지만 get은 LinkedList보단 빠르고 ArrayList보단 살짝 느리다.

 

SET

#HashSet

시간복잡도
add         :   O(1)
contains    :   O(1)
next        :   o(h/n) h는 테이블 용량
java 1.2 thread-safe 보장 안함
특징 : 객체들을 순서없이 저장하고 동일한 객체를 중복 저장하지 않는다.
    - 중복되지 않는 값을 등록할때 용의
    - 순서없이 저장되는것 주위
    - null을 허용한다.

 

#LinkedHashSet

시간복잡도
add       : O(1)
contains  : O(1)
next      : O(1)
java 1.4 thread-safe 보장 안함
특징 : 속도는 hashSet에 비해 느리지만 좋은 성능을 보장한다.
    - 등록한 순으로 정렬을 한다.
    - null을 허용한다.

 

#CopyOnWriteArraySet

시간복잡도
add       : O(1)
contains  : O(1)
next      : O(1)
Java 1.5 에서 나옴
특징 : 적은 메모리를 사용
      - 빠르다
      - null을 사용 할 수 없다.

 

#TreeSet

시간복잡도
add       : O(log n)
contains  : O(log n)
next      : O(log n)
java 1.2 에서 나옴 thread-safe 보장 안함
특징 : 객체기준으로 정렬을 한다. 느리다.
    - null을 허용하지 않는다.

 

#ConcurrentSkipListSet

시간복잡도
add       : O(log n)
contains  : O(log n)
next      : O(1)
java 1.6 병렬처리, thread-safe 보장, 병렬 보장
특징 : Null을 허용하지 않는다.
  - Tree set 처럼 정렬을 한다.

 

Map

#HashMap

시간복잡도
get           : O(1)
containsKey   : O(1)
next          : O(h/n) h는 테이블 용량
java 1.2 에서 나옴
특징 : 순서에 상관없이 저장됨, Null을 허용한다. thread-safe 보장하지 않는다.

 

 

#LinkedHashMap

시간복잡도
get           : O(1)
containsKey   : O(1)
next          : O(1)
java 1.4 에서 나옴
특징 : 순서대로 등록한다. Null을 허용한다. thread-safe 보장하지 않는다.

 

#IdentityHashMap

시간복잡도
get           : O(1)
containsKey   : O(1)
next          : O(h/n) H는 테이블
java 1.4 에서 나옴
특징 : Map 형식에 부합되지 않음

 

#EnumMap

시간복잡도
get           : O(1)
containsKey   : O(1)
next          : O(1)
java 1.5 에서 나옴

 

#TreeMap

시간복잡도
get           : O(log n)
containsKey   : O(log n)
next          : O(log n)
java 1.2 에서 나옴
특징 : 정렬이 되면서 추가가 됨
     -  null은 허용하지 않음
     -  thread-safe 보장하지 않는다.

 

#ConcurrentHashMap

시간복잡도
get           : O(1)
containsKey   : O(1)
next          : O(h/n) h는 테이블
java 1.5 에서 나옴
특징 :  thread-safe 보장하면서 SynchronizedMap 보다 속도가 빠르다
      - null을 허용하지 않음

 

#ConcurrentSkipListMap

시간복잡도
get           : O(log n)
containsKey   : O(log n)
next          : O(1)
java 1.6 에서 나옴
특징 : thread-safe 보장하면서 SynchronizedMap 보다 속도가 빠르다
       - 메모리를 사용하여 O(log n)으로 데이터를 검색, 삽입, 삭제가 가능하다
       - lock이 적게 사용되어야 하는 병렬 처리 시스템에 용의

 

Queue

#PriorityQueue

시간복잡도
offer(입력)   : O(log n)
peek(get)     : O(1)
poll(반환)    : O(log n)
size          : O(1)
natural order : JVM에서 제공하는 일반적인거와 다를수 있음 순서 ex) 문자는 ASCII 순서로 정렬
java 1.5 에서 나옴
특징 : 일반적은 큐는 FIFO의 구조를 가지지만 자연 네추럴 오더에 따라 정렬
      - Null을 허용하지 않는다.

 

#ConcurrentLinkedQueue

시간복잡도
offer     : O(1)
peek     : O(1)
poll     : O(1)
size     : O(n)
java 1.5 에서 나옴 thread-safe 보장(결과에 문제가 발생할 여지 있음)
특징 : FIFO 방식 Queue
 - 데이터/추가/삭제가 빠름
- size는 O(1)이 아니다.
- null을 허용하지 않는다.

 

#ArrayBlockingQueue

시간복잡도
offer     : O(1)
peek     : O(1)
poll     : O(1)
size     : O(1)
java 1.5에서 나옴
특징 - 고정배열에 일반적인 Queue(FIFO)
- 배열이 고정된 사이즈, 생성되면 변경 안됨

 

#LinkedBlockingQueue

시간복잡도
offer     : O(1)
peek     : O(1)
poll     : O(1)
size     : O(1)
java 1.5 에서 나옴
특징 : FIFO 정렬
- 크기를 지정하지 않을 경우 Integer.MAX_VALUE와 동일하게 생성됨
- 삽입이 동적임

 

#PriorityBlockingQueue

시간복잡도
offer     : O(log n)
peek     : O(1)
poll     : O(log n)
size     : O(1)
java 1.5 에서 나옴
특징 : PriorityQueue 와 같은 정렬식으로 저장
- 논리적으로 한대로 추가 가능
- 자원이 고갈되면 OOM 발생

 

#DelayQueue

시간복잡도
offer     : O(log n)
peek     : O(1)
poll     : O(log n)
size     : O(1)
java 1.5 에서 나옴
특징 : 지연이 만료 되었을 때문 요소를 가져올수있다.

 

#ArrayDeque

시간복잡도
offer     : O(1)
peek     : O(1)
poll     : O(1)
size     : O(1)
java 1.6에서 나옴
특징 : 양 측면에서 요소를 추가하거나 제거 할수 있는 확장 가능한 배열의 특별한 종류

 

#LinkedBlockingDeque

시간복잡도
offer     : O(1)
peek     : O(1)
poll     : O(1)
size     : O(1)
java 1.6
특징 : 무제한으로 인스턴스화 할수 있음