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

Привет! Как много часов нужно потратить, чтобы стать в чём-то мастером? Часто слышал что-то вроде: “Чтобы стать мастером в любом деле, нужно потратить 10000 часов”. Пугающая цифра, не так ли? Тем не менее, мне интересно, а правда ли это? И я постоянно пытаюсь прикидывать, сколько часов я уже вложил в овладение программистским искусством. И когда я перешагну те заветные 10000 часов и стану мастером, почувствую ли я эту разницу? Или я уже их давно перешагнул, не осознав этого? Так или иначе, чтобы стать программистом, не нужно вкладывать такое огромное количество времени. Главное — использовать его с умом. Ваша первостепенная цель — пройти собеседование. А на собеседованиях новичков в первую очередь как раз спрашивают теорию, поэтому вы должны быть в ней сильны. Собственно, при самой подготовке к собеседованию ваша задача — обнаружить все ваши пробелы в базовой теории Java-разработчика и покрыть их знаниями. И сегодня я вам помогу в этом деле, ведь я тут, чтобы продолжить разбор самых популярных вопросов. Итак, продолжим!

89. Чем отличается ArrayList от LinkedList?

Это один из самых популярных вопросов наравне с вопросом о внутреннем устройстве HashMap. Ни одно собеседование не обходится без него, и поэтому ответ на него у вас должен “отскакивать от зубов”. Помимо очевидного — разного названия — они отличаются внутренним устройством. Ранее мы разбирали внутренние устройство и ArrayList-а и LinkedList-а, поэтому вдаваться в детали их реализации я не буду. Лишь напомню, что ArrayList реализован на основе внутреннего массива, который по надобности увеличивается по формуле:

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

В то же время LinkedList реализован на основе внутреннего двухсвязного списка, то есть, каждый элемент имеет ссылку на предыдущий и следующий, исключая значения, которые являются началом/концом списка. Этот вопрос любят задавать в формате: “Что лучше — ArrayList или LinkedList?”, надеясь вас подловить. Ведь если вы в качестве ответа укажете на один из них, это будет неправильный ответ. Вместо этого вам стоит уточнить, о какой конкретной ситуации идет речь — доступ по индексу или вставка в середину списка. В зависимости от ответа вы сможете объяснить свой выбор. Ранее я уже описывал, как работает ArrayList и LinkedList в той или иной ситуации. Давайте подытожим это, поставив их в один ряд для сравнения: Добавление элемента (add)

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

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

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

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

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

Итог: в LinkedList алгоритмическая сложность будет колебаться от O(1) до O(n/2). То есть, чем ближе вставка к концу или началу списка, тем она быстрее. В то же время у ArrayList она колеблется от O(1) до O(n): чем вставка ближе к концу списка, тем она быстрее. Задание элемента (set) Данная операция записывает элемент в указанную позицию в списке, перезаписывая предыдущий, если он есть. В LinkedList эта операция будет схожа с добавлением, т.к. самая большая сложность тут — поиск элемента. Перезапись элемента будет проходить путем перезаписывания пары ссылок, поэтому тут также алгоритмическая сложность будет колебаться от O(1) до O(n/2) в зависимости от удаленности позиции от конца или начала списка. В то время в ArrayList для этой операции по индексу будет найдена нужная ячейка, а в нее записан новый элемент. Поиск по индексу, как и данная операция, имеет алгоритмическую сложность O(1). Взять элемент по индексу (get) В LinkedList взятие элемента будет происходить по тому же принципу, что и поиск для других операций — в зависимости от удаленности от конца или начала, т.е. от O(1) до O(n/2). В ArrayList, как я и сказал ранее, поиск элемента в массиве по индексу имеет сложность O(1). Удалить элемент по индексу (remove) Для LinkedList тут тоже срабатывает его принцип действия: сперва находится элемент, а потом происходит перезаписывание ссылок — соседи элемента начинают ссылаться друг на друга, теряя ссылки на данный элемент, который впоследствии будет удален сборщиком мусора. То есть, алгоритмическая сложность всё такая же — от O(1) до O(n/2). Для ArrayList данная операция больше схожа с операцией добавления нового элемента (add). Сперва находится искомый элемент — O(1), потом он удаляется, и все элементы, которые были справа от него перемещаются на одну единицу влево, чтобы закрыть образовавшуюся брешь. Операция удаления будет иметь ту же алгоритмическую сложность, что и операция добавления — от O(1) до O(n). Чем удаление ближе к концу списка, тем меньшая у него алгоритмическая сложность. Собственно, это были все основные операции. Напоминаю: при сравнении этих двух списков вам нужно уточнить, о какой конкретной ситуации идёт речь, и тогда уже и можно однозначно ответить на поставленный вопрос.

90. Чем отличается ArrayList от HashSet?

Если ArrayList и LinkedList можно было сравнить по операциям — где кто лучше — то с ArrayList с HashSet сравнить уже не так просто, ведь это совершенно разные коллекции. Можно сравнить одно сладкое блюдо с другим, но с мясным уже получится — больно уж они разные. Тем не менее, я попробую привести их некоторые различия:

• ArrayList реализует интерфейс List, в то время как HashSet реализует интерфейс Set;

• В ArrayList возможен доступ по индексу элемента: операция get имеет алгоритмическую сложность O(1), а в HashSet необходимый элемент можно получить лишь путём перебора, а это у нас от O(1) до O(n);

• ArrayList допускает присутствие дубликатов элементов. В HashSet все элементы уникальны: добавить в HashSet элемент, аналог которого уже присутствует в коллекции, не получится (проверка дубликатов ведется по hashcode, отсюда и название этой коллекции);

• ArrayList реализован с помощью внутреннего массива, а HashSet реализован с помощью внутренней HashMap;

• ArrayList поддерживает порядок вставки элементов, в то время как HashSet — это неупорядоченное множество и не поддерживает порядок элементов;

• ArrayList допускает любое количество пустых значений (null), в HashSet можно вставить лишь одно значение null (как-никак, уникальность элементов).

91. Зачем в Java такое разнообразие имплементации динамического массива?

Ну, это скорее философский вопрос. Ну а зачем придумывают такое количество новых разнообразных технологий? Для удобства. Собственно, так же и с большим количеством имплементаций динамического массива. Ни одну из них нельзя назвать лучшей или идеальной. У каждой есть преимущество в какой-то конкретной ситуации. И наша задача — знать их различия, их сильные/слабые стороны: чтобы суметь в нужной ситуации использовать самую подходящую из них.

92. Зачем в Java такое разнообразие имплементаций key-value storage?

Здесь ситуация такая же, как и с имплементациями динамического массива. Однозначно лучших нет: у каждой есть сильные и слабые стороны. И мы, конечно, должны по максимуму использовать сильные стороны. Пример: в пакете concurrent, в котором есть множество многопоточных технологий, имеются свои Concurrent коллекции. У той же ConcurrentHashMap есть преимущество в безопасности многопоточной работы с данными в сравнении с обычной HashMap, но не в многопоточной среде она проигрывает в скорости работы. Ну а имплементации, которые ни в одной из ситуаций не бывают сильнейшими, постепенно перестают использовать. Пример: Hashtable, которая изначально задумывалась как потокобезопасная HashMap, но ConcurrentHashMap превзошла ее при работе в многопоточной среде, и в итоге о Hashtable позабыли и перестали использовать.

93. Как отсортировать коллекцию элементов?

Первое, что нужно сказать, — класс элемента коллекции должен имплементировать интерфейс Comparable и его метод compareTo. Или же нужен класс, который имплементирует Comaprator с его методом comparator. Подробнее о них можно почитать в этом посте. Оба способа указывают, каким образом нужно сравнивать объекты данного типа. При сортировке это критически важно, ведь нужно понимать принцип, по которому элементы можно сравнить. В основном используется способ через имплементацию Comparable, реализуемый непосредственно в классе, который вы хотите сортировать. В то же время применение Comparator-а более редко. Скажем, вы используете класс с какой-то библиотеки, у которого нет реализации Comparable, но вам как-то нужно будет его сортировать. Не имея возможности изменить код данного класса (кроме как расширить его), вы можете написать реализацию Comparator-а, в котором укажете, по какому принципу нужно сравнивать объекты данного класса. И еще один пример. Допустим, вам нужны разные принципы сортировки объектов одного и того же типа, поэтому вы пишете несколько Comparator-ов которые используете в разных ситуациях. Как правило, многие классы из коробки уже реализуют интерфейс Comparable — тот же String. Собственно, при их использовании вам не нужно париться, как их сравнить. Вы просто берете и используете их. Первый и самый очевидный способ — использовать коллекцию типа TreeSet или TreeMap, которые хранят элементы в ужеотсортированном порядке, согласно компаратору класса элементов. Не забывайте, что TreeMap сортирует ключи, но не значения. Если вы используете имплементацию Comparator вместо Comparable, вам нужно будет передать его объект в конструктор коллекции при создании:

TreeSet treeSet = new TreeSet(customComparator);

А что если у вас коллекция другого типа? Как её отсортировать? В этом случае подходит второй способ утилитного класса Collections — метод sort(). Он статический, поэтому всё, что вам нужно — имя класса и метод, в который передается необходимый список. Например:

Collections.sort(someList);

Если вы используете не Comparable, а реализацию Comparator, его нужно передать вторым параметром:

Collections.sort(someList, customComparator);

В итоге внутренний порядок элементов переданного списка изменится: он будет отсортирован согласно компаратору элементов. Отмечу, что передаваемый список элементов должен быть мутабельным, т.е. изменяемым, иначе метод не сработает и будет выброшено UnsupportedOperationException. В качестве третьего способа можно использовать Stream операцию sort, которая сортирует элементы коллекции, если используется имплементация Comparable:

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

если Comparator:

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

Подробнее о Stream можно почитать в этой статье. Четвертый способ — ручная реализация сортировки, например, сортировки пузырьком или сортировки слиянием.

Class Object. Equals and HashCode

94. Дайте краткую характеристику class object в Java

Во второй части разбора мы уже говорили о методах класса Object, и я напомню, что класс Object — прародитель всех классов в Java. У него есть 11 методов, которые, соответственно, наследуются всеми классами. Информацию обо всех 11 методах можно найти во второй части разбора вопросов.

95. Для чего используют Equals и HashCode в Java?

hashCode() — это метод класса Object, который наследуется всеми классами. Его задача — генерирование некоторого числа, которое представляет конкретный объект. Примером использования данного метода может служить его применение в HashMap на объекте ключа для дальнейшего определения локального хешкода, по которому определится ячейка внутреннего массива (бакета), в которой будет сохранена пара. Подробно о работе HashMap мы говорили в 9 части разбора, поэтому особо останавливаться на этом не будем. Также как правило данный метод используется в методе equals() как один из его основных инструментов определения идентичности объектов. equals() — метод класса Object, задача которого — сравнивать объекты и определять, равны они или нет. Данный метод используется повсеместно там, где нам необходимо сравнить объекты, ведь обычное сравнение через == не подходит для объектов, т.к. сравнивает только ссылки на них.

96. Расскажите про контракт между Equals и HashCode в Java?

Первое, что скажу — для корректной работы методов equals() и hashCode() их нужно правильно переопределить. После этого они должны соблюдать правила:

• одинаковые объекты, для которых сравнение через equals возвращает true, обязательно имеют одинаковые хеш-коды;
• объекты с одинаковыми хеш-кодами не всегда могут быть равны.

На этом мы и сделаем паузу до следующей части разбора!