Której kolekcji Java mam użyć?

127

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ć?

Tim B.
źródło
W książce Java Generics and Collections (Naftalin & Wadler) znajduje się rozdział na ten temat.
Christophe Roussy

Odpowiedzi:

292

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 .

wprowadź opis obrazu tutaj

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ć HashSetlub TreeSettutaj: Hashset vs Treeset

ArrayList vs LinkedList

Szczegółowe omówienie: Kiedy używać LinkedList zamiast ArrayList?

Tim B.
źródło
Miły! Muszę jednak nie zgadzają się ze swoim LinkedListvs ArrayListdecyzji. Po pierwsze, LinkedListpreferowane jest , jeśli lista jest znaczna . LinkedListma narzut na element, więc jest asymptotycznie gorszy pod względem zużycia pamięci niż plik ArrayList. Ponadto, jeśli większość dostępu znajduje się na końcu listy, ArrayListpreferowany jest dostęp do elementu, ponieważ zapewnia stały dostęp do elementów losowych. Dostęp do nth elementu a LinkedListjest O(n)operacją. ... W rzeczywistości decyzja o użyciu listy połączonej powinna być prawie zawsze „nie”.
Matt Ball
2
@MattBall W większości zgadzam się z tobą. Jednak LinkedListlista 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życie LinkedList- 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życia LinkedList.
Tim B
@MattBall Wykorzystanie pamięci jest o wiele trudniejszą sytuacją, ponieważ podczas gdy LinkedListzużywa więcej pamięci na element ... ArrayListnigdy 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, ArrayListspowoduje to gorszą wydajność pamięci. Narzut pamięci Listsamej siebie jest zwykle (choć nie zawsze) mały w porównaniu z zawartymi w nim elementami.
Tim B
Map<K,V>nie jest częściąjava.util.collection
Mehraj Malik
@MehrajMalik Hmm, oznaczenie jest niejednoznaczne Zgadzam się. Miałem na myśli Kolekcja wewnątrz java.util. tj. java.util. * wstaw tutaj nazwę kolekcji *
Tim B
66

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 a Collectionbez duplikatów.
    • HashSet: SetWspierany przez Hashtable. Najszybsze i najmniejsze zużycie pamięci, gdy zamawianie nie ma znaczenia.
    • LinkedHashSet: A HashSetz dodatkiem połączonej listy w celu skojarzenia elementów w kolejności wstawiania . „Następny” element to następny ostatnio wstawiony element.
    • TreeSet: A, Setgdzie elementy są uporządkowane według Comparator(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 wydajny Setdostosowany do jednego typu wyliczenia.
  • List: Interfejs reprezentujący a, Collectionktó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: ListWspierana 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)-thdodaniu elementu), tablica jest odtwarzana z nową pojemnością - (new length * 1.5)to odtwarzanie jest szybkie, ponieważ używa System.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 , ArrayListkorzystne jest ponad LinkedList.
    • LinkedList: ListWspierane przez zestaw obiektów, z których każdy jest powiązany z „poprzednimi” i „następnymi” sąsiadami. A LinkedListjest również a Queuei Deque. 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ący Collectiongdzie każdy element ma identyfikujący „klucz” - każdy element jest parą klucz-wartość.
    • HashMap: A Mapgdzie klucze są nieuporządkowane i wspierane przez plik Hashtable.
    • LinkedhashMap: Klucze są sortowane według kolejności reklamowej .
    • TreeMap: A Mapgdzie klucze są uporządkowane według Comparator(zazwyczaj w kolejności naturalnej).
  • Queue: Interfejs, który reprezentuje miejsce, w Collectionktó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, w Collectionktó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:

diagram

Porównanie wstawienia elementu za pomocą ArrayListi LinkedList:

diagram

aliteralmind
źródło
2
Najlepsze w krótkim okresie letnim, które można dostać wszędzie :)
roottraveller
11

Jeszcze prostszy obraz. Celowo uproszczone!

  1. Zbiór to wszystko, co zawiera dane zwane „elementami” (tego samego typu). Nie zakłada się nic bardziej szczegółowego.

  2. 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.

  3. 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.

  4. 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 intindeksu (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()lub compareTo()dla SortedSet)

Honza Zidek
źródło
1

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.

filip_j
źródło
1

Mapa

Wybierając a Map, utworzyłem tabelę podsumowującą funkcje każdej z dziesięciu implementacji dołączonych do Java 11.

Tabela implementacji map w Javie 11, porównująca ich funkcje

Basil Bourque
źródło
0

Kolekcje wspólne, kolekcje wspólne wprowadź opis obrazu tutaj

Aliaksandr Shpak
źródło
-2

Której kolekcji Java mam użyć?

To zależy od tego, jaki problem próbujesz rozwiązać lub jakie masz wymagania.

Przykłady:

  1. Czy chcesz, aby elementy były sortowane podczas ich przechowywania? HashSet
  2. Czy chcesz, aby pary (klucz, wartość) były przechowywane? HashMap
  3. Czy chcesz zachować kolejność wstawianych elementów? ArrayList, LinkedList
  4. Czy chcesz, aby klucze w parze (klucz, wartość) były sortowane? - mocny tekst
  5. Czy chcesz wdrożyć stos, aby rozwiązać swój problem? - Stos
  6. Czy chcesz mieć dostęp do FIFO (First in First out)? - Kolejka
  7. Czy chcesz, aby były przechowywane tylko UNIKALNE elementy? - HashSet
  8. Czy chcesz zezwolić na klucz jako „Null” podczas przechowywania (klucz, wartość)? - HashMap
  9. Czy chcesz, aby para (klucz, wartość) nie miała wartości NULL? HashTable
Aviral Kumar
źródło
Nawet jeśli mocny tekst w pozycji 4 zostanie zastąpiony, powiedzmy, ConcurrentSkipListMap (K, V) , co ta odpowiedź dodaje do wykresu decyzyjnego Tima B , do „krótkich opisów listy” aliteralmind ?
siwobrody
Pierwsza uwaga: HashSet nie sortuje danych, nawet kolejność reklam nie jest utrzymywana. Powinieneś to zmienić za pomocą TreeSet
Saurabh Mishra