Podsumowanie Big-O dla implementacji Java Collections Framework? [Zamknięte]

Być może wkrótce będę prowadzić „szybki kurs Java”. Chociaż prawdopodobnie można bezpiecznie założyć, że członkowie publiczności będą znali notację Big-O, prawdopodobnie nie jest bezpiecznie zakładać, że będą wiedzieć, jaka jest kolejność różnych operacji na różnych implementacjach kolekcji.

Mógłbym zająć trochę czasu, aby samodzielnie wygenerować macierz podsumowań, ale jeśli jest już gdzieś w domenie publicznej, na pewno chciałbym go ponownie wykorzystać (oczywiście z odpowiednim kredytem).

Czy ktoś ma jakieś wskazówki?

Ta strona jest całkiem dobra, ale nie jest specyficzna dla Javy: http://bigocheatsheet.com/

W książce Java Generics and Collections znajdują się te informacje (strony: 188, 211, 222, 240).

Lista implementacji:

                      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)

Zestaw realizacji:

                      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)

Implementacje map:

                      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)

Implementacje kolejki:

                      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)

W dolnej części javadoc pakietu java.util znajduje się kilka dobrych linków:

• Przegląd kolekcji ma ładną tabelę podsumowującą.
• Opis z adnotacjami zawiera listę wszystkich implementacji na jednej stronie.

Dokumenty Javadocs firmy Sun dla każdej klasy kolekcji na ogół mówią dokładnie, czego chcesz. HashMap , na przykład:

Ta implementacja zapewnia stałą wydajność dla podstawowych operacji (pobierz i umieść), przy założeniu, że funkcja skrótu prawidłowo rozprasza elementy między zasobnikami. Iteracja po widokach kolekcji wymaga czasu proporcjonalnego do „pojemności” instancji HashMap (liczba segmentów) plus jej rozmiar (liczba mapowań klucz-wartość).

Mapa drzewa :

Ta implementacja zapewnia gwarantowany koszt czasu w dzienniku (n) dla operacji zawieraKey, pobieranie, wysyłanie i usuwanie.

TreeSet :

Ta implementacja zapewnia gwarantowany koszt log (n) czasu dla podstawowych operacji (dodawanie, usuwanie i zawiera).

(podkreślenie moje)

Facet powyżej przedstawił porównanie HashMap / HashSet vs. TreeMap / TreeSet.

Porozmawiam o ArrayList vs. LinkedList:

ArrayList:

• O (1) get()
• amortyzowane O (1) add()
• jeśli wstawisz lub usuniesz element w środku za pomocą ListIterator.add()lub Iterator.remove(), przesunięcie wszystkich kolejnych elementów będzie O (n)

Połączona lista:

• Na) get()
• O (1) add()
• jeśli wstawisz lub usuniesz element w środku za pomocą ListIterator.add()lub Iterator.remove(), będzie to O (1)