Krótko o najważniejszym - Java Collections Framework

Początek drogi

Dzisiaj chciałbym poruszyć tak ciekawy temat jak „ Java Collections Framework ”, czyli w uproszczeniu o kolekcjach. Większość pracy kodu polega na przetwarzaniu danych w takiej czy innej formie. Uzyskaj listę użytkowników, uzyskaj listę adresów itp. Jakoś je posortuj, wyszukaj, porównaj. Dlatego też znajomość kolekcji uważana jest za umiejętność podstawową. Dlatego chcę o tym porozmawiać. Ponadto jednym z najczęstszych pytań w rozmowach z programistami Java jest kwestia kolekcji. Na przykład „narysuj hierarchię kolekcji”. Kompilator online pomoże nam na naszej drodze. Na przykład możesz użyć „ Tutorialspoint Online Java Compiler ” lub Repl.it. Droga do poznania dowolnych struktur danych zaczyna się od zwykłych zmiennych (Zmiennych). W serwisie Oracle różne tematy są reprezentowane jako „ścieżki” lub szlaki. Tak więc droga do poznania Javy nosi nazwę „ Szlak: Nauka języka Java: Spis treści ”. A podstawy języka (tj. Podstawy języka) zaczynają się od zmiennych. Dlatego napiszmy prosty kod:

public static void main(String[] args) {
	String user = "Max";
	System.out.println("Hello, " + user);
}

Jest dobry we wszystkim, z tą różnicą, że rozumiemy, że ten kod jest dobry i piękny tylko dla jednej zmiennej. Co zrobić, jeśli jest ich kilka? Tablice zostały wynalezione do przechowywania danych jednego typu. W tym samym szlaku od Oracle znajduje się osobna sekcja poświęcona tablicom. Ta sekcja nosi nazwę: „ Tablice ”. Praca z tablicami jest również dość prosta:

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    String[] users = new String[2];
    users[0] = "Max";
    users[1] = "John";
    System.out.println("Hello, " + Arrays.toString(users));
  }
}

Tablice rozwiązują problem przechowywania wielu wartości w jednym miejscu. Nakłada to jednak ograniczenie: rozmiar tablicy jest stały. Jeśli, jak w przykładzie, powiedzieliśmy, że rozmiar = 2, to jest on równy dwa. To wszystko. Jeśli chcemy mieć większą tablicę, musimy utworzyć nową instancję. Znalezienie elementu również jest trudne w przypadku tablicy. Istnieje metoda Arrays.binarySearch, ale to wyszukiwanie działa tylko na posortowanej tablicy (w przypadku nieposortowanej tablicy wynik jest niezdefiniowany lub po prostu nieprzewidywalny). Oznacza to, że wyszukiwanie będzie nas zobowiązywać do sortowania za każdym razem. Usunięcie również powoduje wyczyszczenie tylko wartości. Dlatego nadal nie wiemy, ile danych faktycznie znajduje się w tablicy, wiemy jedynie, ile komórek znajduje się w tablicy. Aby odświeżyć swoją wiedzę na temat tablic:

• „ JavaRush: Tablice w Javie ”
• „ Samouczek Java: Tablice ”

A w konsekwencji rozwoju języka Java w JDK 1.2 pojawił się Java Collections Framework, o którym dzisiaj porozmawiamy.

Kolekcja

Zacznij kalkulować koszty od samego początku. Dlaczego Kolekcje? Sam termin pochodzi od „teorii typów” i „abstrakcyjnych typów danych”. Ale jeśli nie patrzy się na jakieś wzniosłe sprawy, to gdy mamy kilka rzeczy, możemy je nazwać „zbiórem rzeczy”. Ci, którzy zbierają przedmioty. Ogólnie rzecz biorąc, samo słowo zbierać pochodzi od łac. collectio „zbieranie, kolekcjonowanie”. Oznacza to, że kolekcja to zbiór czegoś, pojemnik na niektóre elementy. Mamy więc zbiór elementów. Co możemy z tym zrobić: Jak widać, możemy chcieć rzeczy całkiem logicznych. Rozumiemy również, że możemy chcieć zrobić coś z wieloma kolekcjami: W związku z tym programiści Java napisali interfejs java.util.Collection , aby opisać to ogólne zachowanie dla wszystkich kolekcji . Interfejs Kolekcji to miejsce, z którego pochodzą wszystkie kolekcje. Kolekcja to pomysł, to pomysł na to, jak powinny zachowywać się wszystkie kolekcje. Dlatego termin „kolekcja” jest wyrażany jako interfejs. Interfejs wymaga oczywiście implementacji. Interfejs java.util.Collectionma klasę abstrakcyjną AbstractCollection, to znaczy „kolekcję abstrakcyjną”, która reprezentuje szkielet dla innych implementacji (jak napisano w JavaDoc nad klasą java.util.AbstractCollection). Skoro już mowa o kolekcjach, cofnijmy się i pamiętajmy, że chcemy po nich iterować. Oznacza to, że chcemy iterować elementy jeden po drugim. To bardzo ważna koncepcja. Dlatego interfejs Collectionjest dziedziczony z Iterable. To bardzo ważne, ponieważ... po pierwsze, wszystko Iterable musi być w stanie zwrócić Iterator na podstawie jego zawartości. A po drugie, wszystko, co Iterable można wykorzystać w pętlach for-each-loop. I to właśnie przy pomocy iteratora implementowane są AbstractCollectionmetody takie jak contains, toArray. removeA droga do zrozumienia kolekcji zaczyna się od jednej z najczęstszych struktur danych – listy, czyli tzw. List.

Listy

Listy zajmują więc ważne miejsce w hierarchii kolekcji: Jak widzimy, listy implementują interfejs java.util.List . Listy wyrażają, że mamy zbiór elementów ułożonych w pewnej kolejności, jeden po drugim. Każdy element ma indeks (jak w tablicy). Zazwyczaj lista pozwala na posiadanie elementów o tej samej wartości. Jak powiedzieliśmy powyżej, Listzna indeks elementu. Pozwala to uzyskać ( get) element według indeksu lub ustawić wartość dla określonego indeksu ( set). addMetody zbierania addAllpozwalają removeokreślić indeks, z którego mają zostać wykonane. Dodatkowo y Listma własną wersję iteratora o nazwie ListIterator. Iterator ten zna indeks elementu, dzięki czemu może iterować nie tylko do przodu, ale także do tyłu. Można go nawet utworzyć z określonego miejsca w kolekcji. Spośród wszystkich implementacji najczęściej stosowane są dwie: ArrayListi LinkedList. Po pierwsze, ArrayListjest to lista ( List) oparta na tablicy ( Array). Pozwala to uzyskać „Losowy dostęp” do elementów. Dostęp losowy to możliwość natychmiastowego pobrania elementu według indeksu, zamiast iteracji po wszystkich elementach, aż znajdziemy element o żądanym indeksie. To właśnie tablica stanowi podstawę, która pozwala to osiągnąć. Wręcz przeciwnie, LinkedListjest to lista połączona. Każdy wpis na połączonej liście jest reprezentowany w formularzu Entry, w którym przechowywane są same dane, a także łącze do następnego (następnego) i poprzedniego (poprzedniego) Entry. W ten sposób LinkedListrealizuje „Dostęp sekwencyjny ” . Oczywiste jest, że aby znaleźć piąty element, będziemy musieli przejść od pierwszego elementu do ostatniego, ponieważ nie mamy bezpośredniego dostępu do piątego elementu. Dostęp do niego mamy tylko z czwartego elementu. Poniżej przedstawiono różnicę w ich koncepcji: W pracy, jak rozumiesz, jest też różnica. Na przykład dodanie elementów. Elementy LinkedListsą po prostu połączone jak ogniwa łańcucha. Ale ArrayListprzechowuje elementy w tablicy. A tablica, jak wiemy, nie może zmienić swojego rozmiaru. Jak to wtedy działa ArrayList? I działa to bardzo prosto. Kiedy miejsce w tablicy się skończy, zwiększa się ono 1,5 razy. Oto kod powiększenia: int newCapacity = oldCapacity + (oldCapacity >> 1); Kolejną różnicą w działaniu jest dowolne przemieszczanie elementów. Na przykład podczas dodawania lub usuwania elementów na środku. Aby usunąć z LinkedListelementu, po prostu usuń odniesienia do tego elementu. W przypadku , ArrayListjesteśmy zmuszeni każdorazowo przesuwać elementy za pomocą System.arraycopy. Zatem im więcej elementów, tym więcej czynności będzie trzeba wykonać. Bardziej szczegółowy opis można znaleźć w tych artykułach:

• " Struktury danych na obrazach. ArrayList "
• " Struktury danych na zdjęciach. LinkedList "
• „ Co kryje się pod maską LinkedList? ”

Po zapoznaniu się z ArrayList nie sposób nie wspomnieć o jego „poprzedniku”, klasie java.util.Vector . Różni się Vectortym ArrayList, że metody pracy z kolekcją (dodawanie, usuwanie itp.) są zsynchronizowane. Oznacza to, że jeśli jeden wątek ( Thread) doda elementy, to pozostałe wątki będą czekać, aż pierwszy wątek zakończy swoją pracę. Ponieważ bezpieczeństwo wątków często nie jest wymagane, w takich przypadkach zaleca się używanie tej klasy ArrayList, jak wyraźnie stwierdzono w dokumentacji JavaDoc dla tej klasy Vector. Ponadto Vectorzwiększa swój rozmiar nie 1,5-krotnie, ArrayListale 2-krotnie. W przeciwnym razie zachowanie jest takie samo - Vectorprzechowywanie elementów w postaci tablicy jest ukryte, a dodawanie/usuwanie elementów ma takie same konsekwencje jak w ArrayList. Właściwie Vectornie bez powodu o tym pamiętaliśmy. Jeśli zajrzymy do Javadoc, w „Bezpośrednio znanych podklasach” zobaczymy strukturę taką jak java.util.Stack . Stos jest interesującą strukturą, która jest last-in-first-outstrukturą LIFO (ostatnie weszło, pierwsze wyszło). Stos przetłumaczony z angielskiego to stos (na przykład stos książek). Stos implementuje dodatkowe metody: peek(patrz, patrz), pop(push), push(push). Metodę tę peektłumaczy się jako zaglądanie (na przykład zaglądanie do torby oznacza „ zaglądanie do torby ”, a zaglądanie przez dziurkę od klucza oznacza „ zaglądanie przez dziurkę od klucza ”). Metoda ta pozwala spojrzeć na „górę” stosu, tj. zdobądź ostatni element bez usuwania (tj. bez usuwania) go ze stosu. Metoda pushwypycha (dodaje) nowy element na stos i zwraca go, a metoda elementowa popwypycha (usuwa) i zwraca usunięty. We wszystkich trzech przypadkach (tj. peek, pop i push) pracujemy tylko z ostatnim elementem (tj. „szczytem stosu”). Jest to główna cecha struktury stosu. Nawiasem mówiąc, istnieje ciekawe zadanie zrozumienia stosów, opisane w książce „Kariera programisty” (Wywiad dotyczący łamania kodu).Interesujące jest zadanie, w którym korzystając ze struktury „stosu” (LIFO) należy zaimplementować „kolejkę ”struktura (FIFO). To powinno wyglądać tak: Analizę tego zadania można znaleźć tutaj: „ Zaimplementuj kolejkę za pomocą stosów — ADT kolejki („Zaimplementuj kolejkę za pomocą stosów” w LeetCode) „. Płynnie zatem przechodzimy do nowej struktury danych – kolejki.

Kolejka

Kolejka to konstrukcja znana nam z życia. Kolejki do sklepów, do lekarzy. Ktokolwiek przyszedł pierwszy (First In), jako pierwszy opuści kolejkę (First Out). W Javie kolejka jest reprezentowana przez interfejs java.util.Queue . Według Javadoc kolejki kolejka dodaje następujące metody: Jak widać, istnieją metody rozkazujące (niewykonanie ich jest obarczone wyjątkiem) i istnieją metody żądań (niemożność ich wykonania nie prowadzi do błędów). Możliwe jest również zdobycie elementu bez jego usuwania (zaglądanie lub element). Interfejs kolejki ma także przydatnego następcę - Deque . Jest to tak zwana „kolejka dwukierunkowa”. Oznacza to, że taka kolejka pozwala na użycie tej struktury zarówno od początku, jak i od końca. Dokumentacja mówi, że „Deques może być również używany jako stosy LIFO (Last-In-First-Out). Tego interfejsu należy używać zamiast starszej klasy Stack.”, to znaczy zaleca się używanie implementacji Deque zamiast Stos. Javadoc pokazuje, jakie metody opisuje interfejs Deque: Zobaczmy, jakie są implementacje. I zobaczymy ciekawy fakt - LinkedList dostał się do obozu kolejek) Oznacza to, że LinkedList implementuje zarówno List, jak i Deque. Ale są też na przykład „tylko kolejki” PriorityQueue. Nieczęsto się o niej pamięta, ale na próżno. Po pierwsze, w tej kolejce nie można używać „obiektów nieporównywalnych”, tj. Należy określić komparator lub wszystkie obiekty muszą być porównywalne. Po drugie, „ta implementacja zapewnia czas O(log(n)) dla metod umieszczania w kolejce i usuwania z kolejki”. Złożoność logarytmiczna istnieje nie bez powodu. Zaimplementowano PriorityQueue w oparciu o stertę. Javadoc mówi: „Kolejka priorytetowa reprezentowana jako zrównoważona sterta binarna”. Sama pamięć do tego jest zwykłą tablicą. Który rośnie, gdy jest to konieczne. Kiedy sterta jest mała, zwiększa się 2 razy. A potem o 50%. Komentarz z kodu: „Podwójny rozmiar, jeśli jest mały; w przeciwnym razie zwiększ o 50%”. Kolejka priorytetowa i sterta binarna to osobny temat. A więc więcej informacji:

• Super artykuł na temat Habré: „ Struktury danych. Nieformalny przewodnik ”
• Jasne wyjaśnienie „sterty”: „ Foxford: Informatyka. Struktury danych: Kopiec ”
• Artykuł z Habr o stercie binarnej: „ Struktury danych: sterta binarna ”
• „ Wprowadzenie do kopców binarnych (MaxHeaps) ”

Implementacją java.util.Dequemoże być klasa java.util.ArrayDeque . Oznacza to, że listy można implementować przy użyciu listy połączonej i tablicy, a kolejki można również implementować przy użyciu tablicy lub listy połączonej. Interfejsy Queuei Dequemają potomków reprezentujących „kolejkę blokującą”: BlockingQueue​​i BlockingDeque. Oto zmiana interfejsu w porównaniu do zwykłych kolejek: Przyjrzyjmy się kilku przykładom blokowania kolejek. Ale są interesujące. Na przykład BlockingQueue jest implementowany przez: PriorityBlockingQueue , SynchronousQueue , ArrayBlockingQueue, DelayQueue , LinkedBlockingQueue . Ale BlockingDequeimplementują wszystko, począwszy od standardowych frameworków kolekcji LinkedBlockingDeque. Każda kolejka jest tematem osobnej recenzji. W ramach tego przeglądu przedstawimy hierarchię klas nie tylko za pomocą List, ale także za pomocą Queue: Jak widać na diagramie, interfejsy i klasy Java Collections Framework są ze sobą ściśle powiązane. Dodajmy kolejną gałąź hierarchii - Set.

Ustawić

Set— przetłumaczone jako „zestaw”. Różni się od kolejki i listy Setwiększą abstrakcją w zakresie przechowywania elementów. Set- jak worek z przedmiotami, w którym nie wiadomo, gdzie przedmioty są ułożone i w jakiej kolejności są ułożone. W Javie taki zbiór jest reprezentowany przez interfejs java.util.Set . Jak mówi dokumentacja, Setjest to „kolekcja niezawierająca zduplikowanych elementów”. Co ciekawe, sam interfejs Setnie dodaje do interfejsu nowych metod Collection, a jedynie precyzuje wymagania (o tym, co nie powinno zawierać duplikatów). Ponadto z poprzedniego opisu wynika, że ​​nie można po prostu Setuzyskać z niego elementu. Iterator służy do pobierania elementów. Setma kilka dodatkowych interfejsów z nim związanych. Pierwszy z nich to SortedSet. Jak sama nazwa wskazuje, SortedSetoznacza to, że taki zbiór jest posortowany, w związku z czym elementy implementują interfejs Comparablelub są określone Comparator. Ponadto SortedSetoferuje kilka ciekawych metod: Ponadto istnieją metody first(najmniejszy element według wartości) i last(największy element według wartości). Jest SortedSetspadkobierca - NavigableSet. Celem tego interfejsu jest opisanie metod nawigacji potrzebnych do dokładniejszej identyfikacji odpowiednich elementów. Ciekawostką jest NavigableSetto, że dodaje do zwykłego iteratora (który przechodzi od najmniejszego do największego) iterator dla odwrotnej kolejności - descendingIterator. Dodatkowo NavigableSetumożliwia zastosowanie metody descendingSetuzyskania obrazu siebie (View), w którym elementy są ułożone w odwrotnej kolejności. Nazywa się to View, ponieważ poprzez powstały element można zmienić elementy pierwotnego Set. Oznacza to, że w istocie jest to reprezentacja oryginalnych danych w inny sposób, a nie ich kopia. Co ciekawe, NavigableSetpodobnie jak Queue, może obsługiwać elementy pollFirst(minimalne) i (maksymalne). pollLastOznacza to, że pobiera ten element i usuwa go ze zbioru. Jakie są rodzaje implementacji? Po pierwsze, najsłynniejsza implementacja opiera się na kodzie skrótu – HashSet . Inna, równie znana implementacja oparta jest na czerwono-czarnym drzewie – TreeSet . Uzupełnijmy nasz diagram: W zbiorach pozostaje uporządkowanie hierarchii – pustelnicy. Co na pierwszy rzut oka stoi na uboczu - java.util.Map.

Mapy

Mapy to struktura danych, w której dane są przechowywane według klucza. Kluczem może być na przykład identyfikator lub kod miasta. I to według tego klucza będą wyszukiwane dane. Co ciekawe, karty są wyświetlane osobno. Według twórców (zobacz „ Często zadawane pytania dotyczące projektowania API kolekcji Java ”), mapowanie klucz-wartość nie jest kolekcją. Mapy można szybciej traktować jako zbiór kluczy, zbiór wartości, zbiór par klucz-wartość. To takie interesujące zwierzę. Jakie metody zapewniają karty? Przyjrzyjmy się interfejsowi Java API java.util.Map . Ponieważ Ponieważ mapy nie są kolekcjami (nie dziedziczą z kolekcji), nie zawierają pliku contains. I to jest logiczne. Mapa składa się z kluczy i wartości. Które z nich warto sprawdzić metodą containsi jak się nie pomylić? Dlatego interfejs Mapma dwie różne wersje: containsKey(zawiera klucz) i containsValue(zawiera wartość). Jego użycie keySetpozwala na zdobycie kompletu kluczy (tego samego Set). Za pomocą tej metody valuesmożemy uzyskać zbiór wartości na mapie. Klucze na mapie są unikalne, co podkreśla struktura danych Set. Wartości mogą się powtarzać, co podkreśla struktura danych Kolekcji. Dodatkowo za pomocą tej metody entrySetmożemy uzyskać zbiór par klucz-wartość. Więcej o tym, jakie implementacje kart występują, przeczytasz w najbardziej szczegółowych analizach:

• " Struktury danych na obrazkach. HashMap "
• " Struktury danych na zdjęciach. LinkedHashMap "
• „ Wewnętrzne działanie HashMap w Javie (aktualizacja dla Java 8) ”

Chciałbym także zobaczyć, co jest HashMapbardzo podobne do HashSet, i TreeMapdo TreeSet. Mają nawet podobne interfejsy: NavigableSetzarówno NavigableMap, SortedSetjak i SortedMap. Zatem nasza ostateczna mapa będzie wyglądać następująco: Możemy zakończyć ciekawostką, że kolekcja Setwewnętrznie korzysta z Map, gdzie wartości dodane są kluczami, a wartość jest wszędzie taka sama. Jest to interesujące, ponieważ Mapnie jest to kolekcja i zwraca Set, która jest kolekcją, ale w rzeczywistości jest zaimplementowana jako Map. Trochę surrealistyczne, ale tak wyszło)

Wniosek

Dobra wiadomość jest taka, że ​​ta recenzja kończy się w tym miejscu. Zła wiadomość jest taka, że ​​jest to artykuł bardzo recenzyjny. Każda implementacja każdej z kolekcji zasługuje na osobny artykuł, a także na każdy ukryty przed naszymi oczami algorytm. Ale celem tej recenzji jest przypomnienie, czym one są i jakie są połączenia między interfejsami. Mam nadzieję, że po wnikliwej lekturze uda Wam się narysować z pamięci schemat zbiorów. No i tradycyjnie kilka linków:

• „ Szlak Wyroczni: Kolekcje ”
• „ Samouczek IBM: Kolekcje Java ”
• " Yuri Tkach: Zaawansowana Java - Kolekcje "
• „ Zbiory Java: Przebudzenie Mocy autorstwa Raoula-Gabriela Urmy i Richarda Warburtona ”
• " Timur Batyrshinov: 22 - Podstawy języka Java. Kolekcje (i następujące filmy z listy odtwarzania) "
• „ Pięć rzeczy, których nie wiedziałeś o… interfejsie API Java Collections ”

#Wiaczesław