Java Collections Framework 구현에 대한 Big-O 요약

Java Collections Framework 구현에 대한 Big-O 요약

마감되었습니다. 이 질문은 충족되지 않습니다.스택 오버플로우 가이드라인현재 답변을 받고 있지 않습니다.

---

이 질문을 개선하시겠습니까?스택 오버플로의 토픽이 되도록 질문을 업데이트합니다.

5년 전에 문을 닫았어요

이 질문을 개선하다

저는 곧 "자바 크래시 코스"를 가르칠지도 모릅니다.시청자는 Big-O 표기법을 알고 있다고 가정하는 것이 안전할 수 있지만, 다양한 수집 구현에 대한 다양한 조작 순서를 알고 있다고 가정하는 것은 안전하지 않을 수 있습니다.

제가 직접 요약 매트릭스를 생성하는 데 시간을 들일 수는 있지만, 이미 어딘가에 공개되어 있다면, 그것을 재사용하고 싶습니다(물론 적절한 신용으로).

조언해 줄 사람?

Java Generics and Collections 책에는 이러한 정보가 있습니다(페이지: 188, 211, 222, 240).

구현 목록:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

구현 설정:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

맵 실장:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

큐 구현:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

java.util 패키지의 javadoc 하단에는 다음과 같은 정상적인 링크가 포함되어 있습니다.

• Collections Overview에는 멋진 요약 테이블이 있습니다.
• 주석이 달린 개요는 모든 구현을 한 페이지에 나열합니다.

이 웹사이트는 꽤 좋지만 Java에만 국한된 것은 아닙니다.http://bigocheatsheet.com/

각 컬렉션 클래스의 Sun의 Javadocs는 일반적으로 원하는 것을 정확하게 알려줍니다.HashMap의 예:

이 실장에서는 해시함수가 요소를 버킷간에 적절히 분산하는 것을 전제로 하여 기본 조작(get 및 put)에 일정한 시간 퍼포먼스를 제공합니다.컬렉션 뷰를 반복하려면 HashMap 인스턴스의 "용량"(버킷 수)에 비례하는 시간과 해당 크기(키-값 매핑 수)가 필요합니다.

트리 맵:

이 실장에서는, containsKey, get, put, 및 remove 조작의 로그(n)의 시간 코스트가 보증됩니다.

트리 세트:

이 실장에서는, 기본적인 조작(추가, 삭제, 및 포함)에 대해서, 로그(n)의 시간 코스트가 보증됩니다.

(내 것을 제외)

위의 남자는 HashMap/HashSet과 비교했습니다.TreeMap / TreeSet.

Array List와Linked List:

어레이 리스트:

• O(1)get()
• )add()
• 에 ListIterator.add() ★★★★★★★★★★★★★★★★★」Iterator.remove(), 다음의 모든 요소를 시프트 하는 것은 O(n)가 됩니다.

Linked List:

• O(n)get()
• O(1)add()
• 에 ListIterator.add() ★★★★★★★★★★★★★★★★★」Iterator.remove()(1O(1)가 되다.

언급URL : https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations