1. введение
Коллекции Java-это тема, часто поднимаемая в технических интервью для разработчиков Java. В этой статье рассматриваются некоторые важные вопросы, которые задаются чаще всего и могут быть сложными для правильного ответа.
2. Вопросы
Q1. Опишите иерархию типов коллекций. Каковы Основные Интерфейсы и Каковы Различия между Ними?
Интерфейс Iterable представляет любую коллекцию, которую можно повторить с помощью цикла for-each . Интерфейс Collection наследуется от Iterable и добавляет общие методы для проверки наличия элемента в коллекции, добавления и удаления элементов из коллекции, определения его размера и т. Д.
Интерфейсы List , Set и Queue наследуются от интерфейса Collection .
List – это упорядоченная коллекция, и доступ к ее элементам можно получить по их индексу в списке.
Множество – это неупорядоченная коллекция с различными элементами, аналогичная математическому понятию множества.
Queue – это коллекция с дополнительными методами добавления, удаления и проверки элементов, полезная для хранения элементов перед обработкой.
Интерфейс Map также является частью структуры коллекции, но он не расширяет Collection . Это сделано специально, чтобы подчеркнуть разницу между коллекциями и отображениями, которые трудно собрать в рамках общей абстракции. Интерфейс Map представляет структуру данных ключ-значение с уникальными ключами и не более чем одним значением для каждого ключа.
Q2. Опишите Различные реализации интерфейса карты и их Различия в вариантах использования.
Одной из наиболее часто используемых реализаций интерфейса Map является HashMap . Это типичная структура данных hashmap, которая позволяет получать доступ к элементам в постоянное время или O(1), но не сохраняет порядок и не является потокобезопасной .
Чтобы сохранить порядок вставки элементов, вы можете использовать класс LinkedHashMap , который расширяет HashMap и дополнительно связывает элементы в связанный список с предсказуемыми накладными расходами.
Класс TreeMap хранит свои элементы в красно-черной древовидной структуре, которая позволяет получать доступ к элементам в логарифмическом времени или O(log(n)). В большинстве случаев он медленнее, чем HashMap , но позволяет сохранять элементы в порядке в соответствии с некоторым Компаратором .
ConcurrentHashMap -это потокобезопасная реализация хэш-карты. Он обеспечивает полный параллелизм извлечения (поскольку операция get не влечет за собой блокировку) и высокий ожидаемый параллелизм обновлений.
Класс Hashtable существует в Java с версии 1.0. Он не устарел, но в основном считается устаревшим. Это потокобезопасная хэш-карта, но в отличие от ConcurrentHashMap , все ее методы просто синхронизированы , что означает, что все операции на этой карте блокируются, даже извлечение независимых значений.
Q3. Объясните разницу между Linkedlist и Arraylist.
ArrayList – это реализация интерфейса List , основанного на массиве. ArrayList внутренне обрабатывает изменение размера этого массива при добавлении или удалении элементов. Вы можете получить доступ к его элементам в постоянное время по их индексу в массиве. Однако вставка или удаление элемента приводит к смещению всех последующих элементов, что может быть медленным, если массив огромен, а вставленный или удаленный элемент находится близко к началу списка.
LinkedList -это двусвязный список: отдельные элементы помещаются в объекты Node , которые имеют ссылки на предыдущий и следующий Node . Эта реализация может показаться более эффективной, чем ArrayList , если у вас много вставок или удалений в разных частях списка, особенно если список большой.
Однако в большинстве случаев ArrayList превосходит Связанный список . Даже элементы сдвигаются в ArrayList , будучи операцией O(n), реализуется как очень быстрый вызов System.arraycopy () . Он может даже появиться быстрее, чем Связанный список ‘sO(1) вставка, которая требует создания экземпляра объекта Node и обновления нескольких ссылок под капотом. Связанный список также может иметь большие накладные расходы на память из-за создания нескольких небольших Узлов объектов.
Q4. В чем разница между Hashset и Treeset?
Оба класса HashSet и TreeSet реализуют интерфейс Set и представляют наборы различных элементов. Кроме того, TreeSet реализует интерфейс NavigableSet . Этот интерфейс определяет методы, которые используют преимущества упорядочения элементов.
HashSet внутренне основан на HashMap , а TreeSet поддерживается экземпляром TreeMap , который определяет их свойства: HashSet не сохраняет элементы в каком-либо определенном порядке. Итерация по элементам в HashSet создает их в перемешанном порядке. TreeSet , с другой стороны, производит элементы в порядке в соответствии с некоторым предопределенным Компаратором .
Q5. Как реализована Hashmap в Java? Как его реализация использует хэш-код и методы объектов Equals? Какова временная сложность Размещения и получения элемента из Такой структуры?
Класс HashMap представляет типичную структуру данных hashmap с определенными вариантами дизайна.
HashMap поддерживается массивом с возможностью изменения размера, который имеет размер степени два. Когда элемент добавляется в HashMap , сначала вычисляется его hashCode (значение int ). Затем определенное количество младших битов этого значения используется в качестве индекса массива. Этот индекс непосредственно указывает на ячейку массива (называемую ведром), в которой должна быть размещена эта пара ключ-значение. Доступ к элементу по его индексу в массиве-это очень быстрая операция O(1), которая является основной особенностью структуры хэш-карты.
Однако Хэш-код не является уникальным, и даже для разных хэш-кодов мы можем получить одну и ту же позицию массива. Это называется столкновением. Существует несколько способов разрешения коллизий в структурах данных hashmap. В Java HashMap каждое ведро фактически ссылается не на один объект, а на красно-черное дерево всех объектов, которые попали в это ведро (до Java 8 это был связанный список).
Поэтому, когда HashMap определил ведро для ключа, он должен пересечь это дерево, чтобы поместить пару ключ-значение на свое место. Если пара с таким ключом уже существует в корзине, она заменяется новой.
Чтобы получить объект по его ключу, HashMap снова должен вычислить hashCode для ключа, найти соответствующее ведро, пересечь дерево, вызвать equals по ключам в дереве и найти соответствующий.
HashMap имеет O(1) сложность, или сложность с постоянным временем, размещения и получения элементов. Конечно, множество столкновений может снизить производительность до O(log(n)) временной сложности в худшем случае, когда все элементы попадают в одно ведро. Обычно это решается путем предоставления хорошей хэш-функции с равномерным распределением.
Когда внутренний массив HashMap заполняется (подробнее об этом в следующем вопросе), его размер автоматически увеличивается в два раза. Эта операция приводит к повторному хэшированию (перестройке внутренних структур данных), что является дорогостоящим, поэтому вам следует заранее спланировать размер вашей HashMap .
Q6. Какова цель параметров Начальной емкости и коэффициента загрузки хэш-карты? Каковы Их Значения По Умолчанию?
Аргумент initial Capacity конструктора HashMap влияет на размер внутренней структуры данных HashMap , но рассуждать о фактическом размере карты немного сложно. Внутренняя структура данных HashMap представляет собой массив с размером степени два. Таким образом, значение аргумента initial Capacity увеличивается до следующей степени двойки (например, если вы установите его равным 10, фактический размер внутреннего массива будет равен 16).
Коэффициент загрузки HashMap – это отношение количества элементов, деленное на количество ячеек (т. Е. Размер внутреннего массива). Например, если 16-ведро HashMap содержит 12 элементов, его коэффициент загрузки равен.75. Высокий коэффициент нагрузки означает много столкновений, что, в свою очередь, означает, что размер карты должен быть изменен до следующей степени двух. Таким образом, аргумент load Factor является максимальным значением коэффициента загрузки карты. Когда карта достигает этого коэффициента нагрузки, она изменяет размер своего внутреннего массива до следующего значения степени двух.
initialCapacity по умолчанию равен 16, а loadFactor по умолчанию равен 0,75, поэтому вы можете поместить 12 элементов в HashMap , который был создан с помощью конструктора по умолчанию, и он не будет изменять размер. То же самое касается HashSet , который поддерживается внутренним экземпляром HashMap .
Следовательно, нетривиально придумать начальную емкость , которая удовлетворяет вашим потребностям. Вот почему в библиотеке Guava есть методы Maps.newHashMapWithExpectedSize() и Sets.newHashSetWithExpectedSize () , которые позволяют создавать HashMap или HashSet , которые могут содержать ожидаемое количество элементов без изменения размера.
Q7. Опишите Специальные коллекции для перечислений. Каковы преимущества Их внедрения По сравнению с обычными Сборами?
EnumSet и EnumMap являются специальными реализациями интерфейсов Set и Map соответственно. Вы всегда должны использовать эти реализации, когда имеете дело с перечислениями, потому что они очень эффективны.
EnumSet – это просто битовый вектор с “единицами” в позициях, соответствующих порядковым значениям перечислений, присутствующих в наборе. Чтобы проверить, находится ли значение перечисления в наборе, реализация просто должна проверить, является ли соответствующий бит в векторе “единицей”, что является очень простой операцией. Аналогично, EnumMap – это массив, доступ к которому осуществляется с порядковым значением enum в качестве индекса. В случае EnumMap нет необходимости вычислять хэш-коды или разрешать коллизии.
Q8. В чем разница между Быстродействующими и Безотказными итераторами?
Итераторы для разных коллекций либо быстры, либо надежны, в зависимости от того, как они реагируют на одновременные изменения. Параллельная модификация-это не только модификация коллекции из другого потока, но и модификация из того же потока, но с использованием другого итератора или непосредственным изменением коллекции.
Отказоустойчивые итераторы (возвращаемые HashMap , ArrayList и другими небезопасными для потоков коллекциями) повторяют внутреннюю структуру данных коллекции и выбрасывают ConcurrentModificationException , как только обнаруживают параллельную модификацию.
Отказоустойчивые итераторы (возвращаемые потокобезопасными коллекциями, такими как ConcurrentHashMap , CopyOnWriteArrayList ) создают копию структуры, по которой они выполняют итерацию. Они гарантируют безопасность от одновременных модификаций. Их недостатки включают чрезмерное потребление памяти и повторение, возможно, устаревших данных в случае изменения коллекции.
Q9. Как можно использовать интерфейсы Сравнения и Компаратора для сортировки коллекций?
Интерфейс Comparable – это интерфейс для объектов, которые можно сравнивать в определенном порядке. Его единственным методом является compare To , который оперирует двумя значениями: самим объектом и объектом аргумента того же типа. Например, Integer , Long и другие числовые типы реализуют этот интерфейс. String также реализует этот интерфейс, и его метод compareTo сравнивает строки в лексикографическом порядке.
Интерфейс Comparable позволяет сортировать списки соответствующих объектов с помощью метода Collections.sort() и поддерживать порядок итераций в коллекциях, реализующих SortedSet и SortedMap . Если ваши объекты могут быть отсортированы с использованием некоторой логики, они должны реализовать интерфейс Comparable .
Интерфейс Comparable обычно реализуется с использованием естественного упорядочения элементов. Например, все Целочисленные числа упорядочены от меньших к большим значениям. Но иногда вам может потребоваться реализовать другой вид упорядочения, например, для сортировки чисел в порядке убывания. Здесь может помочь интерфейс Comparator .
Класс объектов, которые вы хотите отсортировать, не нуждается в реализации этого интерфейса. Вы просто создаете реализующий класс и определяете метод compare , который получает два объекта и решает, как их упорядочить. Затем вы можете использовать экземпляр этого класса для переопределения естественного порядка Collections.sort() метода или SortedSet и SortedMap экземпляров.
Поскольку интерфейс Comparator является функциональным интерфейсом, вы можете заменить его лямбда-выражением, как в следующем примере. Он показывает упорядочение списка с использованием естественного порядка ( Integer ‘s Comparable interface) и с использованием пользовательского итератора ( Comparator interface).
Listlist1 = Arrays.asList(5, 2, 3, 4, 1); Collections.sort(list1); assertEquals(new Integer(1), list1.get(0)); List list1 = Arrays.asList(5, 2, 3, 4, 1); Collections.sort(list1, (a, b) -> b - a); assertEquals(new Integer(5), list1.get(0));