Pagsusuri ng mga tanong at sagot mula sa mga panayam para sa developer ng Java. Bahagi 9

Paputok! Ang pagiging programmer ay hindi madali. Kailangan mong patuloy na matuto, laging matuto ng bago. Ngunit, tulad ng sa anumang iba pang negosyo, ang pinakamahirap na bagay ay magsimula, gawin ang unang hakbang patungo sa iyong layunin. At dahil nakaupo ka sa site na ito at binabasa ang artikulong ito, nakumpleto mo na ang unang hakbang. Nangangahulugan ito na ngayon ay kailangan mong may layunin na lumipat patungo sa iyong layunin, nang hindi bumabagal o lumiliko sa daan. Kung naiintindihan ko nang tama, ang iyong layunin ay maging isang developer ng Java o pahusayin ang iyong kaalaman kung isa ka. Kung gayon, nasa tamang lugar ka, dahil patuloy naming susuriin ang isang malawak na listahan ng 250+ tanong sa panayam ng developer ng Java. Ituloy natin!

Mga koleksyon

84. Sabihin sa amin ang tungkol sa mga iterator at ang kanilang paggamit

Ang mga koleksyon ay isa sa mga paboritong paksa sa anumang panayam ng developer ng Java, at kapag pinag-uusapan ang hierarchy ng koleksyon, kadalasang sinasabi ng mga kandidato na nagsisimula ito sa interface ng Collection . Ngunit hindi ito totoo, dahil sa itaas ng interface na ito ay may isa pa - Iterable . Kinakatawan ng interface na ito ang iterator() method , na nagbibigay-daan sa iyong tumawag ng Iterator object para sa kasalukuyang koleksyon. At ano nga ba ang Iterator object na ito ? Ang Iterator ay isang bagay na nagbibigay ng kakayahang lumipat sa isang koleksyon at umulit sa mga elemento nang hindi kailangang malaman ng user ang pagpapatupad ng isang partikular na koleksyon. Iyon ay, ito ay isang uri ng pointer sa mga elemento ng koleksyon, na, bilang ito ay, ay tumitingin sa isang tiyak na lugar sa loob nito. Ang iterator ay may mga sumusunod na pamamaraan:

• hasNext() - nagbabalik ng true kung mayroong isang elemento na matatagpuan pagkatapos ng pointer (paraang ito ay nagbibigay-daan sa iyo upang malaman kung ang katapusan ng koleksyon ay naabot na);
• next() - ibinabalik ang susunod na elemento pagkatapos ng pointer. Kung wala, ang NoSuchElementException ay itinapon . Iyon ay, bago gamitin ang pamamaraang ito, mas mahusay na tiyakin na ang elemento ay umiiral - gamit ang hasNext() ;
• remove() - inaalis ang huling elementong natanggap mula sa koleksyon gamit ang susunod na() na pamamaraan . Kung ang next() ay hindi pa natawag bago ang remove() ay tinawag, ang isang exception ay itatapon - IllegalStateException ;
• forEachRemaining(<Consumer>) - nagsasagawa ng naipasa na aksyon sa bawat elemento ng koleksyon (lumalabas ang pamamaraan sa Java 8).

Narito ang isang maliit na halimbawa ng pag-ulit sa isang listahan at pag-alis ng lahat ng elemento nito gamit ang mga pamamaraan ng iterator na tinalakay:

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

Ipapakita ng console ang: Nangangahulugan ito na matagumpay ang pag-alis ng mga elemento. Kapag nagkaroon na kami ng iterator, maaari kaming gumamit ng paraan para i-print ang lahat ng elemento sa screen:

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

Но после этого итератор стал бы непригоден для дальнейшего использования, так How он обошел бы весь список, а методов для обратного перебора у обычного итератора нет. Тут мы плавно подходим к LinkedList, а именно — к его методу listIterator(), который возвращает модернизированный вид итератора — ListIterator. Помимо методов обычного (стандартного) итератора, у этого есть дополнительные:

• add(<Element>) — вставляет новый элемент в список;
• hasPrevious() — возвращает true, если есть элемент, расположенный перед указателем (есть ли предыдущий элемент);
• nextIndex() — возвращает индекс в списке следующего element после указателя;
• previous() — возвращает предыдущий элемент (до указателя);
• previousIndex() — возвращает индекс предыдущего element;
• set(<Element>) — заменяет последний элемент, возвращенный методами next() or previous().

Как видим, функционал этого итератора гораздо интереснее: он позволяет ходить в обе стороны и развязывает руки в работе с elementми. Также когда говорят об итераторах иногда подразумевают сам паттерн. Whatбы не попасть впросак и рассказать о нем убедительно, читайте эту статью о паттерне Iterator.

85. Какая иерархия коллекций в Java Collection Framework?

Существует две иерархии коллекций в Java. Первая иерархия — непосредственно иерархия Collection со следующей структурой: Она в свою очередь делится на следующие подколлекции:

• Set — интерфейс, описывающий такую структуру данных How множество, содержащее неупорядоченные уникальные (неповторяющиеся) элементы. У интерфейса есть стандартные реализации — TreeSet, HashSet и LinkedHashSet.
• List — интерфейс, описывающий структуру данных, которая хранит упорядоченную последовательность an objectов. Экземпляры, которые содержатся в List-е, можно вставлять и удалять по их индексу в данной коллекции (аналог массива, но с динамическим изменением размера). У интерфейса есть стандартные реализации — ArrayList, Vector (считается устаревшей и фактически не используется) и LinkedList.
• Queue — интерфейс, описывающий структуру данных, хранящую элементы в виде очереди, которая следует правилу FIFO — First In First Out (первым вошел, первым вышел). У интерфейса есть такие стандартные реализации: LinkedList (да, он реализует и Queue тоже) и PriotityQueue.

Вторая иерархия коллекций — Map, которая имеет следующую структуру: В этой коллекции разделений на подколлекции нет (так How сама иерархия Map — что-то вроде подколлекции, но лежащая отдельно). Стандартные реализации Map — Hashtable (считается устаревшей), LinkedHashMap и TreeMap. Собственно, когда спрашивают о Collection, How правило подразумевают обе иерархии.

86. Каково внутреннее строение ArrayList?

ArrayList — это аналог массива, но со способностью динамически расширяться. What это значит? Дело в том, что ArrayList работает на основе обычного массива, а именно он хранит элементы во внутреннем массиве (его размер по умолчанию — 10 ячеек). Когда внутренний массив заполняется, создается новый массив, размер которого определяется по формуле:

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

То есть если размер нашего массива 10, размер нового будет: 10 * 3 / 2 + 1 = 16. Далее в него копируются все значения из первого (старого) массива c помощью нативного метода System.arraycopy(), и первый массив удаляется. Собственно, так и реализуется динамическая расширяемость ArrayList. Рассмотрим самые используемые методы ArrayList: 1. add(<Elelement>) — добавляет элемент в конец массива (в последнюю пустую ячейку), при этом сперва проверяется, есть ли место в данном массиве. Если его нет, создается новый массив, в который копируются элементы. Логарифмическая сложность данной операции — O(1). Есть аналогичный метод — add(<Index>,<Elelement>). Он добавляет элемент не в конец списка (массива), а в определенную ячейку с индексом, который пришёл в качестве аргумента. В таком случае логарифмическая сложность будет отличаться в зависимости от места добавления:

• если это было примерно начало списка, логарифмическая сложность будет близка к O(N), ведь придется все элементы, расположенные справа от нового, двигать на одну ячейку вправо;
• если элемент вставляется в середину — O(N/2) т.к. нам нужно сдвинуть на одну ячейку вправо только половину элементов списка.

То есть логарифмическая сложность данного метода колеблется от O(N) до O(1) в зависимости от места вставки element. 2. set(<Index>,<Elelement>) — записывает элемент в указанную позицию в списке. Если в той позиции уже присутствует элемент, перезаписывает его. Логарифмическая сложность данной операции — O(1), ведь там ниHowих сдвигов нет: только поиск по индексу в массиве, что, How мы помним, имеет сложность O(1), и запись element. 3. remove(<index>) — удаление element по его индексу во внутреннем массиве. При удалении element, который расположен не в конце списка, необходимо сдвинуть все элементы справа от него на одну ячейку влево, чтобы закрыть образовавшуюся брешь после удаления element. Поэтому логарифмическая сложность будет такой же, How и у add(<Index>,<Elelement>), если элемент был в середине — O(N/2), — ведь нужно половину элементов сдвинуть на один влево. Соответственно, если он был в начале —- O(N). Ну и если в конце — O(1), ведь и двигать ничего не нужно. Для желающих углубиться в данную тему я оставлю данную ссылку на статью с разбором класса ArrayList.

87. Какое внутреннее строение LinkedList?

Если ArrayList содержит элементы во внутреннем массиве, то LinkedList — в виде двусвязного списка. Это значит, что каждый элемент содержит ссылку на предыдущий элемент (previous) и на следующий (next). У первого element нет ссылки на предыдущий (он ведь первый), при этом он считается главой списка, и в LinkedList есть link непосредственно на него. У последнего element, собственно, нет следующего element, он является хвостом списка, и поэтому прямая link на него есть в самом LinkedList. Поэтому логарифмическая сложность при доступе к главе or хвосту списка — O(1). В ArrayList при увеличении списка увеличивался внутренний массив, тут же все происходит проще — при добавлении element просто меняются пару ссылок. Давайте рассмотрим некоторые наиболее используемые методы LinkedlList-а: 1. add(<Elelement>) — происходит добавление в конце списка, т.е. после последнего element (5) добавится link на новый элемент How next. Новому элементу добавится link на последний (5) How previous элемент. Логарифмическая сложность такой операции будет O(1), так How необходима всего лишь link на последний элемент, а How вы помните, на хвост есть прямая link с LinkedList и логарифмическая сложность доступа к нему минимальная. 2. add(<Index>,<Elelement>) — добавление element по индексу. При добавлении element, например, в середину списка, сперва перебираются элементы с головы и хвоста (с обеих сторон), пока не будет найдено нужное место. Если мы хотим вставить элемент между третьим и четвертым (на рисунке выше), то при поиске нужного места link next третьего element будет уже указывать на новый. У нового же link previous будет указывать на третий. Соответственно, link четвертого element — previous — будет указывать уже на новый элемент, а у нового element link next будет указывать на четвертый элемент: Логарифмическая сложность данного метода будет зависеть от индекса, задаваемого новому элементу:

• если он будет близок к голове or хвосту, то будет приближаться к O(1), поскольку перебирать элементы фактически будет не нужно;
• если же близко к середине, то O(N/2) — будет происходить переборка элементов с головы и хвоста одновременно, пока не будет найден нужный элемент.

3. set(<Index>,<Elelement>) — записывает элемент в указанную позицию в списке. Логарифмическая сложность данной операции будет колебаться от O(1) до O(N/2), опять же в зависимости от того, насколько близок элемент к голове, хвосту or середине. 4. remove(<index>) — удаляет элемент из списка, по сути делая так, чтобы элемент, который находится перед удаляемым (previous), ссылался на элемент, который идёт после удаляемого (next). И наоборот: чтобы элемент, который идет после удаляемого, ссылался на тот, который идёт перед удаляемым: Получился процесс, обратный добавлению по индексу (add(<Index>,<Elelement>)). Желающим узнать больше о внутреннем устройстве LinkedList посоветую прочесть вот эту статью.

88. Каково внутреннее строение HashMap?

Пожалуй, один из самых популярных вопросов при собеседовании Java-разработчика. HashMapv работает с парами ключ – meaning. Как же они хранятся внутри самого HashMapv? Внутри HashMap есть массив нод:

Node<K,V>[] table

По умолчанию размер массива — 16, и он увеличивается каждый раз в два раза по мере заполнения elementми (при достижении LOAD_FACTOR — определенного процента заполненности, по умолчанию он — 0.75). Каждая из нод хранит в себе хеш ключа, ключ, meaning, ссылку на следующий элемент: Собственно, “link на следующий элемент” означает, что мы имеем дело с односвязным списком, где каждый элемент содержит ссылку на следующий. То есть HashMap хранит данные в массиве односвязных списков. Но сразу отмечу: когда одна ячейка массива table имеет ссылку на подобный односвязный список, состоящий из более чем одного element, это не есть хорошо. Такое явление называется коллизия. Но обо всём по порядку. Давайте разберемся, How происходит сохранение новой пары через метод put. Сперва берется hachCode() ключа. Поэтому для корректной работы hashmap в качестве ключей нужно брать классы, в которых данный метод переопределен. Далее этот хеш code используется во внутреннем методе — hash() — для определения числа в пределах размера массива table. Далее по полученному числу, идёт обращение к конкретной ячейке массива table. Тут у нас два случая:

1. Ячейка пустая — в нее сохраняется новое meaning Node.
2. Ячейка не пустая — сравнивается meaning ключей. Если они равны, новое meaning Node перезаписывает старое, если не равны — идёт обращение к элементу next (следующему), идёт сравнение уже с его ключом… И так до тех пор, пока новое meaning не перезапишет некоторое старое or не достигнет конца односвязного списка и сохранится там последним элементом.

При поиске element по ключу (метод get(<key>)), вычисляется hashCode ключа, потом его meaning в пределах массива с помощью hash(), и по полученному числу находится ячейка массива table, в которой уже ведется поиск путем перебора нод и сравнения ключа искомой ноды с ключом текущей. Операции в Map при идеальном раскладе имеют алгоритмическую сложность O(1), ведь идёт обращение к массиву, а How вы помните, независимо от количества элементов операции у массива имеют сложность O(1). Но это в идеальном случае. Когда используемая ячейка массива не пустая (2) и там уже есть некоторые ноды, алгоритмическая сложность превращается в линейную O(N), ведь теперь необходимо перебрать элементы, прежде чем найдется нужное место. Не могу не упомянуть вот что: начиная с Java 8, если у односвязного списка node больше 8 элементов (коллизии), он превращается в двоичное дерево. В таком случае алгоритмическая сложность будет уже не O(N), а O(log(N)) — это уже другое дело, не так ли? HashMap — большая тема, и по ней любят задавать вопросы на собеседованиях. Поэтому советую подробно разобраться в ней (чтобы аж от зубов отсHowивало). Лично у меня не было собеседований без вопросов по HashMap. Глубокий разбор HashMap вы можете найти в этой статье. На этом сегодня всё, продолжение следует…