출처) https://www.grepiu.com/post/9
AVA Collection 시간 복잡도/특징 정리
시간복잡도 대표 표현식 위일수록 빠르다.
빠른 순서 ↑
상수 시간 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(long 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
특징 : 무제한으로 인스턴스화 할수 있음
