Java Collection Framework, необходимая для собеседований

Java

вот изображение:

Коллекции Java, также известные как контейнеры, в основном состоят из两大接口 (Interface)Полученный из:
Collection 和 Map

Как следует из названия, контейнеры используются для хранения данных.

Итак, разница между этими двумя интерфейсами:

  • Коллекция хранит один элемент;
  • Карта хранит пары ключ-значение.

То есть в Коллекцию помещаются одиночные собаки, а в Карту - пары. (Так где ты принадлежишь?

Изучая эти ансамблевые фреймворки, я думаю, что есть 4 цели:

  1. Выяснить соответствие между каждым интерфейсом и классом;
  2. Для каждого интерфейса и класса ознакомьтесь с часто используемыми API;
  3. Для разных сценариев можно выбрать подходящую структуру данных и проанализировать преимущества и недостатки;
  4. Изучите дизайн исходного кода, и вы должны быть в состоянии ответить на интервью.

Что касается Map, предыдущая статья о HashMap была очень тщательной и подробной, поэтому в этой статье они повторяться не будут. Если вы не читали статью, пожалуйста, перейдите на официальный аккаунт и ответьте "HashMap"Посмотрите на статью~

Collection

Давайте сначала посмотрим на коллекцию верхнего уровня.

В Collection также определено множество методов, и эти методы также будут унаследованы в различных подинтерфейсах и классах реализации, и использование этих API также распространено в повседневной работе и на собеседованиях, поэтому давайте сначала рассмотрим эти методы.

Набор операций представляет собой не что иное, как четыре категории «добавление, удаление, изменение и проверка», также называемыеCRUD:

Create, Read, Update, and Delete.

Затем я также делю эти API на следующие четыре категории:

Функции метод
увеличивать add()/addAll()
Удалить remove()/ removeAll()
изменять Не в интерфейсе коллекции
чек contains()/ containsAll()
разное isEmpty()/size()/toArray()

Давайте посмотрим на это подробно:

увеличивать: 

boolean add(E e);

add()Тип данных, передаваемый методом, должен быть Object, поэтому при записи базовых типов данных будет выполняться автоупаковка и автораспаковка.

Есть другой способaddAll(), вы можете добавить в этот набор элементы из другого набора.

boolean addAll(Collection<? extends E> c);

Удалить: 

boolean remove(Object o);

remove()— указанный элемент для удаления.

это иaddAll()соответствующий,
естественно естьremoveAll(), состоит в том, чтобы удалить все элементы множества B.

boolean removeAll(Collection<?> c);

изменять:

Прямой операции по изменению элементов в Интерфейсе Коллекции нет, в любом случае для завершения изменения можно выполнить удаление и добавление!

чек:

  • Проверьте, есть ли в коллекции определенный элемент:
boolean contains(Object o);
  • Проверьте, содержит ли множество A множество B:
boolean containsAll(Collection<?> c);

Также есть некоторые операции над коллекцией в целом:

  • Проверьте, пуста ли коллекция:
boolean isEmpty();
  • Размер коллекции:
int size();
  • Преобразовать коллекцию в массив:
Object[] toArray();

Выше приведены часто используемые API в Collection.

Он определен в интерфейсе, и подклассу он не нужен.

Конечно, подклассы также будут иметь некоторые собственные реализации, так что они будут иметь разные структуры данных.

Тогда давайте рассмотрим их один за другим.

List

Самая большая особенность List:有序,可重复.

Посмотрите, что написано на официальном сайте:

An ordered collection (also known as a sequence).

Unlike sets, lists typically allow duplicate elements.

На этот раз также заявлены характеристики Сета, что полностью противоположно Списку.无序,不重复из.

Существует два способа реализации List, LinkedList и ArrayList.Наиболее распространенный вопрос на собеседованиях — как выбрать эти две структуры данных.

Для этого типа проблемы выбора:
Во-первых, подумайте, может ли структура данныхвыполнить необходимую функцию;
Если это можно сделать, то второй – рассмотреть, какойболее эффективным.

(Все так.

Давайте посмотрим на API этих двух классов и их временную сложность:

Функции метод ArrayList LinkedList
увеличивать add(E e) O(1) O(1)
увеличивать add(int index, E e) O(n) O(n)
Удалить remove(int index) O(n) O(n)
Удалить remove(E e) O(n) O(n)
изменять set(int index, E e) O(1) O(n)
чек get(int index) O(1) O(n)

Небольшое объяснение:

add(E e)Это добавление элементов в хвост.Хотя ArrayList может расширяться, амортизированная временная сложность по-прежнему составляет O (1).

add(int index, E e)Это добавление элемента в определенную позицию. LinkedList должен сначала найти эту позицию, а затем добавить этот элемент. Хотя простое действие «добавление» — это O (1), для нахождения этой позиции по-прежнему требуется O (n). (Некоторые люди думают, что это O(1), просто объясните это интервьюеру и отказывайтесь нести суть.

remove(int index)заключается в удалении элемента по этому индексу, поэтому

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

remove(E e)это первый элемент, видимый remove, затем

  • ArrayList должен сначала найти этот элемент, этот процесс - O(n), а затем переместиться на одну позицию после его удаления, это еще больше O(n), а общее количество по-прежнему O(n);
  • LinkedList также должен сначала найти, этот процесс равен O(n), а затем удалить, этот процесс равен O(1), а общее количество равно O(n).

В чем причина разницы во временной сложности?

отвечать:

  • Поскольку ArrayList реализован с помощью массивов.

  • Самая большая разница между массивом и связанным списком заключается в том, чтоМассивы имеют произвольный доступ.

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

Другими словами, в двух функциях «проверки изменений», поскольку доступ к массиву возможен случайным образом, эффективность ArrayList высока.

А как насчет "добавлений и удалений"?

Если вы не считаете время, чтобы найти этот элемент,

Из-за физической непрерывности массива, когда вы хотите добавить или удалить элементы, это нормально в конце, но другие места заставят последующие элементы перемещаться, поэтому эффективность низкая; в то время как связанный список может легко отключить соединение со следующим элементом, вставка новых элементов напрямую или удаление старых элементов.

Но, на самом деле, вы не можете игнорировать время, чтобы найти элемент. . . А если операция в конце, то ArrayList будет быстрее, когда объем данных большой.

так:

  1. Измените флажок, чтобы выбрать ArrayList;
  2. Добавьте или удалите выделение ArrayList в конце;
  3. В других случаях, если временная сложность одинакова, рекомендуется использовать ArrayList, так как накладные расходы меньше или использование памяти более эффективно.

Vector

В качестве последнего пункта знаний о List давайте поговорим о Vector. Это также пост, разоблачающий возраст, используемый большими парнями.

Как и ArrayList, Vector также наследуется от java.util.AbstractList, а нижний уровень также реализован с помощью массивов.

Но теперь он устарел, потому что... он добавляет слишком много синхронизации!

Любая выгода имеет свою цену.Цена потокобезопасности - низкая эффективность, которая легко может стать узким местом в некоторых системах, поэтому сейчас все уже не добавляют синхронизацию на уровне структуры данных, а перекладывают эту задачу на наших программистов ==

Затем в интервью часто задавали вопросы: в чем разница между Vector и ArrayList, оно недостаточно полно, чтобы ответить на это.

Взгляните на ответы, получившие наибольшее количество голосов о переполнении стека:

Одна из них — проблема безопасности потоков, о которой только что говорилось;
Во-вторых, разница в том, насколько расширяться при расширении.

Это должно смотреть на исходный код:

Это реализация расширения ArrayList, этоАрифметический сдвиг вправоОперация состоит в том, чтобы сдвинуть двоичный код этого числа на один бит вправо, а крайний левыйбит знака дополнения, но поскольку у емкости нет отрицательного числа, она все равно заполнена 0.

Эффект смещения на одно место вправо состоит в делении на 2, тогда новая определяемая емкость является исходной емкостью.1,5 раза.

Давайте посмотрим на Вектора:

Поскольку обычно мы не определяем capacityIncrement, по умолчанию этоУдвойте емкость.

Если вы ответите на эти два пункта, все будет в порядке.

Queue & Deque

Очередь — это линейная структура данных, которая входит и выходит на другом конце, в то время как Deque может входить и выходить на обоих концах.

Queue

Интерфейс Queue в Java немного изрыт, вообще говоря, семантика очередейпервым пришел-первым вышел(ФИФО).

Но здесь есть исключение, то есть PriorityQueue, также называемый heap, выходит не по порядку времени, а выходит согласно заданному приоритету, и его работа не O(1), расчет временной сложности немного сложно, мы откроем отдельную статью позже.

Этот метод очередиОфициальный сайт[1]Это все в сумме, у него два набора API, а базовые функции одинаковые, а как насчет:

  • Группа выдаст исключение;
  • Другой набор возвращает специальное значение.
Функции генерировать исключение возвращаемое значение
увеличивать add(e) offer(e)
Удалить remove() poll()
вуаля element() peek()

Зачем бросать исключение?

  • Например, если очередь пуста, функция remove() сгенерирует исключение, а poll() вернет null, element() сгенерирует исключение, а peek() вернет null.

Тогда как add(e) может генерировать исключение?

Некоторые очереди имеют ограничения емкости, напримерBlockingQueue, то если он достиг своей максимальной емкости и не будет расширяться, будет выброшено исключение, а если offer(e), то будет возвращено значение false.

Как выбрать? :

  • Во-первых, используйте еготот же набор API, чтобы быть унифицированным до и после;

  • Во-вторых, по требованию. Если вам нужно выбрасывать исключения, используйте выбрасывание исключений; но они вам не нужны при решении арифметических задач, поэтому выбирайте группу, которая возвращает специальные значения.

Deque

В деку можно войти и выйти с обоих концов.Естественно, есть операции на первой стороне и операции на последней стороне.С каждой стороны две группы, одна выдает исключение, а другая возвращает специальное значение:

Функции генерировать исключение возвращаемое значение
увеличивать addFirst(e)/ addLast(e) offerFirst(e)/ offerLast(e)
Удалить removeFirst()/ removeLast() pollFirst()/ pollLast()
вуаля getFirst()/ getLast() peekFirst()/ peekLast()

Таким же образом используйте ту же группу.

Эти API-интерфейсы Queue и Deque имеют временную сложность O (1), что точно соответствует амортизированной временной сложности.

Класс реализации

Для них существует три класса реализации:

так,

  • Если вы хотите достичь семантики "нормальной очереди - первый пришел, первый вышел", используйте для этого LinkedList или ArrayDeque;
  • Если вы хотите реализовать семантику «очереди с приоритетом», используйте PriorityQueue;
  • Если вы хотите добиться семантики "стека", используйте ArrayDeque.

Давайте посмотрим на них один за другим.

При реализации обычной очередиКак выбрать между LinkedList или ArrayDeque?

посмотриStackOverflow[2]Ответ, за который проголосовали:

В заключение, ArrayDeque рекомендуется из-за его высокой эффективности, а LinkedList будет иметь другие накладные расходы.

В чем разница между ArrayDeque и LinkedList?

Все еще по тому же вопросу только что, это лучшее резюме, которое я думаю:

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

Итак, если вам не нужно хранить нулевые значения, выберите ArrayDeque!

Затем, если высокопоставленный интервьюер спросит вас, при каких обстоятельствах вы бы предпочли использовать LinkedList?

  • О: До Java 6. . . Поскольку ArrayDeque существует только после Java 6. .

Что касается совместимости версий, то в реальной работе нам приходится идти на некоторые компромиссы. .

Последний вопрос касается стека.

Stack

Стек семантическиПоследний пришел, первый ушел (LIFO)линейная структура данных.

Есть много часто задаваемых вопросов на собеседованиях, в которых используются стеки, например, проблема подключения к воде.Хотя оптимальное решение — использование двойных указателей, также необходимо понимать, что использование стеков — наиболее интуитивное решение.Я напишу это позже, когда У меня есть возможность.

Так как же реализован стек в Java?

Несмотря на то, что в Java есть класс Stack, в официальных документах сказано, что его использование запрещено!

Причина также очень проста, потому что Vector устарел, а Stack унаследован от Vector.

Итак, если вы хотите достичь семантики стека, используйте ArrayDeque:

Deque<Integer> stack = new ArrayDeque<>();

Set

Последний Сет, я только что сказал, что специфика Сета заключается в无序,不重复из.

Это согласуется с понятием «множество» в математике.

Существует три общих класса реализации Set:

HashSet: Ключ Hashmap используется для хранения элементов.Главная особенность в том, что он неупорядочен, а базовые операции имеют временную сложность O(1), что очень быстро.

LinkedHashSet: это структура HashSet + LinkedList, которая характеризуется не только временной сложностью O(1), но и сохранением порядка вставки.

TreeSet: Используется красно-черная древовидная структура, которая характеризуется упорядоченностью, и может быть отсортирована естественной сортировкой или пользовательским компаратором, недостаток в том, что скорость запроса не такая высокая, как у HashSet.

что каждый наборнизкоуровневая реализацияПо сути, это соответствующая карта:

Значение помещается в ключ на карте, а PRESENT помещается в значение, которое является статическим объектом, эквивалентным заполнителю, и каждый ключ указывает на этот объект.

такой конкретныйПринцип реализации,CRUDчетыре операции ихэш-коллизия,hashCode()/equals()Другие вопросы обсуждались в статье о HashMap, поэтому я не буду повторяться здесь, а те, кто не читал, могут ответить на "HashMap" в фоновом режиме официального аккаунта, чтобы получить статью~

Суммировать

Возвращаясь к картинке в начале, она яснее?

Под каждой структурой данных на самом деле много контента, например, PriorityQueue в этой статье подробно не рассматривается, потому что этот парень будет долго рассказывать. .

Если вы считаете, что статья хорошая, лайк 👍 в конце статьи вернулся,Не забывайте ставить лайки и смотреть за меня~

Наконец, многие читатели задавали мне вопросы о группе обмена, потому что я не сделал этого из-за неудобного управления разницей во времени.

Но теперь я нашел профессионального администратора, чтобы управлять им вместе со мной, так что «Секретная база сестры Ци» находится в стадии подготовки, и я приглашу некоторых важных шишек из дома и из-за границы, чтобы они познакомили вас с другой точкой зрения.

Затем в середине-начале июля планируется открытие первого этапа группы общения, в это время я отправлю приглашение в круг друзей, так что следите за новостями!

использованная литература

[1]

Queue: https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

 [2]

ArrayDeque vs LinkedList: https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist

Категории