Przeglądanie pytań i odpowiedzi z rozmowy kwalifikacyjnej na stanowisko programisty Java. Część 9

Bycie programistą nie jest łatwe. Zawsze jest coś nowego do nauczenia się. I jak w każdym innym przedsięwzięciu, najtrudniej jest zacząć, zrobić pierwszy krok w stronę celu. Ale skoro już tu jesteś i czytasz ten artykuł, wykonałeś pierwszy krok. Oznacza to, że teraz musisz świadomie zmierzać do celu, nie zwalniając ani nie zbaczając na bok. Zakładam, że Twoim celem jest zostanie programistą Java lub poszerzenie swojej wiedzy, jeśli już jesteś programistą. Jeśli tak, przejdźmy dalej do omówienia obszernej listy pytań do rozmowy kwalifikacyjnej z programistami Java. Kontynuujmy!

Kolekcje

84. Opowiedz nam o iteratorach i sposobie ich użycia

Kolekcje to ulubiony temat każdej rozmowy kwalifikacyjnej z programistą Java. Odpowiadając na pytania dotyczące hierarchii kolekcji, kandydaci często mówią, że zaczyna się od interfejsu Kolekcji . Ale tak nie jest. Poziom wyżej istnieje inny interfejs: Iterable . Interfejs ten składa się z metody iterator() , która umożliwia dostęp do obiektu Iterator dla bieżącej kolekcji. A czym właściwie jest ten obiekt Iteratora ? Obiekt Iterator umożliwia poruszanie się po kolekcji i iterację po jej elementach, a użytkownik nie musi znać konkretnych szczegółów implementacji kolekcji. Inaczej mówiąc, jest to swego rodzaju wskaźnik do elementów kolekcji, jakby zaglądał do środka, na któryś z nich. Iterator posiada metody takie jak:

• hasNext() — zwraca wartość true , jeśli iteracja zawiera inny element (ta metoda informuje, kiedy doszedłeś do końca kolekcji);

• next() — zwraca następny element w iteracji. Jeśli takowego nie ma, zgłaszany jest wyjątek NoSuchElementException . Oznacza to, że przed użyciem tej metody najlepiej jest użyć metody hasNext() , aby upewnić się, że istnieje następny element;

• Remove() — usuwa z kolekcji ostatni otrzymany element metodą next() . Jeśli funkcja next() nigdy nie została wywołana, wywołanie metody Remove() spowoduje zgłoszenie wyjątku IllegalStateException ;

• forEachRemaining(<Consumer>) — wykonuje przekazaną akcję na każdym elemencie kolekcji (metoda ta pojawiła się w Javie 8).

Oto mały przykład iteracji listy i usuwania wszystkich jej elementów przy użyciu różnych metod iteratora, które sprawdziliśmy:

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());

Konsola wyświetli następujące informacje: Oznacza to, że elementy zostały pomyślnie usunięte. Gdy już otrzymasz iterator, możesz użyć metody, aby wyświetlić wszystkie elementy na ekranie:

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

Ale kiedy to zrobimy, iterator staje się nieodpowiedni do dalszego użycia: przeszedł całą listę, a zwykły iterator nie ma metod iteracji wstecz. To stanowi miłe przejście do dyskusji na temat LinkedList , a konkretnie na temat jej metody listIterator() , która zwraca ulepszony typ iteratora: ListIterator . Oprócz metod zwykłego (standardowego) iteratora, ten rodzaj ma następujące cechy:

• add(<Element>) — dodaje nowy element do listy;

• hasPrevious() — zwraca wartość true , jeśli przed kolejnym elementem znajduje się element (jeśli istnieje element poprzedni);

• nextIndex() — zwraca indeks następnego elementu;

• poprzedni() — zwraca element poprzedni (ten przed kolejnym elementem);

• poprzedniIndeks zwraca indeks poprzedniego elementu.

• set(<Element>) — zastępuje ostatni element zwrócony przez next() lub poprzedni() .

Jak widać, iterator ten ma znacznie ciekawszą funkcjonalność: pozwala chodzić w obu kierunkach i zapewnia znaczną swobodę podczas pracy z elementami. Powinieneś także wiedzieć, że gdy ludzie mówią o iteratorach, czasami mają na myśli sam wzorzec projektowy.

85. Jaka hierarchia kolekcji istnieje w Java Collection Framework?

W Javie istnieją dwie hierarchie kolekcji. Pierwszą hierarchią jest hierarchia Kolekcji, która ma następującą strukturę: Jest podzielona na następujące podkolekcje:

• Zestaw to interfejs opisujący zestaw, strukturę danych zawierającą nieuporządkowane, unikalne (niepowtarzające się) elementy. Ten interfejs ma kilka standardowych implementacji: TreeSet , HashSet i LinkedHashSet .

• Lista to interfejs opisujący strukturę danych przechowującą uporządkowaną sekwencję obiektów. Obiekty na liście można wstawiać i usuwać na podstawie ich indeksu na liście (podobnie jak tablica, ale z dynamiczną zmianą rozmiaru). Ten interfejs ma również kilka standardowych implementacji: ArrayList , Vector ( przestarzałe i faktycznie nieużywane ) i LinkedList .

• Kolejka to interfejs opisujący strukturę danych, która przechowuje elementy w kolejce „pierwsze weszło, pierwsze wyszło” (FIFO) . Interfejs ten ma następujące standardowe implementacje: LinkedList (zgadza się, implementuje również Queue ) i PriotityQueue .

Drugą hierarchią kolekcji jest hierarchia Map , która ma następującą strukturę: Ta hierarchia kolekcji nie ma podziału na podkolekcje (ponieważ sama hierarchia Map jest czymś w rodzaju podkolekcji, która wyróżnia się samodzielnie). Standardowe implementacje Map to Hashtable (przestarzałe), LinkedHashMap i TreeMap . W praktyce, gdy ludzie pytają o Kolekcje , zwykle mają na myśli obie hierarchie.

86. Jaka jest wewnętrzna struktura listy ArrayList?

ArrayList przypomina tablicę, ale może się dynamicznie rozwijać . Co to znaczy? Pod maską ArrayList wykorzystuje zwykłą tablicę, tj. przechowuje swoje elementy w wewnętrznej tablicy, której domyślny rozmiar wynosi 10 komórek. Po zapełnieniu tablicy wewnętrznej tworzona jest nowa tablica. Rozmiar nowej tablicy określa się za pomocą następującego wzoru:

<size of the current array> * 3 / 2 + 1

Zatem 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 oryginalnej (starej) tablicy za pomocą wbudowanej funkcji System.arraycopy() , a oryginalna tablica zostanie usunięta. W skrócie, w ten sposób ArrayList implementuje dynamiczną zmianę rozmiaru. Rozważmy najpopularniejsze metody ArrayList : 1. add(<Element>) — dodaje element na koniec tablicy (w ostatniej pustej komórce), po uprzednim sprawdzeniu, czy w tablicy jest dostępna komórka. Jeśli nie, tworzona jest nowa tablica i elementy są do niej kopiowane. Złożoność czasowa tej operacji wynosi O(1). Istnieje podobna metoda add(<Index>, <Elelement>) . Dodaje element nie na końcu listy (tablicy), ale do konkretnej komórki wskazanej przez indeks, który przyszedł jako argument. W takim przypadku złożoność czasowa będzie się różnić w zależności od tego, gdzie dodasz:

• jeśli dodanie będzie blisko początku listy, to złożoność czasowa 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 zostanie wstawiony na środku, będzie to O(N/2), ponieważ wystarczy przesunąć połowę pozycji listy o jedną komórkę w prawo.

Oznacza to, że złożoność czasowa tej metody waha się od O(1) do O(N), w zależności od miejsca wstawienia elementu. 2. set(<Index>, <Element>) — zapisuje element na określoną pozycję na liście. Jeśli element znajduje się już na tej pozycji, metoda nadpisuje go. Złożoność czasowa tej operacji wynosi O(1), ponieważ nie wymaga ona żadnych operacji przesunięcia: po prostu używamy indeksu do obliczenia adresu komórki w tablicy, która ma złożoność O(1), a następnie zapisujemy nowy element . 3. usuń(<indeks>) — usuwa element według jego indeksu w tablicy wewnętrznej. Usuwając pozycję, która nie znajduje się na końcu listy, wszystkie pozycje na prawo od usuniętej należy przesunąć o jedną komórkę w lewo, aby zapełnić lukę powstałą po usunięciu. W związku z tym złożoność czasowa będzie taka sama jak w przypadku add(<Index>, <Element>) , gdy w środku zostanie dodany element: O(N/2). W końcu musisz przesunąć połowę elementów o jedną komórkę w lewo. A jeśli mówimy o początku, to O(N). Lub jeśli na końcu, to O(1), ponieważ nie musisz niczego przesuwać.

87. Jaka jest wewnętrzna struktura LinkedList?

ArrayList zawiera elementy w tablicy wewnętrznej, ale LinkedList przechowuje je na podwójnie połączonej liście . Oznacza to, że każdy element zawiera łącze do poprzedniego elementu i do następnego elementu. Pierwszy element nie łączy się z poprzednim elementem (w końcu jest pierwszym). Jest również uważany za głowę listy, a obiekt LinkedList ma do niego bezpośrednie odniesienie. Podobnie ostatni element nie ma następnego elementu, ponieważ jest końcem listy. Obiekt LinkedList również odwołuje się do niego bezpośrednio. Oznacza to, że złożoność czasowa dostępu do początku lub końca listy wynosi O(1). W ArrayList , jeśli lista rośnie, rośnie także tablica wewnętrzna. Tutaj wszystko jest prostsze: dodanie referencji jest tak proste, jak zmiana kilku linków. Przyjrzyjmy się niektórym najczęściej stosowanym metodom LinkedList : 1. add(<Element>) — dodaje element na koniec listy, czyli po ostatnim elemencie (5) jako następny zostanie dodany link do nowego elementu . Poprzednie odwołanie w nowym elemencie będzie wskazywało element (5), który teraz go poprzedza na liście. Złożoność czasowa tej operacji wynosi O(1), ponieważ potrzebujemy tylko połączenia z ostatnim elementem, a jak pamiętasz, obiekt LinkedList ma bezpośrednie odniesienie do ogona, a dostęp do niego ma minimalną stałą złożoność czasową. 2. add(<Index>, <Element>) — dodaje element według indeksu. Podczas dodawania elementu, powiedzmy, na środku listy, metoda ta najpierw iteruje po elementach od początku i końca (w obu kierunkach), aż do znalezienia żądanego miejsca. Jeżeli pomiędzy trzecim i czwartym elementem dodamy element (na powyższym obrazku), to kolejne łącze trzeciego elementu będzie wskazywało nowy element. A poprzedni nowo dodanego elementu będzie wskazywał trzeci. Z kolei poprzedni link starego czwartego elementu będzie teraz wskazywał nowy element, a następny link nowego elementu będzie wskazywał nowy czwarty element: Złożoność czasowa tej metody zależy od indeksu nowego elementu:

• jeśli jest blisko głowy lub ogona, operacja zbliży się do O(1), ponieważ w rzeczywistości nie będzie konieczne iterowanie po elementach;
• jeśli będzie blisko środka, to będziemy mieli O(N/2), gdyż metoda będzie przeszukiwać jednocześnie od głowy i ogona, aż do znalezienia żądanego elementu.

3. set(<Index>, <Element>) — zapisuje element na określoną pozycję na liście. Złożoność czasowa tej operacji będzie wynosić od O(1) do O(N/2), ponownie w zależności od tego, jak blisko nowy element znajduje się od głowy, ogona lub środka. 4. usuń(<indeks>) — usuwa element z listy w taki sposób, że element poprzedzający usunięty ( poprzedni ) odnosi się teraz do elementu następującego po usuniętym ( następny ). I odwrotnie, czyli element po usuniętym odnosi się teraz do elementu poprzedzającego usunięty: Jest to proces odwrotny do dodawania według indeksu ( add(<Index>, <Element>) ).

88. Jaka jest wewnętrzna struktura HashMap?

To może być jedno z najpopularniejszych pytań na rozmowach kwalifikacyjnych, które zadaje się kandydatom na programistów Java. HashMap działa z parami klucz -wartość . W jaki sposób są przechowywane w samej HashMap ? HashMap ma wewnętrzną tablicę węzłów:

Node<K,V>[] table

Domyślnie rozmiar tablicy wynosi 16 i podwaja się przy każdym wypełnieniu elementami (to znaczy po osiągnięciu LOAD_FACTOR ; określa próg zapełnienia tablicy — domyślnie jest to 0,75 ). . Każdy z węzłów przechowuje skrót klucza, klucz, wartość i odniesienie do następnego elementu: W tym przypadku „odwołanie do następnego elementu” oznacza, że ​​mamy do czynienia z listą jednopołączoną, gdzie każdy element zawiera łącze do następnego. Innymi słowy, HashMap przechowuje swoje dane w tablicy pojedynczo połączonych list. Ale od razu powiem, że gdy komórka tablicy tabeli zawiera pojedynczo połączoną listę składającą się z więcej niż jednego elementu, nie jest to dobre. Zjawisko to nazywa się kolizją . Ale najpierw najważniejsze. Zobaczmy, jak zapisuje się nową parę za pomocą metody put . Najpierw metoda pobiera hashCode() klucza . Oznacza to, że aby HashMap działał poprawnie, używane klucze muszą być klasami, które zastępują tę metodę. Ten kod skrótu jest następnie używany w wewnętrznej metodzie hash() w celu określenia indeksu jakiejś komórki w tablicy tabeli. Wynikowy indeks umożliwia nam dostęp do określonej komórki tablicy tabeli. Mamy tu dwa przypadki:

1. Komórka jest pusta — w tym przypadku zapisywana jest w niej nowa wartość Node .
2. Komórka nie jest pusta — w tym przypadku porównywane są wartości kluczy. Jeśli są równe, nowa wartość Node zastępuje starą; jeśli nie jest równa, wówczas uzyskiwany jest dostęp do następnej i porównywany jest jej klucz... I tak dalej, aż nowa wartość albo nadpisze jakąś starą wartość, albo dotrzemy do końca pojedynczo połączonej listy i zapiszemy tam nową wartość jako ostatni element.

Podczas wyszukiwania elementu po kluczu (przy użyciu metody get(<key>) ) obliczany jest hashCode() klucza , a następnie obliczany jest jego indeks w tablicy za pomocą hash() . Wynikowa liczba jest indeksem komórki w tablicy tabeli , którą następnie przeszukujemy, iterując po węzłach i porównując klucz żądanego węzła z kluczem bieżącego węzła. W idealnym przypadku operacje na mapie mają złożoność algorytmiczną O(1), ponieważ uzyskujemy dostęp do tablicy, a jak pamiętasz, jest to O(1), niezależnie od liczby zawartych w niej elementów. Ale nie mamy do czynienia z przypadkiem idealnym. Gdy komórka nie jest pusta (2) i przechowuje już kilka węzłów, wówczas złożoność algorytmiczna staje się O(N) (liniowa), ponieważ teraz konieczne jest iterowanie po elementach, zanim znajdziemy właściwe miejsce. Nie mogę nie wspomnieć, że począwszy od Java 8, jeśli węzeł w postaci listy z pojedynczym łączem ma więcej niż 8 elementów (kolizje), to zostaje przekonwertowany na drzewo binarne. W tym przypadku złożoność algorytmiczna nie wynosi już O(N), ale O(log(N)) — a to zupełnie inna sprawa, prawda? HashMap to duży temat i ludzie uwielbiają zadawać pytania na ten temat podczas rozmów kwalifikacyjnych. Sugeruję więc, żebyś znał to jak własną kieszeń. Osobiście nigdy nie odbyłem rozmowy kwalifikacyjnej, która nie zawierałaby pytań dotyczących HashMap . To wszystko na dzisiaj. Ciąg dalszy nastąpi...