Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 9

Салют! Быть программистом непросто. Нужно постоянно учиться, вечно познавать что-то новое. Но, как и в любом другом деле, самое сложное — начать, сделать первый шаг на пути к своей цели. И раз ты сидишь на данном сайте и читаешь данную статью, с первым шагом ты справился. А значит, теперь нужно целеустремленно двигаться к своей цели, не тормозя и не сворачивая на пути. Если я понимаю правильно, твоя цель — стать Java-разработчиком или усилить знания, если ты таковым являешься. Если всё так, то ты по адресу, ведь мы будем продолжать разбирать обширный список из 250+ вопросов на собеседованиях для Java-разработчика. Продолжим!

Collections

84. Расскажите про итераторы и их применение

Коллекции — одна из самых любимых тем на любом собеседовании Java-разработчика, и рассказывая об иерархии коллекций кандидаты часто говорят, что она начинается с интерфейса Collection. Но это не так, ведь над этим интерфейсом есть ещё один — Iterable. Данный интерфейс представляет метод iterator(), который позволяет вызывать объект Iterator для текущей коллекции. И что же такое этот объект Iterator? Iterator — это объект предоставляющий возможность двигаться по коллекции и перебирать элементы, причем пользователю не нужно знать реализацию конкретной коллекции. То есть, это некоторый указатель на элементы коллекции, который как бы смотрит на определенное место в ней. У итератора есть такие методы:

• hasNext() — возвращает true, если есть элемент, расположенный после указателя (данный метод позволяет узнать, достигнут ли конец коллекции);
• next() — возвращает следующий элемент после указателя. Если такового не будет, выбрасывается NoSuchElementException. То есть перед использованием этого метода лучше убедиться в том, что элемент есть — с помощью hasNext();
• remove() — удаляет из коллекции последний полученный элемент методом next(). Если же next() до вызова remove() ни разу не вызывали, будет брошено исключение — IllegalStateException;
• forEachRemaining(<Consumer>) — выполняет переданное действие с каждым элементом коллекции (метод появился с Java 8).

Вот небольшой пример прохода по списку и удаления всех его элементов с помощью рассмотренных методов итератора:

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

В консоли будет выведено: А это значит, что удаление элементов прошло успешно. Получив итератор, можно было бы воспользоваться методом для вывода всех элементов на экран:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Node<K,V>[] table

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

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

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