Ano ang maaari nilang itanong sa isang panayam: Mga istruktura ng data sa Java. Bahagi 2

BAHAGI 1 Ngayon ay pinag-uusapan natin ang base na dapat malaman ng bawat developer ng Java. Tungkol sa klasikal na kaalaman kung saan nagsisimula ang lahat. Ngayon gusto kong hawakan ang isa sa mga pangunahing paksa ng anumang mga istruktura ng panayam-data sa Java . Kaya, sa halip na matalo sa paligid ng bush, magsimula tayo. Abangan ang pagpapatuloy ng listahan ng mga tanong na maaaring itanong sa iyo sa paksang ito sa panahon ng isang panayam.

6. Sabihin sa amin ang tungkol sa Listahan

Ang listahan ay isang interface na kumakatawan sa isang nakaayos na istraktura ng mga bagay, na tinatawag na isang listahan. Ang "panlinlang" ng istrukturang ito ay ang mga elementong nakapaloob sa Listahan ay maaaring ipasok, baguhin o tanggalin ng index, iyon ay, ang panloob na identifier ng Listahan . Sa madaling salita, ang ibig sabihin ng index ay: "kung gaano karaming mga elemento ang mula sa simula ng listahan." Ang unang elemento ng Listahan ay may index 0, ang pangalawa ay may index 1, at iba pa. Kaya ang ikalimang elemento ay apat na elemento ang layo mula sa simula ng listahan. Tulad ng nabanggit sa itaas, ang pagkakasunud-sunod kung saan ang mga item ay idinagdag sa isang listahan ay mahalaga. Iyon ang dahilan kung bakit ang istraktura ng data ay tinatawag na isang listahan . Inililista namin ang mga pamamaraan na natatangi sa istrukturang ito na naglalayong magtrabaho kasama ang mga elemento ayon sa index:

• get - ibinabalik ang elemento sa tinukoy na posisyon (ayon sa halaga ng index),
• alisin - inaalis ang elemento sa tinukoy na posisyon,
• set - pinapalitan ang elemento sa tinukoy na posisyon ng elementong tinukoy sa pamamaraan.

Основные реализации — ArrayList и LinkedList. Подробнее о них поговорим немного позже. Vector — список, который ориентирован на многопоточное использование, поэтому в данном классе каждый метод синхронизирован. Но учтите, что если вы хотите обезопасить некоторые действия со списками, вы будете синхронизировать целую последовательность операций. А синхронизация отдельных операций и менее безопасна, и гораздо медленнее. Конечно, Vector также имеет накладные расходы на блокировку, даже если вам эта блокировка и не нужна. Поэтому сейчас этот класс считается устаревшим и не используется. Кстати: ArrayList является аналогом Vector, но не использует блокировку, поэтому используется повсеместно. Stack — это подкласс класса Vector с одним конструктором по умолчанию и всеми методами класса Vector, а также несколькими собственными (о них мы поговорим чуть ниже). В качестве примера можно представить процесс в виде стопки папок с documentами. Наверх стопки вы кладете по одной папке, и брать данные папки можно только в обратном порядке, начиная с верхней. Собственно, это и есть механизм типа LIFO, то есть Last In First Out, последний пришел — первым ушел. Стек реализует свои собственные методы:

• push — добавляет переданный элемент на вершину стека;
• peek — возвращает элемент, который находится на вершине стека;
• pop — также возвращает элемент, который находится на вершине стека, но при этом удаляет его;
• empty — проверяет, пуст ли стек — true, or нет — false;
• search — выполняет поиск заданного element в стеке. Если элемент найден, возвращается его порядковый номер относительно верхушки стека. Если же элемент не найден, возвращается meaning -1.

В данный момент подкласс Stack фактически не используется в силу своей простоты и негибкости, но, тем не менее, он может вам встретиться. Например, когда вы получаете некоторую ошибку, и в консоли видите стек сообщений о ней. Подробнее о стеке и очереди можно почитать вот в этой статье.

7. Расскажите о Map

Как сказано выше, Map — это коллекция имеющая отдельную структуру интерфейсов и их реализаций. Отдельная она потому, что здесь значения не хранятся по одному, а в паре “ключ – meaning”.Основные методы Map:

• put(K key, V value) — добавление element в Map;
• get(Object key) — поиск значения по ключу;
• containsKey(Object key) — проверка Map на наличие данного ключа;
• containsValue(Object value) — проверка Map на наличие данного значения;
• remove(Object key) — удаление значения по его ключу.

Как вы видите, большинство операций работает с помощью использования ключа. В качестве ключей, How правило, выбираются неизменные an objectы (immutable). Типичный пример данного an object — String. Основные реализации Map:

1. HashMap — предназначена для хранения значений в произвольном порядке, но позволяет быстро искать элементы карты. Позволяет задавать ключ ключевым словом null, но не более одного раза, т.к. пары с одинаковыми ключами записываются поверх друг друга. Главным conditionм является уникальность ключей: значения же могут повторяться (может быть несколько null значений).
2. LinkedHashMap — аналог HashMap, который хранит значения в порядке добавления. Соответственно, How и LinkedList, у него есть header — голова двусвязного списка. При инициализации указывает сам на себя.

   Также у LinkedHashMap есть accessOrder, который указывает, Howим образом будет осуществляться доступ к elementм во время использования итератора. При accessOrder false доступ будет осуществляться в порядке вставки элементов. При значении true элементы будут в порядке последнего доступа (элемент, к которому было последнее обращение будет помещен в конец).

3. TreeMap — это Map, сортирующая элементы по значениям ключа. Аналог TreeSet, но для пар с ориентировкой на значения ключей. Для задания правил сортировки TreeMap ключи должны реализовывать Comparable интерфейс. В ином случае должен быть Comparator, ориентированный на ключи (тот, который задается в конструктор TreeMap), TreeSet — реализован с an objectом TreeMap внутри, в котором, собственно, и происходит вся магия.

   Подробнее про сортировку в TreeMap с помощью красно-черных деревьев можно почитать в статье об особенностях TreeMap.

4. Hashtable — аналогичен HashMap, но но не позволяет хранить null ни в качестве ключей, ни в качестве значений. Он тщательно синхронизирован с точки зрения многопоточности, что в свою очередь означает, что он безопасен с точки зрения многопоточности. Но данная реализация устаревшая и медленная, поэтому сейчас вы и не встретите Hashtable в более-менее новых проектах.

8. ArrayList vs LinkedList. Какой предпочтительней использовать?

Этот вопрос, пожалуй, самый популярный по структурам данных и несет в себе некоторые подводные камни. Прежде чем отвечать на него, давайте узнаем подробнее об этих структурах данных. ArrayList реализует интерфейс List, работает за счет внутреннего массива, который расширяется по мере необходимости. Когда внутренний массив fully заполняется, и при этом нужно вставить новый элемент то создается новый массив, с размером (oldSize * 1,5) +1. После этого все данные из старого массива копируются в новый +новый элемент, старый же будет удален сборщиком мусора. Метод add добавляет элемент в последнюю пустую ячейку массива. То есть, если у нас там уже есть 3 element, он добавит следующий в 4-ю ячейку. Давайте пройдемся по производительности базовых методов:

• get(int index) — взятие element в массиве по индексу работает быстрее всего за O(1);
• add(Object obj) — если достаточно места во внутреннем массиве для нового element, то при обычной вставке будет затрачено время O(1), так How добавление идет целенаправленно в последнюю ячейку.

  Если же нужно создавать новый массив и копировать в него содержимое, то время у нас будет прямо пропорционально количеству элементов в массиве O(n);

• remove(int index) — при удалении element, к примеру, из середины, мы получим время O(n/2), так How нужно будет передвигать элементы справа от него на одну ячейку назад. Соответственно, если удаление с начала списка, то O(n), c конца — O(1);
• add(int index, Object obj) — ситуация, схожая с удалением: при добавлении в середину нам нужно будет передвинуть элементы справа на одну ячейку вперед, поэтому время — O(n/2). Разумеется, с начала — O(n), с конца — O(1);
• set(int index, Object obj) — тут ситуация иная, так How требуется только найти нужный элемент и записать поверх него, не передвигая остальные, поэтому O(1).

Подробнее про ArrayList — в этой статье. LinkedList реализует сразу два интерфейса — List и Queue, поэтому и владеет свойствами и методами, присущими обоим структурам данных. От List он взял доступ к элементу по индексу, от Queue — наличие “головы” и “хвоста”. Внутри он реализован How структура данных, представляющая двусвязный список. То есть, у каждого element есть link на следующий и предыдущий, кроме “хвоста” и “головы”.

• get(int index) — при поиске element, который находится в середине списка, начинается перебор всех элементов по порядку, пока не будет найден нужный. По логике поиск должен занимать O(n/2), но у LinkedList есть еще и хвост, поэтому перебор ведется одновременно с двух сторон. Соответственно, время уменьшается до O(n/4).

  Если же элемент будет недалеко от начала списка or конца, то и время будет O(1);

• add(Object obj) — при добавлении нового element, у element-”хвоста” добавится link на следующий элемент, а новый получит ссылку на этот предыдущий элемент и станет новым “хвостом”. Соответственно, время будет O(1);
• remove(int index) — логика, схожая с методом get(int index). Для удаления element из середины списка, его нужно сначала найти. Это опять же O(n/4), в то время How само удаление фактически ничего не занимает, так How там только меняются указатель соседних an objectов (они начинают ссылаться друг на друга). Если элемент в начале or в конце, то опять же — O(1);
• add(int index, Object obj) и set(int index, Object obj) — у методов временная сложность будет идентична get(int index), так How основное время занимает поиск element. Поэтому для середины списка — O(n/4), для начала — O(1).

Больше о работе с LinkedList рассказано в этой статье. Давайте все это рассмотрим в таблице: Как вы уже наверное поняли, однозначно ответить на данный вопрос нельзя. Ведь при разных ситуациях они и работают с разной speedю. Поэтому, когда вам задают подобный вопрос, вы должны сразу спросить, на что будет ориентирован данный список и Howие операции будут чаще всего производиться. Уже отталкиваясь от этого, давать ответ, но с пояснениями, почему именно так. Подведем же небольшие итоги по нашему сравнению: ArrayList:

• лучший выбор, если наиболее частая операция — поиск element, перезапись element;
• худший выбор, если операция — вставка и удаление в начале-середине, потому что будут проходить операции сдвига элементов справа.

LinkedList:

• лучший выбор, если нашей частой операцией является вставка и удаление в начале-середине;
• худший выбор, если наиболее частая операция — поиск.

9. Как хранятся элементы в HashMap?

Коллекция HashMap содержит в себе внутренний массив Node [] table, ячейки которого еще называют бакетами (корзинами). Node содержат в себе:

• key — ссылку на ключ,
• value — ссылку на meaning,
• hash — meaning hash,
• next — ссылку на следующий Node.

В одной ячейке массива table[] может содержаться link на an object Node со ссылкой на следующий элемент Node, а он может иметь ссылку на другой, и так далее… В итоге, данные элементы Node могут образовывать односвязный список, с elementми со ссылкой на следующие. При этом meaning hash у элементов одной цепочки одинаковое. После небольшого отступления давайте посмотрим, How происходит сохранение элементов в HashMap:

1. Ключ проверяется на equalsство null. Если он null, то key будет сохранен в ячейке table[0], потому что хэш-code для null всегда equals 0.
2. Если ключ не null, то у an object key вызывается метод hashcode(), который выдаст его хэш-code. Этот хэш-code используется для определения ячейки массива, где будет храниться an object Node.
3. Далее данный hashcode помещается в внутренний метод hash(), который высчитывает hashcode, но уже в пределах размера массива table[].
4. Дальше, в зависимости от значения hash, Node помещается в конкретную ячейку в массиве table[].
5. Если же ячейка table[], используемая для сохранения текущего element Node не пуста, а уже имеет Howой-то элемент, то происходит перебор элементов Node по значению next, пока не будет достигнут последний элемент. То есть, тот, у которого поле next равно null.

   Во время данного перебора сравниваются ключ охраняемого an object Node с ключами перебираемых:

   • если будет найдено соответствие, то перебор закончится, и новый Node перезапишет Node, в котором найдено соответствие (перезапишется только его поле value);
   • если соответствия ключей не найдены, то новый Node станет последним в этом списке, а предыдущий будет иметь ссылку next на него.

Часто на собеседованиях мелькает вопрос: что такое коллизия? Ситуацию, когда в ячейке массива table[] хранится не один элемент, а цепочка из двух и более, и называется коллизия. В обычных случаях, когда в одной ячейке table[] хранится только один элемент, доступ к elementм HashMap имеет константную временную сложность O(1). Но когда в ячейке с нужным элементом присутствует цепочка элементов (коллизия), то O(n), так How в таком случае время прямо пропорционально зависит от количества перебираемых элементов.

10. Расскажите об итераторе

В схеме с отображением иерархии Collection выше интерфейс Collection был тем, с чего начиналась вся иерархия, но на практике все не совсем так. Collection наследуется от интерфейса с методом iterator(), который возвращает an object, реализующий интерфейс Iterator<E>. Интерфейс Iterator имеет вид:

public interface Iterator <E>{

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

next() — вызывая данный метод, можно будет получить следующий элемент. hasNext() — дает возможность узнать, есть ли следующий элемент, и не достигнут ли конец коллекции. И когда элементы еще есть, то hasNext() вернет meaning true. Как правило, hasNext() вызывается перед методом next(), так How при достижении конца коллекции next() будет выбрасывать исключение NoSuchElementException. remove() — удаляет элемент, который получен последним вызовом next(). Преднаmeaningм Iterator является перебор элементов. Например:

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

Собственно, цикл for-each loop и реализован под капотом с помощью итератора. Подробнее об этом можно почитать тут. List предоставляет свою версию итератора, но более крутую и навороченную — ListIterator. Данный интерфейс расширяет Iterator, и у него есть дополнительные методы:

• hasPrevious вернет true, если в коллекции имеется предыдущий элемент, иначе — false;
• previous возвращает текущий элемент и переходит к предыдущему; если такого нет, то выбрасывается исключение NoSuchElementException;
• add вставит переданный an object перед элементом, который должен быть возвращен следующим вызовом next();
• set присваивает текущему элементу ссылку на переданный an object;
• nextIndex возвращает индекс следующего element. Если такого нет, то возвращается размер списка;
• previousIndex возвращает индекс предыдущего element. Если такого нет, то возвращается число -1.

What же, на этом у меня сегодня все. Я надеюсь, что после прочтения этой статьи вы стали еще ближе к заветной мечте — стать разработчиком.