O co mogą zapytać na rozmowie kwalifikacyjnej: Struktury danych w Javie. Część 2

CZĘŚĆ 1 Mówimy teraz o podstawach, które powinien znać każdy programista Java. O tej klasycznej wiedzy, od której wszystko się zaczyna. Dzisiaj chciałbym poruszyć jeden z podstawowych tematów wszelkich struktur danych wywiadu w Javie . Zamiast więc owijać w bawełnę, zacznijmy. Łap kontynuację listy pytań, jakie możesz zadać na ten temat podczas rozmowy kwalifikacyjnej.

6. Opowiedz nam o Liście

Lista to interfejs reprezentujący uporządkowaną strukturę obiektów, który nazywa się listą. „Sztuczka” tej struktury polega na tym, że elementy zawarte w Liście można wstawiać, modyfikować lub usuwać za pomocą indeksu, czyli wewnętrznego identyfikatora Listy . Inaczej mówiąc, indeks oznacza: „ile elementów jest od początku listy”. Pierwszy element List ma indeks 0, drugi ma indeks 1 i tak dalej. Zatem piąty element jest oddalony o cztery elementy od początku listy. Jak wspomniano powyżej, kolejność dodawania pozycji do listy jest ważna. Dlatego struktura danych nazywa się listą . Podajemy metody unikalne dla tej struktury, które mają na celu pracę z elementami według indeksu:

• get - zwraca element na podanej pozycji (według wartości indeksu),
• usuń - usuwa element z podanej pozycji,
• set - zastępuje element na określonej pozycji elementem określonym w metodzie.

Główne implementacje to ArrayList i LinkedList . Porozmawiamy o nich więcej nieco później. Vector to lista bezpieczna dla wątków, więc każda metoda w tej klasie jest synchronizowana. Pamiętaj jednak, że jeśli chcesz zabezpieczyć niektóre akcje na liście, będziesz synchronizować całą sekwencję operacji. Synchronizowanie poszczególnych operacji jest zarówno mniej bezpieczne, jak i znacznie wolniejsze. Oczywiście Vector ma również blokadę nad głową, nawet jeśli nie potrzebujesz zamka. Dlatego ta klasa jest obecnie uważana za przestarzałą i nie jest używana. Przy okazji: ArrayList jest podobny do Vector , ale nie używa blokowania, więc jest używany wszędzie. Stack jest podklasą klasy Vector z jednym domyślnym konstruktorem i wszystkimi metodami klasy Vector oraz kilkoma własnymi (porozmawiamy o nich później). Jako przykład możesz sobie wyobrazić ten proces jako stos folderów z dokumentami. Umieszczasz jeden folder na górze stosu i możesz je przenosić tylko w odwrotnej kolejności, zaczynając od góry. Właściwie jest to mechanizm typu LIFO , czyli Last In First Out , ostatni który przyjdzie, ten pierwszy wyjdzie. Stos implementuje własne metody:

• push - dodaje przekazany element na górę stosu;
• peek - zwraca element znajdujący się na szczycie stosu;
• pop - również zwraca element znajdujący się na górze stosu, ale go usuwa;
• pusty – sprawdza, czy stos jest pusty – prawda czy nie – fałsz ;
• search - przeszukuje stos pod kątem danego elementu. Jeśli element zostanie znaleziony, zwracany jest jego numer kolejny względem wierzchołka stosu. Jeżeli element nie zostanie znaleziony, zwracana jest wartość -1.

W tej chwili podklasa Stack nie jest właściwie używana ze względu na jej prostotę i brak elastyczności, ale mimo to możesz ją spotkać. Na przykład, gdy pojawi się jakiś błąd i w konsoli zobaczysz stos komunikatów na jego temat. Więcej o stosie i kolejce możesz przeczytać w tym artykule .

7. Opowiedz nam o Mapie

Jak wspomniano powyżej, mapa to kolekcja posiadająca odrębną strukturę interfejsów i ich implementacji. Jest oddzielny, ponieważ tutaj wartości nie są przechowywane pojedynczo, ale w parze „klucz-wartość”. Podstawowe metody map :

• put(klawisz K, wartość V) - dodanie elementu do Mapy;
• get(Object key) - szukaj wartości według klucza;
• zawieraKey(Object key) — sprawdza Mapę pod kątem obecności tego klucza;
• zawieraValue(Wartość obiektu) - sprawdza Mapę pod kątem obecności tej wartości;
• usuń(obiekt klucz) - usunięcie wartości według jej klucza.

Jak widać, większość operacji odbywa się za pomocą klawisza. Z reguły jako klucze wybierane są obiekty niezmienne . Typowym przykładem tego obiektu jest String . Podstawowe implementacje map :

1. HashMap - przeznaczony do przechowywania wartości w losowej kolejności, ale pozwala na szybkie wyszukiwanie elementów mapy. Umożliwia określenie klucza za pomocą słowa kluczowego null , ale nie więcej niż raz, ponieważ pary z tymi samymi kluczami są zapisane jeden na drugim. Głównym warunkiem jest unikalność kluczy: wartości można powtarzać (może być kilka wartości null).
2. LinkedHashMap to odpowiednik HashMap , który przechowuje wartości w kolejności, w jakiej zostały dodane. W związku z tym, podobnie jak LinkedList , ma nagłówek - głowę podwójnie połączonej listy. Po zainicjowaniu wskazuje na siebie.

   LinkedHashMap ma również accessOrder , który określa sposób dostępu do elementów, gdy używany jest iterator. Jeżeli accessOrder ma wartość false, dostęp zostanie wykonany w kolejności wstawiania elementów. Jeśli ma wartość true, elementy będą uporządkowane w kolejności, do której ostatnio uzyskiwano dostęp (element, do którego ostatnio uzyskiwano dostęp, zostanie umieszczony na końcu).

3. TreeMap to mapa , która sortuje elementy według wartości kluczy. Podobny do TreeSet , ale dla par w oparciu o wartości kluczy. Aby ustawić reguły sortowania TreeMap , klucze muszą implementować interfejs Comparable . W przeciwnym razie powinien istnieć Komparator zorientowany na klucz (ten, który jest określony w konstruktorze TreeMap ), TreeSet - zaimplementowany z obiektem TreeMap w środku, w którym tak naprawdę dzieje się cała magia.

   Więcej o sortowaniu w TreeMap przy użyciu czerwono-czarnych drzew przeczytasz w artykule o możliwościach TreeMap .

4. Hashtable jest podobny do HashMap , ale nie pozwala na przechowywanie wartości null jako kluczy lub wartości. Jest starannie zsynchronizowany z wielowątkowego punktu widzenia, co z kolei oznacza, że ​​jest bezpieczny z wielowątkowego punktu widzenia. Ale ta implementacja jest przestarzała i powolna, więc teraz nie zobaczysz Hashtable w mniej lub bardziej nowych projektach.

8. ArrayList vs LinkedList. Którego z nich najlepiej używać?

To pytanie jest prawdopodobnie najbardziej popularne w przypadku struktur danych i niesie ze sobą pewne pułapki. Zanim odpowiemy, dowiedzmy się więcej o tych strukturach danych. ArrayList implementuje interfejs List i działa na wewnętrznej tablicy, która jest rozwijana w razie potrzeby. Kiedy tablica wewnętrzna jest całkowicie wypełniona i trzeba wstawić nowy element, tworzona jest nowa tablica o rozmiarze (oldSize * 1,5) +1. Następnie wszystkie dane ze starej tablicy zostaną skopiowane do nowego + nowego elementu, a stary zostanie usunięty przez moduł zbierający elementy bezużyteczne . Metoda add dodaje element do ostatniej pustej komórki tablicy. Oznacza to, że jeśli mamy tam już 3 elementy, doda kolejny do czwartej komórki. Przejdźmy do wykonania podstawowych metod:

• get(int indeks) - pobranie elementu tablicy według indeksu jest najszybsze w O(1) ;
• add(Object obj) - jeśli w tablicy wewnętrznej jest wystarczająco dużo miejsca na nowy element, to przy normalnym wstawieniu zostanie wykorzystany czas O(1) , ponieważ dodawanie jest kierowane do ostatniej komórki.

  Jeśli będziemy musieli utworzyć nową tablicę i skopiować do niej zawartość, to nasz czas będzie wprost proporcjonalny do liczby elementów w tablicy O(n) ;

• usuń(int indeks) - usuwając element np. ze środka, otrzymamy czas O(n/2), gdyż będziemy musieli przesunąć elementy na prawo od niego o jedną komórkę do tyłu. Odpowiednio, jeśli usuwamy od początku listy, to O(n), od końca - O(1);
• add(int indeks, Object obj) - sytuacja podobna do usuwania: przy dodawaniu do środka będziemy musieli przesunąć elementy z prawej strony o jedną komórkę do przodu, więc czas będzie wynosił O(n/2). Oczywiście od początku - O(n), od końca - O(1);
• set(int indeks, Object obj) - tutaj sytuacja jest inna, ponieważ wystarczy znaleźć żądany element i nad nim nadpisać, nie przesuwając reszty, więc O(1).

Przeczytaj więcej o ArrayList w tym artykule . LinkedList implementuje dwa interfejsy jednocześnie - List i Queue , dlatego posiada właściwości i metody właściwe dla obu struktur danych. Z Listy uzyskał dostęp do elementu według indeksu, z Kolejki - obecność „głowy” i „ogona”. Wewnętrznie jest zaimplementowany jako struktura danych reprezentująca podwójnie połączoną listę. Oznacza to, że każdy element ma link do następnego i poprzedniego, z wyjątkiem „ogona” i „głowy”.

• get(int indeks) - szukając elementu znajdującego się w środku listy, rozpoczyna przeszukiwanie wszystkich elementów po kolei, aż do znalezienia żądanego. Logicznie rzecz biorąc, wyszukiwanie powinno zająć O(n/2) , ale LinkedList ma również ogon, więc wyszukiwanie odbywa się jednocześnie z obu stron. Odpowiednio czas zmniejsza się do O(n/4) .

  Jeżeli element znajduje się blisko początku listy lub jej końca, to czas będzie wynosić O(1) ;

• add(Object obj) - podczas dodawania nowego elementu element „ogon” będzie miał link do dodanego kolejnego elementu, a nowy otrzyma link do tego poprzedniego elementu i stanie się nowym „ogonem”. Odpowiednio czas będzie wynosić O(1) ;
• usuń(int indeks) - logika podobna do metody get(int indeks) . Aby usunąć element ze środka listy, należy go najpierw znaleźć. To znowu O(n/4) , podczas gdy samo usunięcie właściwie nic nie bierze, ponieważ zmienia jedynie wskaźnik sąsiednich obiektów (zaczynają się do siebie odnosić). Jeśli element znajduje się na początku lub na końcu, to znowu - O(1) ;
• add(int indeks, obiekt obj) i set(int indeks, obiekt obj) - metody będą miały złożoność czasową identyczną jak get(int indeks) , ponieważ większość czasu spędza się na poszukiwaniu elementu. Zatem dla środka listy - O(n/4) , na początek - O(1).

Więcej informacji na temat pracy z LinkedList opisano w tym artykule . Spójrzmy na to wszystko w tabeli: Jak zapewne już zrozumiałeś, nie da się jednoznacznie odpowiedzieć na to pytanie. Przecież w różnych sytuacjach pracują z różnymi prędkościami. Dlatego też, gdy pojawi się takie pytanie, należy od razu zadać sobie pytanie, na czym będzie skupiać się ta lista i jakie operacje będą najczęściej wykonywane. Zaczynając od tego, udziel odpowiedzi, ale z wyjaśnieniem, dlaczego tak jest. Podsumujmy nasze porównanie: ArrayList:

• najlepszy wybór, jeśli najczęstszą operacją jest wyszukiwanie elementu, nadpisywanie elementu;
• najgorszy wybór jeśli operacja polega na wstawieniu i usunięciu na początku-środku, ponieważ nastąpią operacje przesunięcia elementów po prawej stronie.

Połączona lista:

• najlepszy wybór jeśli naszą częstą operacją jest wstawianie i usuwanie na początku-środku;
• najgorszy wybór, jeśli najczęstszą operacją jest wyszukiwanie.

9. W jaki sposób elementy są przechowywane w HashMap?

Kolekcja HashMap zawiera wewnętrzną tablicę Node[] table , której komórki nazywane są także segmentami . Węzeł zawiera:

• klucz - link do klucza,
• wartość - odniesienie do wartości,
• hash - wartość skrótu,
• next -link do następnego węzła .

Jedna komórka tablicy table[] może zawierać odwołanie do obiektu Node z łączem do następnego elementu Node , może zawierać łącze do innego elementu Node itd. W rezultacie te elementy Node mogą tworzyć pojedynczo połączona lista zawierająca elementy z łączem do następnej. W tym przypadku wartość skrótu elementów tego samego łańcucha jest taka sama. Po krótkiej dygresji przyjrzyjmy się, jak elementy są przechowywane w HashMap :

1. Klucz jest sprawdzany pod kątem wartości null . Jeśli ma wartość null , klucz zostanie zapisany w komórce table[0] , ponieważ kod skrótu dla wartości null wynosi zawsze 0.
2. Jeśli klucz nie ma wartości null , wywoływana jest metoda hashcode() obiektu klucza , która zwróci jego kod skrótu. Ten kod skrótu służy do określenia komórki tablicy, w której będzie przechowywany obiekt Node.
3. Następnie ten kod skrótu jest umieszczany w wewnętrznej metodzie hash() , która oblicza kod skrótu, ale w rozmiarze tablicy table[] .
4. Następnie, w zależności od wartości skrótu, Node umieszczany jest w określonej komórce tablicy table [] .
5. Jeśli komórka table[] użyta do zapisania bieżącego elementu Node nie jest pusta, ale zawiera już jakiś element, wówczas elementy Node są iterowane po kolejnej wartości , aż do osiągnięcia ostatniego elementu. Oznacza to, że ten, którego następne pole ma wartość null .

   Podczas tego wyszukiwania klucz chronionego obiektu Node jest porównywany z kluczami przeszukiwanych obiektów:

   • jeżeli zostanie znalezione dopasowanie, wyszukiwanie zostanie zakończone, a nowy Węzeł nadpisze Węzeł , w którym znaleziono dopasowanie (nadpisane zostanie jedynie pole jego wartości );
   • jeśli nie zostaną znalezione żadne kluczowe dopasowania, nowy węzeł stanie się ostatnim na tej liście, a poprzedni będzie miał do niego następny link.

Podczas rozmów kwalifikacyjnych często pojawia się pytanie: czym jest konflikt ? Sytuację, w której komórka tablicy table[] przechowuje nie jeden element, ale łańcuch dwóch lub więcej, nazywa się kolizją . W normalnych przypadkach, gdy w pojedynczej komórce table[] przechowywany jest tylko jeden element , dostęp do elementów HashMap ma stałą złożoność czasową O(1) . Ale gdy komórka z żądanym elementem zawiera łańcuch elementów ( kolizja ), to O(n) , ponieważ w tym przypadku czas jest wprost proporcjonalny do liczby sortowanych elementów.

10. Wyjaśnij iterator

Na powyższym diagramie mapowania hierarchii kolekcji interfejs kolekcji był miejscem, w którym zaczynała się cała hierarchia, ale w praktyce nie do końca tak jest. Kolekcja dziedziczy po interfejsie za pomocą metody iterator() , która zwraca obiekt implementujący interfejs Iterator<E> . Interfejs Iteratora wygląda następująco:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - wywołując tę ​​metodę można uzyskać kolejny element. hasNext() - pozwala dowiedzieć się, czy jest następny element i czy osiągnięto koniec kolekcji. A gdy nadal są elementy, hasNext() zwróci true . Zwykle metoda hasNext() jest wywoływana przed metodą next() , ponieważ next() zgłosi wyjątek NoSuchElementException , gdy osiągnie koniec kolekcji . usuń() – Usuwa element pobrany przez ostatnie wywołanie metody next() . Celem Iteratora jest iteracja po elementach. Na przykład:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

W rzeczywistości pętla for-each jest implementowana pod maską za pomocą iteratora. Więcej na ten temat możesz przeczytać tutaj . List udostępnia własną wersję iteratora, ale fajniejszą i bardziej wyrafinowaną - ListIterator . Interfejs ten rozszerza Iterator i posiada dodatkowe metody:

• hasPrevious zwróci wartość true, jeśli w kolekcji znajduje się poprzedni element, w przeciwnym razie false;
• poprzedni zwraca bieżący element i przechodzi do poprzedniego; jeśli go nie ma, zgłaszany jest wyjątek NoSuchElementException;
• add wstawi przekazany obiekt przed elementem, który ma zostać zwrócony przez następne wywołanie next () ;
• set przypisuje bieżącemu elementowi referencję do przekazanego obiektu;
• nextIndex zwraca indeks następnego elementu. Jeśli czegoś takiego nie ma, zwracany jest rozmiar listy;
• poprzedniIndeks zwraca indeks poprzedniego elementu. Jeśli go nie ma, zwracana jest liczba -1.

Cóż, to wszystko dla mnie dzisiaj. Mam nadzieję, że po przeczytaniu tego artykułu jesteś jeszcze bliżej swojego ukochanego marzenia - zostania programistą.