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

Cześć! Ile godzin potrzeba, aby zostać w czymś mistrzem? Często słyszałem coś w stylu: „Aby zostać w czymkolwiek mistrzem, trzeba spędzić 10 000 godzin”. Przerażająca liczba, prawda? Zastanawiam się jednak, czy to prawda? I ciągle próbuję policzyć, ile godzin już zainwestowałem w opanowanie sztuki programowania. A kiedy przekroczę te cenne 10 000 godzin i zostanę mistrzem, czy poczuję tę różnicę? A może już dawno je przekroczyłem, nie zdając sobie z tego sprawy? Tak czy inaczej, aby zostać programistą, nie trzeba inwestować tak dużej ilości czasu. Najważniejsze, żeby mądrze z tego korzystać. Twoim głównym celem jest zdanie rozmowy kwalifikacyjnej. A na rozmowach kwalifikacyjnych dla nowicjuszy pierwszą rzeczą, o którą pytają, jest teoria, więc musisz być w niej mocny. Tak naprawdę, przygotowując się do rozmowy kwalifikacyjnej, Twoim zadaniem jest odkrycie wszystkich luk w podstawowej teorii programisty Java i pokrycie ich wiedzą. I dzisiaj pomogę Ci w tej kwestii, ponieważ jestem tutaj, aby kontynuować analizę najpopularniejszych pytań. Więc kontynuujmy!

89. Czym różni się ArrayList od LinkedList?

To jedno z najpopularniejszych pytań, obok pytania o wewnętrzną strukturę HashMap . Żaden wywiad nie jest kompletny bez niego, dlatego odpowiedź na nie powinna „odbić się od zębów”. Oprócz oczywistych – różnych nazw – różnią się one budową wewnętrzną. Wcześniej badaliśmy wewnętrzną strukturę zarówno ArrayList , jak i LinkedList , więc nie będę wchodził w szczegóły ich implementacji. Przypominam, że ArrayList implementowany jest w oparciu o wewnętrzną tablicę, która jest zwiększana w miarę potrzeb według wzoru:

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

Jednocześnie LinkedList jest realizowany w oparciu o wewnętrzną listę podwójnie połączoną, czyli każdy element posiada link do poprzedniego i następnego, z wyłączeniem wartości będących początkiem/końcem listy. Ludzie lubią zadawać to pytanie w formacie: „Co jest lepsze – ArrayList czy LinkedList ?”, mając nadzieję, że Cię złapią. W końcu, jeśli wskażesz jedną z nich jako odpowiedź, będzie to odpowiedź błędna. Zamiast tego powinieneś wyjaśnić, o jakiej konkretnej sytuacji mówisz - dostęp do indeksu lub wstawienie na środek listy. W zależności od odpowiedzi będziesz mógł uzasadnić swój wybór. Opisałem wcześniej, jak ArrayList i LinkedList działają w tej czy innej sytuacji. Podsumujmy to, umieszczając je na tej samej stronie dla porównania: Dodanie elementu (dodaj)

1. Добавление нового element без указания индекса Jak местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу Jak правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

Konkluzja: w LinkedList złożoność algorytmiczna będzie wynosić od O(1) do O(n/2) . Oznacza to, że im bliżej końca lub początku listy jest wstawianie, tym jest ono szybsze. Jednocześnie dla ArrayList waha się od O(1) do O(n) : im bliżej końca listy, tym jest szybsze. Ustawianie elementu (zestawu) Operacja ta zapisuje element na określoną pozycję na liście, nadpisując poprzedni, jeśli taki istnieje. W LinkedList operacja ta będzie podobna do dodawania, ponieważ Największą trudnością jest tutaj znalezienie elementu. Przepisanie elementu będzie odbywać się poprzez przepisanie pary linków, więc i tutaj złożoność algorytmiczna będzie się wahać od O(1) do O(n/2) w zależności od odległości pozycji od końca lub początku listy. Wówczas w ArrayList zostanie odnaleziona żądana komórka dla tej operacji indeksowania i zostanie do niej dopisany nowy element. Wyszukiwanie indeksu, podobnie jak ta operacja, ma złożoność algorytmiczną O(1) . Pobieranie elementu po indeksie (get) W LinkedList pobranie elementu będzie odbywać się na tej samej zasadzie, co wyszukiwanie innych operacji – w zależności od odległości od końca lub początku, tj. od O(1) do O(n/2) . W ArrayList , jak powiedziałem wcześniej, znalezienie elementu w tablicy według indeksu ma złożoność O(1) . Usuń element po indeksie (usuń) W przypadku LinkedList zasada jego działania również tutaj działa: najpierw zostaje znaleziony element, a następnie nadpisane są linki - sąsiedzi elementu zaczynają się do siebie odwoływać, tracąc odniesienia do tego elementu, które następnie zostaną usunięte przez moduł zbierający śmieci. Oznacza to, że złożoność algorytmiczna jest nadal taka sama - od O(1) do O(n/2) . W przypadku ArrayList operacja ta jest bardziej podobna do operacji dodania nowego elementu (add). Najpierw zostaje znaleziony wymagany element - O(1) , następnie jest on usuwany, a wszystkie elementy, które znajdowały się na prawo od niego, są przesuwane o jedną jednostkę w lewo, aby zamknąć powstałą lukę. Operacja usuwania będzie miała taką samą złożoność algorytmiczną jak operacja dodawania - od O(1) do O(n) . Im bliżej końca listy jest usunięcie, tym mniejsza jest złożoność algorytmiczna. Właściwie były to wszystkie główne operacje. Przypomnę: porównując te dwa zestawienia trzeba doprecyzować, o jakiej konkretnej sytuacji mówimy, a wtedy będzie można jednoznacznie odpowiedzieć na postawione pytanie.

90. Czym różni się ArrayList od HashSet?

Jeśli można by porównać ArrayList i LinkedList pod względem operacji - co jest lepsze - to porównanie ArrayList z HashSet nie jest takie proste, ponieważ są to zupełnie różne kolekcje. Można porównać jedno słodkie danie z drugim, ale sprawdzi się z daniem mięsnym - są zbyt różne. Spróbuję jednak podać pewne różnice między nimi:

• ArrayList implementuje interfejs List , podczas gdy HashSet implementuje interfejs Set ;

• W ArrayList dostęp jest możliwy poprzez indeks elementu: operacja get ma złożoność algorytmiczną O(1) , a w HashSet wymagany element można uzyskać tylko metodą brute-force i jest to od O(1) do O(n) ;

• ArrayList pozwala na duplikowanie elementów. W HashSet wszystkie elementy są unikalne: dodanie elementu do HashSet , którego odpowiednik jest już obecny w kolekcji, nie będzie działać (duplikaty są sprawdzane za pomocą hashcode, stąd nazwa tej kolekcji);

• ArrayList jest zaimplementowany przy użyciu tablicy wewnętrznej, a HashSet jest zaimplementowany przy użyciu wewnętrznej HashMap ;

• ArrayList utrzymuje kolejność wstawiania elementów, podczas gdy HashSet jest zestawem nieuporządkowanym i nie zachowuje kolejności elementów;

• ArrayList dopuszcza dowolną liczbę pustych wartości (null), do HashSet można wstawić tylko jedną wartość null (w końcu unikalność elementów).

91. Dlaczego w Javie istnieje taka różnorodność implementacji tablic dynamicznych?

Cóż, to jest raczej pytanie filozoficzne. Dlaczego wymyślają tak wiele różnych nowych technologii? Dla komfortu. Właściwie to samo dotyczy dużej liczby implementacji tablic dynamicznych. Żadnego z nich nie można nazwać najlepszym i idealnym. Każdy ma przewagę w jakiejś konkretnej sytuacji. A naszym zadaniem jest poznać ich różnice, mocne/słabe strony, aby móc zastosować najodpowiedniejszy w danej sytuacji.

92. Dlaczego w Javie istnieje tak wiele różnych implementacji przechowywania klucz-wartość?

Tutaj sytuacja jest taka sama jak w przypadku implementacji tablic dynamicznych. Nie ma nikogo najlepszego: każdy ma mocne i słabe strony. Musimy oczywiście maksymalnie wykorzystać nasze mocne strony. Przykład: pakiet współbieżny, który zawiera wiele technologii wielowątkowych, ma własne kolekcje współbieżne . Ta sama ConcurrentHashMap ma przewagę w bezpieczeństwie wielowątkowej pracy z danymi w porównaniu ze zwykłą HashMap , ale w środowisku nie-wielowątkowym traci na szybkości. Otóż ​​wdrożenia, które w żadnej sytuacji nie są najmocniejsze, stopniowo odchodzą do lamusa. Przykład: Hashtable pierwotnie miał być bezpieczną wątkowo HashMap , ale ConcurrentHashMap radził sobie lepiej w środowisku wielowątkowym, a Hashtable ostatecznie został zapomniany i nie był już używany.

93. Jak posortować zbiór elementów?

Pierwszą rzeczą do powiedzenia jest to, że klasa elementu kolekcji musi implementować interfejs Comparable i jego metodę CompareTo . Lub potrzebujesz klasy, która implementuje Comaprator z jego metodą porównawczą . Więcej na ich temat przeczytacie w tym poście . Obie metody określają sposób porównywania obiektów danego typu. Podczas sortowania jest to niezwykle ważne, ponieważ należy zrozumieć zasadę, według której można porównywać elementy. Głównym sposobem na to jest zaimplementowanie Comparable , zaimplementowane bezpośrednio w klasie, którą chcesz posortować. Jednocześnie korzystanie z komparatora jest mniej powszechne. Załóżmy, że używasz klasy z jakiejś biblioteki, która nie ma implementacji Comparable , ale musisz ją jakoś posortować. Nie mając możliwości zmiany kodu tej klasy (poza jego rozszerzeniem) można napisać implementację Comparator , w której wskazujesz na jakiej zasadzie chcesz porównywać obiekty tej klasy. I jeszcze jeden przykład. Załóżmy, że potrzebujesz różnych zasad sortowania obiektów tego samego typu, więc piszesz kilka komparatorów , których używasz w różnych sytuacjach. Z reguły wiele klas od razu implementuje interfejs Comparable - ten sam String . Właściwie, korzystając z nich, nie musisz się martwić, jak je porównać. Po prostu je bierzesz i używasz. Pierwszym i najbardziej oczywistym sposobem jest użycie kolekcji takiej jak TreeSet lub TreeMap , która przechowuje elementy w już posortowanej kolejności zgodnie z komparatorem klas elementów. Pamiętaj, że TreeMap sortuje klucze, ale nie wartości. Jeśli użyjesz implementacji Comparator zamiast Comparable , podczas tworzenia będziesz musiał przekazać jej obiekt do konstruktora kolekcji:

TreeSet treeSet = new TreeSet(customComparator);

A co jeśli masz inny rodzaj kolekcji? Jak to posortować? W tym wypadku odpowiednia jest druga metoda klasy użytkowej Collections – metoda sort() . Jest statyczny, więc wystarczy nazwa klasy i metoda, do której przekazywana jest wymagana lista. Na przykład:

Collections.sort(someList);

Jeśli nie używasz Comparable , ale raczej implementację Comparator , musisz przekazać ją jako drugi parametr:

Collections.sort(someList, customComparator);

W rezultacie zmieni się wewnętrzna kolejność elementów przekazanej listy: zostanie ona posortowana według komparatora elementów. Zwracam uwagę, że przenoszona lista elementów musi być zmienna, tj. mutable, w przeciwnym razie metoda nie będzie działać i zostanie zgłoszony wyjątek UnsupportedOperationException . Trzecim sposobem możesz użyć operacji sortowania Stream , która sortuje elementy kolekcji, jeśli używana jest implementacja Comparable :

someList = someList.stream().sorted().collect(Collectors.toList());

jeśli komparator :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Więcej o Streamie możesz przeczytać w tym artykule . Czwartą metodą jest ręczne wdrożenie sortowania, takiego jak sortowanie bąbelkowe lub sortowanie przez scalanie .

Obiekt klasy. Równa się i HashCode

94. Podaj krótki opis obiektu klasy w Javie

W drugiej części analizy mówiliśmy już o metodach klasy Object i przypomnę, że klasa Object jest przodkiem wszystkich klas w Javie. Ma 11 metod, które odpowiednio są dziedziczone przez wszystkie klasy. Informacje o wszystkich 11 metodach można znaleźć w drugiej części dyskusji.

95. Do czego służą znaki Equal i HashCode w Javie?

hashCode() to metoda klasy Object , która jest dziedziczona przez wszystkie klasy. Jego zadaniem jest wygenerowanie pewnej liczby reprezentującej konkretny obiekt. Przykładem użycia tej metody jest jej użycie w HashMap na obiekcie kluczowym w celu dalszego określenia lokalnego kodu skrótu, który określi komórkę wewnętrznej tablicy (zasobnika), w której będzie przechowywana para. O działaniu HashMap szczegółowo pisaliśmy w części 9 analizy , więc nie będziemy się nad tym zbytnio rozwodzić. Z reguły metoda ta jest stosowana w metodzie równości() jako jedno z jej głównych narzędzi do określania tożsamości obiektów. quals() to metoda klasy Object , której zadaniem jest porównywanie obiektów i określanie, czy są one równe, czy nie. Metodę tę stosuje się wszędzie tam, gdzie musimy porównać obiekty, ponieważ zwykłe porównanie za pomocą == nie jest odpowiednie dla obiektów, ponieważ porównuje tylko linki do nich.

96. Opowiedz nam o umowie pomiędzy Equals i HashCode w Javie?

Pierwszą rzeczą, którą powiem, jest to, że aby metody równości() i hashCode() działały poprawnie , muszą zostać poprawnie zastąpione. Następnie muszą przestrzegać zasad:

• identyczne obiekty, dla których porównanie przez równanie zwraca wartość true, muszą mieć identyczne kody skrótu;
• obiekty z tymi samymi kodami skrótu nie zawsze mogą być równe.

W tym momencie zrobimy pauzę do następnej części analizy!