W tym pytaniu Jak efektywnie wybrać kontener biblioteki standardowej w C ++ 11? to przydatny schemat blokowy, którego można używać podczas wybierania kolekcji w języku C ++.
Pomyślałem, że to przydatne źródło informacji dla osób, które nie są pewne, której kolekcji powinny używać, więc próbowałem znaleźć podobny schemat blokowy dla języka Java i nie byłem w stanie tego zrobić.
Jakie zasoby i „ściągawki” są dostępne, aby pomóc ludziom wybrać odpowiednią kolekcję do użycia podczas programowania w Javie? Skąd ludzie wiedzą, jakich implementacji List, Set i Map powinni używać?
Odpowiedzi:
Ponieważ nie mogłem znaleźć podobnego schematu blokowego, zdecydowałem się go stworzyć samodzielnie.
Ten schemat blokowy nie obejmuje takich rzeczy, jak dostęp zsynchronizowany, bezpieczeństwo wątków itp. Lub starszych kolekcji, ale obejmuje 3 standardowe zestawy , 3 standardowe mapy i 2 standardowe listy .
Ten obraz został utworzony dla tej odpowiedzi i jest objęty licencją na podstawie międzynarodowej licencji Creative Commons Attribution 4.0. Najprostszym atrybucją jest umieszczenie linku do tego pytania lub tej odpowiedzi.
Inne zasoby
Prawdopodobnie najbardziej użytecznym innym odniesieniem jest następująca strona z dokumentacji Oracle, która opisuje każdą Kolekcję .
HashSet vs TreeSet
Istnieje szczegółowa dyskusja, kiedy używać
HashSet
lubTreeSet
tutaj: Hashset vs TreesetArrayList vs LinkedList
Szczegółowe omówienie: Kiedy używać LinkedList zamiast ArrayList?
źródło
LinkedList
vsArrayList
decyzji. Po pierwsze,LinkedList
preferowane jest , jeśli lista jest znaczna .LinkedList
ma narzut na element, więc jest asymptotycznie gorszy pod względem zużycia pamięci niż plikArrayList
. Ponadto, jeśli większość dostępu znajduje się na końcu listy,ArrayList
preferowany jest dostęp do elementu, ponieważ zapewnia stały dostęp do elementów losowych. Dostęp don
th elementu aLinkedList
jestO(n)
operacją. ... W rzeczywistości decyzja o użyciu listy połączonej powinna być prawie zawsze „nie”.LinkedList
lista Java jest podwójnie połączona, więc dostęp na początku i na końcu jest szybki. Zauważysz, że z oddziałów powyżej wszystkie trzy pytania muszą odpowiedzieć tak, zanim poleciłbym użycieLinkedList
- innymi słowy zgadzam się z tobą, że w większości przypadków odpowiedź brzmi nie. Rzeczy takie jak kolejki i usuwanie z kolejki, w których stale dodajesz i usuwasz rzeczy z końców listy, jest dobrym przykładem użyciaLinkedList
.LinkedList
zużywa więcej pamięci na element ...ArrayList
nigdy nie zwalnia pamięci. Oznacza to, że jeśli masz listę, która czasami rośnie do ogromnych rozmiarów, ale zwykle jest mała,ArrayList
spowoduje to gorszą wydajność pamięci. Narzut pamięciList
samej siebie jest zwykle (choć nie zawsze) mały w porównaniu z zawartymi w nim elementami.Map<K,V>
nie jest częściąjava.util.collection
Podsumowanie głównych niespójnych, niezsynchronizowanych kolekcji
Collection
: Interfejs reprezentujący nieuporządkowany „worek” przedmiotów, zwany „elementami”. „Następny” element jest niezdefiniowany (losowy).Set
: Interfejs reprezentujący aCollection
bez duplikatów.HashSet
:Set
Wspierany przezHashtable
. Najszybsze i najmniejsze zużycie pamięci, gdy zamawianie nie ma znaczenia.LinkedHashSet
: AHashSet
z dodatkiem połączonej listy w celu skojarzenia elementów w kolejności wstawiania . „Następny” element to następny ostatnio wstawiony element.TreeSet
: A,Set
gdzie elementy są uporządkowane wedługComparator
(typowo naturalny porządek ). Najwolniejsze i największe użycie pamięci, ale niezbędne do porządkowania na podstawie komparatorów.EnumSet
: Niezwykle szybki i wydajnySet
dostosowany do jednego typu wyliczenia.List
: Interfejs reprezentujący a,Collection
którego elementy są uporządkowane i każdy ma indeks numeryczny reprezentujący jego pozycję, gdzie zero jest pierwszym elementem, a(length - 1)
ostatnim.ArrayList
:List
Wspierana przez tablicę, gdzie tablica ma długość (zwaną „pojemnością”) co najmniej równą liczbie elementów („rozmiar” listy). Gdy rozmiar przekracza pojemność (po(capacity + 1)-th
dodaniu elementu), tablica jest odtwarzana z nową pojemnością -(new length * 1.5)
to odtwarzanie jest szybkie, ponieważ używaSystem.arrayCopy()
. Usuwanie i wstawianie / dodawanie elementów wymaga, aby wszystkie sąsiednie elementy (po prawej) zostały przesunięte do lub z tej przestrzeni. Dostęp do dowolnego elementu jest szybki, ponieważ wymaga tylko obliczeń,(element-zero-address + desired-index * element-size)
aby znaleźć jego lokalizację. W większości sytuacji ,ArrayList
korzystne jest ponadLinkedList
.LinkedList
:List
Wspierane przez zestaw obiektów, z których każdy jest powiązany z „poprzednimi” i „następnymi” sąsiadami. ALinkedList
jest również aQueue
iDeque
. Dostęp do elementów odbywa się zaczynając od pierwszego lub ostatniego elementu i przechodząc do momentu osiągnięcia żądanego indeksu. Wstawianie i usuwanie, gdy pożądany indeks zostanie osiągnięty za pomocą przemierzania, jest sprawą trywialną polegającą na ponownym mapowaniu tylko łączy bezpośredniego sąsiada w celu wskazania nowego elementu lub obejścia usuniętego elementu.Map
: Interfejs reprezentującyCollection
gdzie każdy element ma identyfikujący „klucz” - każdy element jest parą klucz-wartość.HashMap
: AMap
gdzie klucze są nieuporządkowane i wspierane przez plikHashtable
.LinkedhashMap
: Klucze są sortowane według kolejności reklamowej .TreeMap
: AMap
gdzie klucze są uporządkowane wedługComparator
(zazwyczaj w kolejności naturalnej).Queue
: Interfejs, który reprezentuje miejsce, wCollection
którym elementy są zazwyczaj dodawane na jednym końcu i usuwane z drugiego (FIFO: pierwszy na wejściu, pierwszy na wyjściu).Stack
: Interfejs, który reprezentuje miejsce, wCollection
którym elementy są zazwyczaj dodawane (wypychane) i usuwane (usuwane) z tego samego końca (LIFO: ostatnie weszło, pierwsze wyszło).Deque
: Skrót od „podwójnie zakończonej kolejki”, zwykle wymawiany jako „talia”. Lista połączona, która jest zwykle dodawana i odczytywana tylko z jednego końca (nie ze środka).Podstawowe schematy kolekcji:
Porównanie wstawienia elementu za pomocą
ArrayList
iLinkedList
:źródło
Jeszcze prostszy obraz. Celowo uproszczone!
Zbiór to wszystko, co zawiera dane zwane „elementami” (tego samego typu). Nie zakłada się nic bardziej szczegółowego.
Lista to indeksowana kolekcja danych, w której każdy element ma indeks. Coś w rodzaju tablicy, ale bardziej elastyczne.
Dane na liście zachowują kolejność wstawiania.
Typowa operacja: pobierz n-ty element.
Zestaw to worek elementów , każdy element tylko raz (elementy wyróżnia się swoją
equals()
metodą.Dane w zestawie są przechowywane głównie po to, aby wiedzieć, jakie dane są.
Typowa operacja: sprawdź, czy element znajduje się na liście.
Mapa jest czymś w rodzaju Listy, ale zamiast dostępu do elementów poprzez ich indeksy całkowite, uzyskujesz do nich dostęp za pomocą ich klucza , którym jest dowolny obiekt. Podobnie jak tablica w PHP :)
Dane w Mapie można przeszukiwać według ich klucza.
Typowa operacja: pobierz element po jego ID (gdzie ID jest dowolnego typu, nie tylko
int
jak w przypadku Listy).Różnice
Set and Map: w Set wyszukujesz dane samodzielnie , podczas gdy w Map ich klucz .
Lista i Mapa: w Liście uzyskujesz dostęp do elementu według ich
int
indeksu (pozycja na liście), podczas gdy w Map za pomocą klucza dowolnego typu (zazwyczaj: ID)List i Set: w List elementy są powiązane przez ich położenie i mogą być zduplikowane, podczas gdy w Set elementy są po prostu „obecne” (nieobecne) i są unikalne (w znaczeniu
equals()
lubcompareTo()
dlaSortedSet
)źródło
To proste: jeśli chcesz przechowywać wartości z przypisanymi do nich kluczami, przejdź do interfejsu Map, w przeciwnym razie użyj Listy dla wartości, które mogą być zduplikowane, a na koniec użyj interfejsu Set, jeśli nie chcesz zduplikowanych wartości w swojej kolekcji.
Oto pełne wyjaśnienie http://javatutorial.net/choose-the-right-java-collection , w tym schemat blokowy itp.
źródło
Mapa
Wybierając a
Map
, utworzyłem tabelę podsumowującą funkcje każdej z dziesięciu implementacji dołączonych do Java 11.źródło
Kolekcje wspólne, kolekcje wspólne
źródło
Której kolekcji Java mam użyć?
To zależy od tego, jaki problem próbujesz rozwiązać lub jakie masz wymagania.
Przykłady:
źródło