«1. Введение
Коллекции Java — это тема, которую часто поднимают на технических собеседованиях с разработчиками Java. В этой статье рассматриваются некоторые важные вопросы, которые задают чаще всего, и на них может быть сложно ответить правильно.
2. Вопросы
Q1. Описать иерархию типов коллекций. Каковы основные интерфейсы и в чем между ними разница?
Интерфейс Iterable представляет любую коллекцию, которую можно повторить с помощью цикла for-each. Интерфейс Collection наследуется от Iterable и добавляет универсальные методы для проверки наличия элемента в коллекции, добавления и удаления элементов из коллекции, определения ее размера и т. д.
Интерфейсы List, Set и Queue наследуются от интерфейса Collection.
Список — это упорядоченная коллекция, и доступ к ее элементам можно получить по их индексу в списке.
Набор — это неупорядоченная коллекция с отдельными элементами, аналогичная математическому понятию множества.
Очередь — это коллекция с дополнительными методами для добавления, удаления и проверки элементов, полезных для удержания элементов перед обработкой.
Интерфейс карты также является частью структуры коллекции, но не расширяет коллекцию. Это задумано, чтобы подчеркнуть разницу между коллекциями и отображениями, которые трудно собрать в рамках общей абстракции. Интерфейс Map представляет собой структуру данных типа «ключ-значение» с уникальными ключами и не более чем одним значением для каждого ключа.
Q2. Описать различные реализации интерфейса карты и их различия в вариантах использования.
Одной из наиболее часто используемых реализаций интерфейса Map является HashMap. Это типичная структура данных хэш-карты, которая позволяет обращаться к элементам за постоянное время или O(1), но не сохраняет порядок и не является потокобезопасной.
Чтобы сохранить порядок вставки элементов, вы можете использовать класс LinkedHashMap, который расширяет HashMap и дополнительно связывает элементы в связанный список с прогнозируемыми накладными расходами.
Класс TreeMap хранит свои элементы в красно-черной древовидной структуре, что позволяет осуществлять доступ к элементам за логарифмическое время или O(log(n)). В большинстве случаев он медленнее, чем HashMap, но позволяет упорядочивать элементы в соответствии с некоторым компаратором.
ConcurrentHashMap — это потокобезопасная реализация хэш-карты. Он обеспечивает полный параллелизм извлечений (поскольку операция получения не влечет за собой блокировку) и высокий ожидаемый параллелизм обновлений.
Класс Hashtable присутствует в Java с версии 1.0. Он не устарел, но в основном считается устаревшим. Это потокобезопасная хеш-карта, но в отличие от ConcurrentHashMap все ее методы просто синхронизируются, а это означает, что все операции с этой картой блокируются, даже извлечение независимых значений.
Q3. Объясните разницу между Linkedlist и Arraylist.
ArrayList — это реализация интерфейса List, основанная на массиве. ArrayList внутренне обрабатывает изменение размера этого массива при добавлении или удалении элементов. Вы можете получить доступ к его элементам в постоянное время по их индексу в массиве. Однако вставка или удаление элемента подразумевает сдвиг всех последующих элементов, что может быть медленным, если массив огромен, а вставленный или удаленный элемент находится близко к началу списка.
LinkedList — это двусвязный список: отдельные элементы помещаются в объекты Node, которые имеют ссылки на предыдущий и следующий Node. Эта реализация может показаться более эффективной, чем ArrayList, если у вас много вставок или удалений в разных частях списка, особенно если список большой.
Однако в большинстве случаев ArrayList превосходит LinkedList. Даже перемещение элементов в ArrayList, хотя и является операцией O(n), реализовано в виде очень быстрого вызова System.arraycopy(). Это может даже оказаться быстрее, чем вставка O(1) LinkedList, которая требует создания экземпляра объекта Node и обновления нескольких ссылок под капотом. LinkedList также может иметь большие накладные расходы памяти из-за создания нескольких небольших объектов Node.
«
«Q4. В чем разница между Hashset и Treeset?
Классы HashSet и TreeSet реализуют интерфейс Set и представляют наборы отдельных элементов. Кроме того, TreeSet реализует интерфейс NavigableSet. Этот интерфейс определяет методы, использующие порядок элементов.
HashSet внутренне основан на HashMap, а TreeSet поддерживается экземпляром TreeMap, который определяет их свойства: HashSet не хранит элементы в каком-либо определенном порядке. Итерация по элементам в HashSet производит их в перемешанном порядке. TreeSet, с другой стороны, создает элементы по порядку в соответствии с некоторым предопределенным Компаратором.
Q5. Как Hashmap реализован в Java? Как его реализация использует методы Hashcode и Equals объектов? Какова временная сложность размещения и получения элемента из такой структуры?
Класс HashMap представляет типичную структуру данных хэш-карты с определенными вариантами дизайна.
HashMap поддерживается массивом изменяемого размера, размер которого равен степени двойки. Когда элемент добавляется в HashMap, сначала вычисляется его hashCode (значение int). Затем определенное количество младших битов этого значения используется как индекс массива. Этот индекс напрямую указывает на ячейку массива (называемую сегментом), в которую следует поместить эту пару ключ-значение. Доступ к элементу по его индексу в массиве — это очень быстрая операция O(1), которая является основной особенностью структуры хэш-карты.
Однако хэш-код не уникален, и даже для разных хэш-кодов мы можем получить одну и ту же позицию в массиве. Это называется столкновением. Существует несколько способов разрешения коллизий в структурах данных хеш-карты. В Java HashMap каждое ведро на самом деле относится не к одному объекту, а к красно-черному дереву всех объектов, которые попали в это ведро (до Java 8 это был связанный список).
Итак, когда HashMap определил корзину для ключа, он должен пройти по этому дереву, чтобы поместить пару ключ-значение на свое место. Если в корзине уже есть пара с таким ключом, она заменяется новой.
Чтобы получить объект по его ключу, HashMap снова должен вычислить хэш-код для ключа, найти соответствующее ведро, пройтись по дереву, вызвать equals для ключей в дереве и найти соответствующий.
HashMap имеет сложность O(1) или сложность с постоянным временем для размещения и получения элементов. Конечно, большое количество столкновений может снизить производительность до O(log(n)) временной сложности в худшем случае, когда все элементы попадают в одно ведро. Обычно это решается предоставлением хорошей хеш-функции с равномерным распределением.
Когда внутренний массив HashMap заполняется (подробнее об этом в следующем вопросе), он автоматически увеличивается в два раза. Эта операция подразумевает повторное хеширование (перестроение внутренних структур данных), что является дорогостоящим, поэтому вам следует заранее спланировать размер вашей HashMap.
Q6. Какова цель параметров начальной емкости и коэффициента загрузки хэш-карты? Каковы их значения по умолчанию?
Аргумент initialCapacity конструктора HashMap влияет на размер внутренней структуры данных HashMap, но рассуждать о фактическом размере карты немного сложно. Внутренняя структура данных HashMap представляет собой массив с размером, равным степени двойки. Таким образом, значение аргумента initialCapacity увеличивается до следующей степени двойки (например, если вы установите его равным 10, фактический размер внутреннего массива будет равен 16).
Коэффициент загрузки HashMap – это отношение количества элементов к количеству сегментов (т. е. к размеру внутреннего массива). Например, если HashMap с 16 сегментами содержит 12 элементов, его коэффициент загрузки составляет 12/16 = 0,75. Высокий коэффициент загрузки означает много столкновений, что, в свою очередь, означает, что размер карты должен быть изменен до следующей степени двойки. Таким образом, аргумент loadFactor представляет собой максимальное значение коэффициента загрузки карты. Когда карта достигает этого коэффициента загрузки, она изменяет размер своего внутреннего массива до следующего значения степени двойки.
«InitialCapacity по умолчанию равен 16, а loadFactor по умолчанию равен 0,75, поэтому вы можете поместить 12 элементов в HashMap, экземпляр которого был создан с помощью конструктора по умолчанию, и он не будет изменять размер. То же самое касается HashSet, который поддерживается внутренним экземпляром HashMap.
Следовательно, не так просто придумать начальный объем емкости, удовлетворяющий вашим потребностям. Вот почему в библиотеке Guava есть методы Maps.newHashMapWithExpectedSize() и Sets.newHashSetWithExpectedSize(), которые позволяют создавать HashMap или HashSet, которые могут содержать ожидаемое количество элементов без изменения размера.
Q7. Описать специальные коллекции для перечислений. Каковы преимущества их внедрения по сравнению с регулярными сборами?
EnumSet и EnumMap являются специальными реализациями интерфейсов Set и Map соответственно. Вы всегда должны использовать эти реализации, когда имеете дело с перечислениями, потому что они очень эффективны.
EnumSet — это просто битовый вектор с «единицами» в позициях, соответствующих порядковым значениям перечислений, присутствующих в наборе. Чтобы проверить, находится ли значение перечисления в наборе, реализация просто должна проверить, является ли соответствующий бит в векторе «единицей», что является очень простой операцией. Точно так же EnumMap — это массив, доступ к которому осуществляется с помощью порядкового значения перечисления в качестве индекса. В случае с EnumMap нет необходимости вычислять хеш-коды или разрешать коллизии.
Q8. В чем разница между отказоустойчивыми и отказоустойчивыми итераторами?
Итераторы для разных коллекций являются либо отказоустойчивыми, либо отказоустойчивыми, в зависимости от того, как они реагируют на одновременные модификации. Параллельная модификация — это не только модификация коллекции из другого потока, но и модификация из того же потока, но с использованием другого итератора или непосредственное изменение коллекции.
Отказоустойчивые итераторы (возвращаемые HashMap, ArrayList и другими коллекциями, не поддерживающими потокобезопасность) перебирают внутреннюю структуру данных коллекции и выдают исключение ConcurrentModificationException, как только обнаруживают параллельную модификацию.
Отказоустойчивые итераторы (возвращаемые потокобезопасными коллекциями, такими как ConcurrentHashMap, CopyOnWriteArrayList) создают копию структуры, по которой они выполняют итерацию. Они гарантируют безопасность от одновременных модификаций. Их недостатки включают чрезмерное потребление памяти и итерацию по возможно устаревшим данным в случае изменения коллекции.
Q9. Как можно использовать интерфейсы Comparable и Comparator для сортировки коллекций?
Интерфейс Comparable — это интерфейс для объектов, которые можно сравнивать в определенном порядке. Его единственным методом является compareTo, который оперирует двумя значениями: самим объектом и объектом-аргументом того же типа. Например, Integer, Long и другие числовые типы реализуют этот интерфейс. String также реализует этот интерфейс, а его метод compareTo сравнивает строки в лексикографическом порядке.
Интерфейс Comparable позволяет сортировать списки соответствующих объектов с помощью метода Collections.sort() и поддерживать порядок итерации в коллекциях, реализующих SortedSet и SortedMap. Если ваши объекты можно сортировать с помощью некоторой логики, они должны реализовывать интерфейс Comparable.
Интерфейс Comparable обычно реализуется с использованием естественного порядка элементов. Например, все целые числа упорядочены от меньшего к большему значению. Но иногда вы можете захотеть реализовать другой вид упорядочения, например, чтобы отсортировать числа в порядке убывания. Здесь может помочь интерфейс Comparator.
Класс объектов, которые вы хотите отсортировать, не должен реализовывать этот интерфейс. Вы просто создаете реализующий класс и определяете метод сравнения, который получает два объекта и решает, как их упорядочить. Затем вы можете использовать экземпляр этого класса, чтобы переопределить естественный порядок метода Collections.sort() или экземпляров SortedSet и SortedMap.
«Поскольку интерфейс Comparator является функциональным интерфейсом, вы можете заменить его лямбда-выражением, как в следующем примере. Он показывает упорядочивание списка с использованием естественного порядка (интерфейс Integer Comparable) и с использованием пользовательского итератора (интерфейс Comparator\u003cInteger\u003e).
«
Q9. How Can You Use Comparable and Comparator Interfaces to Sort Collections?
The Comparable interface is an interface for objects that can be compared according to some order. Its single method is compareTo, which operates on two values: the object itself and the argument object of the same type. For instance, Integer, Long, and other numeric types implement this interface. String also implements this interface, and its compareTo method compares strings in lexicographical order.
The Comparable interface allows to sort lists of corresponding objects with the Collections.sort() method and uphold the iteration order in collections that implement SortedSet and SortedMap. If your objects can be sorted using some logic, they should implement the Comparable interface.
The Comparable interface usually is implemented using natural ordering of the elements. For instance, all Integer numbers are ordered from lesser to greater values. But sometimes you may want to implement another kind of ordering, for instance, to sort the numbers in descending order. The Comparator interface can help here.
The class of the objects you want to sort does not need to implement this interface. You simply create an implementing class and define the compare method which receives two objects and decides how to order them. You may then use the instance of this class to override the natural ordering of the Collections.sort() method or SortedSet and SortedMap instances.
As the Comparator interface is a functional interface, you may replace it with a lambda expression, as in the following example. It shows ordering a list using a natural ordering (Integer‘s Comparable interface) and using a custom iterator (Comparator<Integer> interface).
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1);
assertEquals(new Integer(1), list1.get(0));
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1, (a, b) -> b - a);
assertEquals(new Integer(5), list1.get(0));