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:
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.Collection
ma 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
Collection
jest 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ą
AbstractCollection
metody takie jak
contains
,
toArray
.
remove
A 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,
List
zna indeks elementu. Pozwala to uzyskać (
get
) element według indeksu lub ustawić wartość dla określonego indeksu (
set
).
add
Metody zbierania
addAll
pozwalają
remove
określić indeks, z którego mają zostać wykonane. Dodatkowo y
List
ma 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:
ArrayList
i
LinkedList
. Po pierwsze,
ArrayList
jest 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,
LinkedList
jest 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
LinkedList
realizuje „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
LinkedList
są po prostu połączone jak ogniwa łańcucha. Ale
ArrayList
przechowuje 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
LinkedList
elementu, po prostu usuń odniesienia do tego elementu. W przypadku ,
ArrayList
jesteś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:
Po zapoznaniu się z ArrayList nie sposób nie wspomnieć o jego „poprzedniku”, klasie
java.util.Vector . Różni się
Vector
tym
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
Vector
zwiększa swój rozmiar nie 1,5-krotnie,
ArrayList
ale 2-krotnie. W przeciwnym razie zachowanie jest takie samo -
Vector
przechowywanie elementów w postaci tablicy jest ukryte, a dodawanie/usuwanie elementów ma takie same konsekwencje jak w
ArrayList
. Właściwie
Vector
nie 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-out
strukturą 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ę
peek
tł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
push
wypycha (dodaje) nowy element na stos i zwraca go, a metoda elementowa
pop
wypycha (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:
Implementacją
java.util.Deque
moż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
Queue
i
Deque
mają 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
BlockingDeque
implementują 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
Set
wię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,
Set
jest to „kolekcja niezawierająca zduplikowanych elementów”. Co ciekawe, sam interfejs
Set
nie 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
Set
uzyskać z niego elementu. Iterator służy do pobierania elementów.
Set
ma kilka dodatkowych interfejsów z nim związanych. Pierwszy z nich to
SortedSet
. Jak sama nazwa wskazuje,
SortedSet
oznacza to, że taki zbiór jest posortowany, w związku z czym elementy implementują interfejs
Comparable
lub są określone
Comparator
. Ponadto
SortedSet
oferuje kilka ciekawych metod:
Ponadto istnieją metody
first
(najmniejszy element według wartości) i
last
(największy element według wartości). Jest
SortedSet
spadkobierca -
NavigableSet
. Celem tego interfejsu jest opisanie metod nawigacji potrzebnych do dokładniejszej identyfikacji odpowiednich elementów. Ciekawostką jest
NavigableSet
to, że dodaje do zwykłego iteratora (który przechodzi od najmniejszego do największego) iterator dla odwrotnej kolejności -
descendingIterator
. Dodatkowo
NavigableSet
umożliwia zastosowanie metody
descendingSet
uzyskania 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,
NavigableSet
podobnie jak
Queue
, może obsługiwać elementy
pollFirst
(minimalne) i (maksymalne).
pollLast
Oznacza 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ą
contains
i jak się nie pomylić? Dlatego interfejs
Map
ma dwie różne wersje:
containsKey
(zawiera klucz) i
containsValue
(zawiera wartość). Jego użycie
keySet
pozwala na zdobycie kompletu kluczy (tego samego
Set
). Za pomocą tej metody
values
moż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
entrySet
możemy uzyskać zbiór par klucz-wartość. Więcej o tym, jakie implementacje kart występują, przeczytasz w najbardziej szczegółowych analizach:
Chciałbym także zobaczyć, co jest
HashMap
bardzo podobne do
HashSet
, i
TreeMap
do
TreeSet
. Mają nawet podobne interfejsy:
NavigableSet
zarówno
NavigableMap
,
SortedSet
jak i
SortedMap
. Zatem nasza ostateczna mapa będzie wyglądać następująco:
Możemy zakończyć ciekawostką, że kolekcja
Set
wewnętrznie korzysta z
Map
, gdzie wartości dodane są kluczami, a wartość jest wszędzie taka sama. Jest to interesujące, ponieważ
Map
nie 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:
#Wiaczesław
GO TO FULL VERSION