Java Collections Framework 구현에 대한 큰 요약?

Java Collections Framework 구현에 대한 큰 요약? [닫은]

---

나는 곧 "Java crash-course"를 가르치고있을 것이다. 청중 구성원이 Big-O 표기법을 알고 있다고 가정하는 것이 안전하지만, 다양한 콜렉션 구현에서 다양한 조작의 순서가 무엇인지 알 것이라고 가정하는 것이 안전하지 않을 수 있습니다.

요약 매트릭스를 직접 생성하는 데 시간이 걸릴 수 있지만 이미 공개 도메인에 이미 존재하는 경우 적절한 크레딧으로 재사용하고 싶습니다.

누구든지 포인터가 있습니까?

---

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

---

책 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)

Queue implementations:

                      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)

The bottom of the javadoc for the java.util package contains some good links:

• Collections Overview has a nice summary table.
• Annotated Outline lists all of the implementations on one page.

---

The Javadocs from Sun for each collection class will generally tell you exactly what you want. HashMap, for example:

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

TreeMap:

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

TreeSet:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

(emphasis mine)

---

The guy above gave comparison for HashMap / HashSet vs. TreeMap / TreeSet.

I will talk about ArrayList vs. LinkedList:

ArrayList:

• O(1) get()
• amortized O(1) add()
• if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(n) to shift all the following elements

LinkedList:

• O(n) get()
• O(1) add()
• if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1)

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