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() . Это может даже оказаться быстрее, чем вставка LinkedList O (1), которая требует создания экземпляра объекта Node и обновления нескольких ссылок под капотом. LinkedList также может иметь большие накладные расходы памяти из-за создания нескольких небольших объектов Node .
Q4. В чем разница между Hashset и Treeset?
Классы HashSet и TreeSet реализуют интерфейс Set и представляют наборы отдельных элементов. Кроме того, TreeSet реализует интерфейс NavigableSet . Этот интерфейс определяет методы, использующие порядок элементов. `` ``
HashSet внутренне основан на HashMap , а TreeSet поддерживается экземпляром TreeMap , который определяет их свойства: HashSet не хранит элементы в каком-либо определенном порядке. Итерация по элементам в HashSet производит их в перемешанном порядке. TreeSet , с другой стороны, создает элементы в порядке, соответствующем некоторому предопределенному Comparator .
Q5. Как Hashmap реализован в Java? Как его реализация использует методы Hashcode и Equals объектов? Какова временная сложность размещения и получения элемента из такой структуры?
Класс HashMap представляет типичную структуру данных хэш-карты с определенными вариантами дизайна.
HashMap поддерживается массивом изменяемого размера, размер которого равен степени двойки. Когда элемент добавляется в HashMap , сначала вычисляется его hashCode (значение int ). Затем определенное количество младших битов этого значения используется как индекс массива. Этот индекс напрямую указывает на ячейку массива (называемую сегментом), в которую следует поместить эту пару ключ-значение. Доступ к элементу по его индексу в массиве — это очень быстрая операция O(1), которая является основной особенностью структуры хэш-карты.
Однако hashCode не уникален, и даже для разных hashCode мы можем получить одну и ту же позицию в массиве. Это называется столкновением. Существует несколько способов разрешения коллизий в структурах данных хеш-карты. В Java HashMap каждое ведро на самом деле относится не к одному объекту, а к красно-черному дереву всех объектов, которые попали в это ведро (до Java 8 это был связанный список).
Таким образом, когда HashMap определил сегмент для ключа, он должен пройти по этому дереву, чтобы поместить пару ключ-значение на свое место. Если в корзине уже есть пара с таким ключом, она заменяется новой.
Чтобы получить объект по его ключу, HashMap снова должен вычислить хэш -код для ключа, найти соответствующее ведро, пройти по дереву, вызвать равенство для ключей в дереве и найти соответствующий.
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<Integer> ).
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));