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

JAVA / 글쓴이

나는 곧 “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)

큐 구현 :

                      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의 맨 아래 에는 좋은 링크가 있습니다.

답변

각 콜렉션 클래스에 대한 Sun의 Javadoc은 일반적으로 원하는 것을 정확하게 알려줍니다. 예를 들어, HashMap :

이 구현은 해시 함수가 버킷간에 요소를 올바르게 분산시키는 것으로 가정하여 기본 작업 (get 및 put)에 대해 일정한 시간 성능 을 제공합니다 . 컬렉션 뷰를 반복 할 때는 HashMap 인스턴스의 “용량” (버킷 수)에 크기 (키-값 매핑 수)를 더한 시간이 필요합니다 .

TreeMap :

이 구현은 containsKey, get, put 및 remove 작업에 대해 보장 된 log (n) 시간 비용 을 제공합니다.

TreeSet :

이 구현은 기본 작업 (추가, 제거 및 포함)에 대해 보장 된 log (n) 시간 비용을 제공합니다 .

(강조 광산)

답변

위의 사람은 HashMap / HashSet과 TreeMap / TreeSet을 비교했습니다.

ArrayList와 LinkedList에 대해 이야기하겠습니다.

배열 목록 :

  • O (1) get()
  • 상각 된 O (1) add()
  • 삽입하거나 사용하여 중간의 요소를 삭제하는 경우 ListIterator.add()또는 Iterator.remove(), 그것은 O (n은) 다음의 모든 요소를 이동하는 것

연결 목록 :

  • 의 위에) get()
  • O (1) add()
  • 삽입하거나 사용하여 중간의 요소를 삭제하는 경우 ListIterator.add()또는 Iterator.remove(), 그것은 것입니다 O (1)

답변