Analiza pytań i odpowiedzi z rozmów kwalifikacyjnych dla programisty Java. Część 9

Sztuczne ognie! Bycie programistą nie jest łatwe. Trzeba się ciągle uczyć, zawsze uczyć się czegoś nowego. Ale jak w każdym innym biznesie, najtrudniej jest zacząć, zrobić pierwszy krok w stronę celu. A ponieważ siedzisz na tej stronie i czytasz ten artykuł, wykonałeś pierwszy krok. Oznacza to, że teraz musisz celowo zmierzać do celu, nie zwalniając ani nie skręcając po drodze. Jeśli dobrze rozumiem, Twoim celem jest zostanie programistą Java lub poszerzenie swojej wiedzy, jeśli nim jesteś. Jeśli tak, to jesteś we właściwym miejscu, ponieważ będziemy nadal analizować obszerną listę ponad 250 pytań do wywiadu z programistą Java. Kontynuujmy!

Kolekcje

84. Opowiedz nam o iteratorach i ich zastosowaniu

Kolekcje to jeden z ulubionych tematów rozmów kwalifikacyjnych z programistami Java, a gdy mowa o hierarchii kolekcji, kandydaci często mówią, że zaczyna się od interfejsu kolekcji . Ale to nieprawda, ponieważ nad tym interfejsem znajduje się inny - Iterable . Ten interfejs reprezentuje metodę iterator() , która umożliwia wywołanie obiektu Iterator dla bieżącej kolekcji. A czym dokładnie jest ten obiekt Iteratora ? Iterator to obiekt, który umożliwia poruszanie się po kolekcji i iterację po elementach bez konieczności znajomości implementacji konkretnej kolekcji przez użytkownika. Oznacza to, że jest to swego rodzaju wskaźnik do elementów kolekcji, który niejako patrzy w nią na określone miejsce. Iterator ma następujące metody:

• hasNext() - zwraca true jeśli za wskaźnikiem znajduje się element (metoda ta pozwala sprawdzić czy osiągnięto koniec kolekcji);
• next() - zwraca następny element po wskaźniku. Jeśli go nie ma, zgłaszany jest wyjątek NoSuchElementException . Oznacza to, że przed użyciem tej metody lepiej upewnić się, że element istnieje - używając funkcji hasNext() ;
• usuń() - usuwa ostatni element otrzymany z kolekcji metodą next() . Jeśli funkcja next() nie została nigdy wywołana przed wywołaniem funkcji Remove() , zostanie zgłoszony wyjątek - IllegalStateException ;
• forEachRemaining(<Consumer>) - wykonuje przekazaną akcję na każdym elemencie kolekcji (metoda pojawiła się w Javie 8).

Oto mały przykład iteracji po liście i usuwania wszystkich jej elementów przy użyciu omówionych metod iteratora:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

W konsoli wyświetli się: Oznacza to, że usunięcie elementów przebiegło pomyślnie. Kiedy już mieliśmy iterator, mogliśmy użyć metody wydrukowania wszystkich elementów na ekranie:

iterator.forEachRemaining(x -> System.out.print(x));

Ale po tym iterator stałby się nieodpowiedni do dalszego użycia, ponieważ przemierzyłby całą listę, a zwykły iterator nie ma metod cofania się. Tutaj stopniowo zbliżamy się do LinkedList , a mianowicie do jej metody listIterator() , która zwraca unowocześniony typ iteratora - ListIterator . Oprócz zwykłych (standardowych) metod iteratora, ta ma dodatkowe:

• add(<Element>) - wstawia nowy element do listy;
• hasPrevious() - zwraca true jeśli przed wskaźnikiem znajduje się element (o ile istnieje element poprzedzający);
• nextIndex() - zwraca indeks na liście kolejnego elementu po wskaźniku;
• poprzedni() - zwraca poprzedni element (do wskaźnika);
• poprzedniIndeks() - zwraca indeks poprzedniego elementu;
• set(<Element>) - Zastępuje ostatni element zwrócony przez metodę next() lub poprzedni() .

Jak widać funkcjonalność tego iteratora jest znacznie ciekawsza: pozwala poruszać się w obu kierunkach i uwalnia ręce podczas pracy z elementami. Ponadto, gdy ludzie mówią o iteratorach, czasami mają na myśli sam wzorzec. Aby uniknąć kłopotów i mówić o tym przekonująco, przeczytaj ten artykuł o wzorcu Iterator .

85. Jaka jest hierarchia kolekcji w Java Collection Framework?

W Javie istnieją dwie hierarchie kolekcji. Pierwsza hierarchia to sama hierarchia Kolekcji o następującej strukturze: Ta z kolei jest podzielona na następujące podkolekcje:

• Zbiór to interfejs opisujący taką strukturę danych jako zbiór zawierający nieuporządkowane, unikalne (niepowtarzające się) elementy. Interfejs ma standardowe implementacje - TreeSet , HashSet i LinkedHashSet .
• Lista to interfejs opisujący strukturę danych przechowującą uporządkowaną sekwencję obiektów. Instancje zawarte na liście można wstawiać i usuwać za pomocą ich indeksu w tej kolekcji (analogicznie do tablicy, ale z dynamiczną zmianą rozmiaru). Interfejs ma standardowe implementacje - ArrayList , Vector ( uważane za przestarzałe i faktycznie nieużywane ) i LinkedList .
• Kolejka to interfejs opisujący strukturę danych przechowującą elementy w formie kolejki zgodnej z zasadą FIFO – First In First Out . Interfejs ma następujące standardowe implementacje: LinkedList (tak, implementuje również Queue ) i PriotityQueue .

Drugą hierarchią kolekcji jest Mapa , która ma następującą strukturę: W tej kolekcji nie ma podziałów na podzbiory (ponieważ sama hierarchia Map jest czymś w rodzaju podkolekcji, tyle że leży osobno). Standardowe implementacje map to Hashtable (uważane za przestarzałe), LinkedHashMap i TreeMap . Właściwie, gdy pytamy o Collection , zwykle mamy na myśli obie hierarchie.

86. Jaka jest wewnętrzna struktura listy ArrayList?

ArrayList jest podobna do tablicy, ale ma możliwość dynamicznego rozszerzania. Co to znaczy? Faktem jest, że ArrayList działa w oparciu o zwykłą tablicę, czyli przechowuje elementy w wewnętrznej tablicy (jej domyślny rozmiar to 10 komórek). Gdy tablica wewnętrzna się zapełni, tworzona jest nowa tablica, której wielkość określa wzór:

<размерТекущегоМассива> * 3 / 2  + 1

Oznacza to, że jeśli rozmiar naszej tablicy wynosi 10, to rozmiar nowej będzie wynosił: 10 * 3 / 2 + 1 = 16. Następnie kopiowane są do niej wszystkie wartości z pierwszej (starej) tablicy za pomocą metody natywna metoda System.arraycopy () i pierwsza tablica jest usuwana. Właściwie w ten sposób implementowana jest dynamiczna rozszerzalność ArrayList . Przyjrzyjmy się najczęściej używanym metodom ArrayList : 1. add(<Elelement>) - dodaje element na koniec tablicy (do ostatniej pustej komórki) i najpierw sprawdza, czy w tej tablicy jest miejsce. Jeśli go nie ma, tworzona jest nowa tablica, do której kopiowane są elementy. Złożoność logarytmiczna tej operacji wynosi O(1). Istnieje podobna metoda - add(<Index>,<Elelement>) . Dodaje element nie na końcu listy (tablicy), ale do konkretnej komórki z indeksem, który przyszedł jako argument. W tym przypadku złożoność logarytmiczna będzie się różnić w zależności od tego, gdzie zostanie dodana:

• jeśli to był w przybliżeniu początek listy, złożoność logarytmiczna będzie bliska O(N), ponieważ wszystkie elementy znajdujące się na prawo od nowego będą musiały zostać przesunięte o jedną komórkę w prawo;
• jeśli element jest wstawiony pośrodku - O(N/2) ponieważ musimy przesunąć tylko połowę elementów listy o jedną komórkę w prawo.

Oznacza to, że złożoność logarytmiczna tej metody waha się od O(N) do O(1) w zależności od miejsca wstawienia elementu. 2. set(<Indeks>,<Element>) - zapisuje element na określoną pozycję na liście. Jeżeli na tej pozycji znajduje się już element, nadpisuje go. Złożoność logarytmiczna tej operacji wynosi O(1), ponieważ nie ma przesunięć: jedynie wyszukiwanie po indeksie w tablicy, która jak pamiętamy ma złożoność O(1) i zapisywanie elementu. 3. usuń(<indeks>) - usunięcie elementu po jego indeksie w tablicy wewnętrznej. Usuwając pozycję, która nie znajduje się na końcu listy, należy przesunąć wszystkie pozycje po jej prawej stronie o jedną komórkę w lewo, aby zamknąć lukę pozostałą po usunięciu pozycji. Zatem złożoność logarytmiczna będzie taka sama jak add(<Index>,<Elelement>) jeśli element był w środku - O(N/2) - bo trzeba przesunąć połowę elementów o jeden w lewo. Odpowiednio, jeśli tak było na początku - O(N). Cóż, jeśli na końcu jest to O(1), to nie musisz niczego przesuwać. Dla chcących zagłębić się w ten temat zostawiam link do artykułu z analizą klasy ArrayList .

87. Jaka jest wewnętrzna struktura LinkedList?

Jeśli ArrayList zawiera elementy w tablicy wewnętrznej, wówczas LinkedList ma postać podwójnie połączonej listy. Oznacza to, że każdy element zawiera link do poprzedniego elementu ( poprzedni ) i następnego ( następny ). Pierwszy element nie ma linku do poprzedniego (jest pierwszym), ale jest uważany za nagłówek listy, a LinkedList ma bezpośredni link do niego. Ostatni element tak naprawdę nie ma kolejnego elementu, jest końcem listy i dlatego w samej LinkedList znajduje się bezpośrednie łącze do niego . Dlatego logarytmiczna złożoność dostępu do początku lub końca listy wynosi O(1). W ArrayList, gdy lista rosła, zwiększała się wewnętrzna tablica, ale tutaj wszystko dzieje się prościej - podczas dodawania elementu po prostu zmienia się kilka linków. Przyjrzyjmy się niektórym z najczęściej używanych metod LinkedlList : 1. add(<Elelement>) - dodanie na końcu listy, tj. po ostatnim elemencie (5) zostanie dodany link do nowego elementu jako następny . Nowy element będzie miał łącze do ostatniego (5) tak jak poprzedni element. Logarytmiczna złożoność takiej operacji wyniesie O(1), ponieważ potrzebne jest tylko łącze do ostatniego elementu, a jak pamiętasz, ogon ma bezpośrednie połączenie z LinkedList , a logarytmiczna złożoność dostępu do niego jest minimalna. 2. add(<Indeks>,<Element>) - dodanie elementu według indeksu. Podczas dodawania elementu na przykład na środek listy elementy z początku i końca (po obu stronach) są najpierw iterowane, aż do znalezienia żądanego miejsca. Jeśli chcemy wstawić element pomiędzy trzecim a czwartym (na powyższym rysunku), to przy szukaniu odpowiedniego miejsca kolejne łącze trzeciego elementu będzie już wskazywało nowy. W przypadku nowego poprzedni link będzie wskazywał trzeci. W związku z tym łącze czwartego elementu – poprzedni – będzie już wskazywało nowy element, a kolejne łącze nowego elementu będzie wskazywało element czwarty: Złożoność logarytmiczna tej metody będzie zależała od indeksu nadanego nowemu elementowi:

• jeśli jest blisko głowy lub ogona, zbliży się do O(1), ponieważ w rzeczywistości nie będzie konieczne iterowanie po elementach;
• jeśli jest blisko środka, to O(N/2) - elementy z głowy i ogona będą sortowane jednocześnie, aż do znalezienia żądanego elementu.

3. set(<Indeks>,<Element>) - zapisuje element na określoną pozycję na liście. Logarytmiczna złożoność tej operacji będzie wynosić od O(1) do O(N/2), ponownie w zależności od tego, jak blisko elementu znajduje się głowa, ogon lub środek. 4. usuń(<indeks>) - usuwa element z listy, zasadniczo sprawiając, że element znajdujący się przed usuwanym ( poprzedni ) odnosi się do elementu, który pojawia się po usuwanym ( następny ). I odwrotnie: tak aby element następujący po usuwanym odnosił się do elementu poprzedzającego usuwany: W rezultacie powstaje proces odwrotny do dodawania według indeksu ( add(<Index>,<Elelement>) ). Tym, którzy chcą dowiedzieć się więcej o wewnętrznej strukturze LinkedList , polecam przeczytanie tego artykułu .

88. Jaka jest wewnętrzna struktura HashMap?

Być może jedno z najpopularniejszych pytań podczas rozmowy kwalifikacyjnej z programistą Java. HashMap v działa z parami klucz-wartość . W jaki sposób są one przechowywane w samym HashMapv ? Wewnątrz HashMap znajduje się tablica węzłów:

Node<K,V>[] table

Domyślnie rozmiar tablicy wynosi 16 i podwaja się przy każdym zapełnieniu jej elementami (po osiągnięciu LOAD_FACTOR - określony procent zapełnienia, domyślnie jest to 0,75 ). Każdy węzeł przechowuje skrót klucza, klucz, wartość i link do następnego elementu: Właściwie „link do następnego elementu” oznacza, że ​​mamy do czynienia z pojedynczo połączoną listą, gdzie każdy element zawiera link do Następny. Oznacza to, że HashMap przechowuje dane w tablicy pojedynczo połączonych list. Ale od razu zauważę: gdy jedna komórka tablicy tabeli ma link do podobnej, pojedynczo połączonej listy składającej się z więcej niż jednego elementu, nie jest to dobre. Zjawisko to nazywa się kolizją . Ale najpierw sprawy. Zobaczmy, jak zapisuje się nową parę za pomocą metody put . Najpierw pobierana jest funkcja hachCode() klucza. Dlatego, aby hashmap działał poprawnie , musisz wziąć klasy, w których ta metoda jest nadpisana jako klucze. Ten kod skrótu jest następnie używany w metodzie wewnętrznej – hash() – w celu określenia liczby mieszczącej się w rozmiarze tablicy tabeli . Następnie za pomocą otrzymanego numeru uzyskuje się dostęp do określonej komórki tablicy tabeli . Tutaj mamy dwa przypadki:

1. Komórka jest pusta - zapisywana jest w niej nowa wartość Node .
2. Komórka nie jest pusta - porównywana jest wartość kluczy. Jeśli są równe, nowa wartość Node nadpisuje starą, jeśli nie są równe, uzyskiwany jest dostęp do następnego elementu i porównywany z jego kluczem... I tak dalej, aż nowa wartość nadpisze starą lub osiągnie koniec pojedynczo połączona lista i będzie tam przechowywana jako ostatni element.

Podczas wyszukiwania elementu po kluczu ( metoda get(<key>) ) obliczany jest hashCode klucza, następnie jego wartość w tablicy za pomocą hash() i na podstawie otrzymanej liczby zostaje znaleziona komórka tablicy tablicy , w którym wyszukiwanie odbywa się już poprzez wyliczenie węzłów i porównanie klucza żądanego węzła z kluczem bieżącego. Operacje na Mapie w idealnej sytuacji mają złożoność algorytmiczną O(1), ponieważ uzyskują dostęp do tablicy, a jak pamiętasz, niezależnie od liczby elementów, operacje na tablicy mają złożoność O(1). Ale to jest idealne. Gdy używana komórka tablicy nie jest pusta (2) i jest już w niej kilka węzłów, złożoność algorytmiczna zamienia się w liniowe O(N), ponieważ teraz konieczne jest iterowanie po elementach przed znalezieniem odpowiedniego miejsca. Nie mogę nie wspomnieć o tym: począwszy od Java 8, jeśli pojedynczo połączony węzeł listy ma więcej niż 8 elementów (kolizje), zamienia się w drzewo binarne. W tym przypadku złożoność algorytmiczna nie będzie już wynosić O(N), ale O(log(N)) - to już inna sprawa, prawda? HashMap to duży temat i ludzie lubią zadawać pytania na ten temat podczas wywiadów. Dlatego radzę dokładnie to zrozumieć (aby odbiło się od zębów). Osobiście nie odbyłem rozmowy kwalifikacyjnej bez pytań HashMap . W tym artykule możesz znaleźć szczegółowe informacje na temat HashMap . To tyle na dziś, ciąg dalszy...