Назовите 18 видов очередей на одном дыхании, и собеседование стабильно!

Java
Назовите 18 видов очередей на одном дыхании, и собеседование стабильно!

говорящий«21 картинка, объясняющая ненадежность коллекций»В этой статье я оставил пасхальное яйцо, котороеОчередьЯ еще не говорил об этом, на этот раз мы сосредоточимся на семействе Queue в Java, которое включает в себя в общей сложности18вид очереди. Это наверное есть на рынкесамый полныйОбъясните очередь.

Основное содержание этой статьи следующее:

本篇主要内容

Чтобы помочь вам подытожить хорошую очередь блокировки:

18种Queue总结

1. Очередь представить себя

队列原理图

1.1 Представление очереди

привет всем, мое английское имяQueue, Китайское имя队列, будь то в реальной жизни или в компьютерном мире, я играю очень важную роль~

я数据结构, вы можете думать обо мне как о массиве, элементы входят в меня с одного конца и выходят с другого конца, что называется принципом FIFO (принцип первого входа, первого выхода).

У меня также есть два брата:List(список),Set(комплект), они всеCollectionМой сын, у меня тоже есть дальний родственник:Map(карта). Они всеjava.utilСобери членов этой большой семьи~

1.2 Реальные сценарии

  • Номер ряда Haidilao и другие места (первый номер ряда входит в ресторан первым)
  • Почтальон доставляет письма (почтовые ящики стоят в очереди)

1.3 Сценарии в компьютерном мире

  • очередь сообщений RabbitMQ
  • Протокол UDP (получатель сохраняет сообщение в очереди и считывает данные из очереди)

2. Строительство высотного здания и обзор общей ситуации

18 очередей разделены на три категории:Интерфейсы, абстрактные классы, обычные классы.

Очень полезно понять следующие отношения наследования и реализации, чтобы позже понять 18 видов очередей.

18个Queue的继承实现关系图

  • Queueинтерфейснаследовать Collectionинтерфейс,Collectionинтерфейснаследовать Iterableинтерфейс
  • BlockingQueueинтерфейс,Dequeинтерфейснаследовать Queueинтерфейс
  • AbstractQueueабстрактный классвыполнить Queueинтерфейс
  • BlockingDequeинтерфейс,TransferQueueинтерфейснаследовать BlockingQueueинтерфейс
  • BlockingDequeнаследование интерфейсаDequeинтерфейс
  • LinkedBlockingDequeсвоего родавыполнить BlockingDequeинтерфейс
  • LinkedTransferQueueинтерфейс классавыполнить TransferQueueинтерфейс
  • LinkedListсвоего рода,ArrayDequeсвоего рода,ConcurrentLinkedDequeсвоего родавыполнитьохватыватьDequeинтерфейс
  • ArrayBlockingQueueсвоего рода,LinkendBlockingQueueсвоего рода,LinkedBlockingDequeсвоего рода,LinkedTransferQueueсвоего рода,SynchronousQueueсвоего рода,PriorityBlockQueueсвоего рода,DelayQueue类наследоватьохватыватьAbstractQueueабстрактные классы ивыполнитьИнтерфейс BlockingQueue
  • PriorityQueueкласс иConcurrentLinkedQueueсвоего роданаследоватьохватыватьAbstractQueueабстрактный класс

Уведомление:

  • Deque: Полное название — Double-Ended queue, что означает двустороннюю очередь.
  • Класс реализует интерфейс, используя реализацию
  • Интерфейс наследует интерфейс, использование расширяет
  • Классы наследуют классы, используют расширения

3. Все вещи возвращаются в интерфейс секты Queue

2.1 Глубокое понимание сущности интерфейса Queue

  • Интерфейс Queue — это Коллекция, предназначенная для обработки элементов, которые ранее где-то временно хранились.

  • В дополнение к основным операциям сбора очереди предоставляют дополнительные операции вставки, извлечения и проверки. Каждая операция имеет две формы: в случае сбоя операции выдается исключение; в случае сбоя операции возвращается специальное значение (нулевое или ложное, в зависимости от операции).

  • Очереди обычно представляют собой порядок элементов FIFO (первым пришел, первым обслужен), но это не обязательно.

  • Только приоритетная очередь может сортировать элементы в соответствии с предоставленным компаратором или использовать обычный порядок. Независимо от порядка, заголовок очереди будет удален вызовом методов remove() или poll(). В очереди FIFO все новые элементы вставляются в конец очереди. Другие виды очередей могут использовать другие макеты для хранения элементов.

  • Каждая очередь должна указывать свойство упорядочения.

2.2 Основные методы интерфейса Queue

Всего существует 3 группы методов, и каждая группа методов соответствует двум методам. Как показано ниже:

Queue的核心方法

действие генерировать исключение вернуть специальное значение
Insert add(e) offer(e)
Remove remove() poll
Examine element() peek()

  • (1) Например添加（Insert）Существует два способа воздействия на элемент:add(e)иoffer(e). Если добавление завершается ошибкой при вызове метода add(e),抛异常, и если вызов метода offer(e) завершится ошибкой,返回false. Метод предложения используется, когда исключения являются нормальными, например, в ограниченной очереди, и метод предложения является предпочтительным. Если очередь заполнена и никакие элементы не могут быть добавлены, метод offer возвращает false, поэтому мы знаем, что очередь заполнена, а не исключение, выдаваемое при запуске дескриптора.

  • (2) Аналогично, для действия по удалению элемента, когда очередь пуста, метод удаления выдает исключение, а опрос возвращает значение null. Возвращает удаленный элемент, если удаление элемента в заголовке прошло успешно.

  • (3) Точно так же действие обнаружения (Исследовать) элемента возвращает элемент заголовка (элемент, добавленный в начале), но не удаляет элемент.Если очередь пуста, метод element() выдает исключение, а peek() возвращает false.

  • (4) Интерфейс Queue не определяет методы блокировки очередей, эти методы определяются в интерфейсе BlockQueue.

  • (5) Классы реализации очереди обычно не допускают вставку нулевых элементов.Хотя некоторые классы реализации, такие как LinkedList, не запрещают вставку нулевых элементов, вставлять нулевые элементы не рекомендуется, так как нуль также используется в специальном возврате. значение метода опроса, чтобы указать, что очередь не содержит элементов.

4. Интерфейс Deque доступен на обоих концах

4.1 Глубокое понимание принципа интерфейса Deque

双端队列Deque

(1) Концепция Deque:Линейная коллекция, которая поддерживает вставку и удаление элементов на обоих концах. названиеdequeсокращение от deque, обычно произносится какdeck. Большинство классов, которые реализуют Deque, без фиксированного ограничения на количество содержащихся в них элементов, поддерживают как ограниченные, так и неограниченные.

(2) Описание метода Deque:

Deque方法

**инструкция: **

  • Список содержит методы для доступа к элементам на обоих концах двухсторонней очереди, предоставляя методы для вставки, удаления и проверки элементов.

  • Каждый из этих методов существует в двух формах: в случае сбоя операции выдается исключение, а другой метод возвращает специальное значение (null или false, в зависимости от операции).

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

  • Интерфейс Deque расширяет интерфейс Queue, и при использовании deque в качестве очереди он действует как FIFO. Элементы будут добавлены в конец двухсторонней очереди и удалены с начала.

  • Методы, эквивалентные Queue при использовании в качестве FIFO, показаны в следующей таблице:

Deque等价于Queue的方法

Например, метод add класса Queue эквивалентен методу addLast класса Deque.

  • Deque также можно использовать в качестве стека LIFO (последний вошел, первый вышел), интерфейс, который превосходит традиционный класс Stack. При использовании в качестве стека элементы помещаются в начало очереди очереди, а pop также извлекается из головы очереди.

  • Метод Stack в точности эквивалентен следующему методу Deque:

    Dque等价于Stack的方法

Примечание. Независимо от того, используется ли метод просмотра в качестве стека или очереди, он возвращает первый добавленный элемент из заголовка очереди обнаружения очереди. Например, если вы введете 100 в первый раз и 200 во второй раз, peek вернет 100. Как показано ниже:

示例代码

4.1 Какие классы реализуют интерфейс Deque

  • Класс LinkedList
  • Класс ArrayDeque
  • Класс ConcurrentLinkedDeque
  • Класс LinkedBlockingDeque

4.2 Какие классы наследуют интерфейс Deque

  • Интерфейс BlockingDeque

Пять, скелет очереди Абстрактный класс AbstractQueue

5.1 Глубокое понимание абстрактного класса AbstractQueue

AbstractQueue — это абстрактный класс, который наследует интерфейс Queue и предоставляет некоторые каркасные реализации операций Queue.

AbstractQueue的方法

Методы добавления, удаления и элемента основаны на предложении, опросе и просмотре. То есть, если он не может нормально работать, выбрасывается исключение. Давайте посмотрим, как это делает AbstractQueue.

  • Метод добавления AbstractQueue
public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}
  • Метод удаления AbstractQueue
public E remove() {
    E x = poll();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}
  • Метод элемента AbstractQueue
public E element() {
    E x = peek();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

Уведомление:

  • Если вы наследуете абстрактный класс AbstractQueue, вы должны убедиться, что метод предложения не допускает вставки нулевого значения.

5.2 Какие классы наследуют абстрактный класс AbstractQueue

  • ArrayBlockingQueueсвоего рода,LinkendBlockingQueueсвоего рода,LinkedBlockingDequeсвоего рода,LinkedTransferQueueсвоего рода,SynchronousQueueсвоего рода,PriorityBlockQueueсвоего рода,DelayQueue类наследоватьохватыватьAbstractQueueабстрактный класс
  • PriorityQueueкласс иConcurrentLinkedQueueсвоего роданаследоватьохватыватьAbstractQueueабстрактный класс

Шесть, интерфейс блокирующего буфера BlockingQueue

6.1 Макроскопический вид BlockingQueue (очередь блокировки)

  • BlockQueue заполнена, операция PUT заблокирована

阻塞队列满了的情况

  • BlockQueue пуст, операция Take заблокирована

阻塞队列为空的情况

(1) BlockingQueue (очередь блокировки) также является очередью, поддерживающей методы вставки и удаления блокировки.

(3) Заблокированная вставка: когда очередь заполнена, очередь блокирует поток, который вставляет элементы, до тех пор, пока очередь не будет заполнена.

(4) Удаление блокировки: когда очередь пуста, поток, который получает элемент, будет ждать, пока очередь не станет непустой.

(5) Сценарии приложений: производители и потребители, поток-производитель добавляет элементы в очередь, поток-потребитель удаляет элементы из очереди и контейнер для получения и хранения элементов при блокировании очереди.

(6) Зачем использовать блокирующие очереди: скорость производства производителей и потребителей различна, и для решения проблемы разницы скоростей необходимо использовать очереди.Когда очереди заполнены или пусты, для решения проблемы необходимы блокирующие действия производства или потребления. заполненности очереди или пустых вопросов.

6.2 Анализ случая

Поток A переходит в очередь на блокировку添加элемент, а поток B из очереди блокировки移除элемент.

  • Когда очередь блокировки пуста(совсем нет), операция получения элементов из очереди будет заблокирована.
    • Случай из жизни: Когда я пошел в Хайдилао, чтобы поесть хот-пот, никто не пришел есть хот-пот в 8:00 утра, поэтому мне пришлось ждать, пока придут гости.
    • Преобразование в потоки: теперь нет элементов для добавления, а очередь блокировки пуста, поэтому потоку B не нужно брать элементы из очереди, поэтому операция потока B по получению элементов заблокирована.
  • Когда очередь блокировки заполнена(элементы размещаются во всех позициях), операция добавления элементов из очереди будет заблокирована.
    • Случай из жизни: когда я пошел в Хайдилао, чтобы поесть хот-пот, там было слишком много людей, поэтому мне пришлось стоять в очереди и ждать, пока освободятся другие столы, прежде чем войти.
    • В переводе на потоки: Поток A добавляет элементы в очередь блокировки и заполняет очередь Поток B сейчас занят и не может вынимать элементы из очереди, поэтому в очереди блокировки нет места для размещения элементов В это время поток A добавляет элементы.операция заблокирована

6.3 Ограждение интерфейса BlockingQueue

10 основных методов интерфейса BlockingQueue:

继承的方法

10 основных методов резюмируются следующим образом:

BlockingQueue接口的10个核心方法

Существует три типа операций: вставка, удаление и проверка.

  • Существует четыре способа вставки:добавить, предложить, поставить, предложить тайм-аут версии.
    • Особенностью метода add является создание исключения в случае сбоя добавления. Существует четыре типа исключений:
      • IllegalStateException- очередь заполнена
      • ClassCastException- Тип добавленного элемента не соответствует
      • NullPointerException- добавленный элемент является нулевым
      • IllegalArgumentException- Некоторые атрибуты добавленных элементов не совпадают
    • Особенностью метода offer является то, что он возвращает false только в случае неудачного добавления.
    • Особенностью метода put является то, что когда блокирующая очередь заполнена, если производитель помещает элементы в очередь, очередь будет блокировать поток производителя до тех пор, пока очередь не станет доступной или не выйдет в ответ на прерывание.
    • Особенностью метода тайм-аута предложения является то, что когда очередь блокировки заполнена, если производитель вставляет элемент в очередь, очередь блокирует поток производителя на период времени.Если указанное время превышено, поток производителя выйдет и вернет false.
  • Существует четыре способа удаления:удалить, опросить, взять, опросить версию тайм-аута
    • Особенностью метода удаления является создание исключения в случае сбоя удаления.
      • NoSuchElementException- если эта очередь пуста
    • Особенностью метода опроса является возврат null в случае сбоя удаления.
    • Особенностью метода take является то, что когда блокирующая очередь пуста, если поток-потребитель удаляет элементы из очереди, очередь будет блокировать поток-потребитель до тех пор, пока очередь не станет пустой.
    • Особенностью метода тайм-аута опроса является то, что когда блокирующая очередь пуста, если потребитель удаляет элементы из очереди, очередь всегда будет блокировать поток-потребитель.Если указанное время превышено, поток-потребитель завершится и вернет null
  • Есть два способа проверить:элемент, взгляд
    • Метод элемента используется для обнаружения наличия элемента заголовка, если очередь пуста, он выдает исключение, в противном случае он возвращает элемент заголовка.
    • Метод peek используется для обнаружения наличия элемента заголовка, если очередь пуста, он возвращает специальное значение null, в противном случае он возвращает элемент заголовка.

6.4 Что BlockingQueue блокирует вставку и удаление?

  • При вставке элемента в очередь, если очередь недоступна, блокировка производителя в основном реализуется с помощью LockSupport.park(this).
  • Метод park заблокирует текущий поток и вернется только при выполнении одного из следующих четырех условий.
    • Когда unpark соответствует парковке, выполняется или уже выполнено. «Выполнено» относится к случаю, когда сначала выполняется unpark, а затем выполняется park.
    • когда нить прерывается.
    • Подождите количество миллисекунд, указанное параметром времени.
    • Когда возникает аномалия, причины аномалии нет.

6.5 Какие классы наследуют интерфейс BlockingQueue?

  • Интерфейс BlockingDeque — двойная очередь блокировки
  • Интерфейс TransferQueue - очередь передачи

6.6 Какие классы реализуют интерфейс BlockingQueue?

  • Класс ArrayBlockingQueue — ограниченная очередь блокировки, состоящая из массивов
  • Класс LinkedBlockingQueue - ограниченная очередь блокировки, состоящая из связанного списка. Размер связанного по умолчанию значения Integer.MAX_Value (2^31-1), а значение очень большое, что эквивалентно неограниченному.
  • Класс LinkedBlockingDeque — двунаправленная очередь блокировки, состоящая из связанного списка.
  • Класс LinkedTransferQueue — неограниченная очередь блокировки, состоящая из связанного списка.
  • Класс SynchronousQueue — блокирующая очередь, которая не хранит никаких элементов, только один элемент для передачи данных.
  • Класс LinkedTransferQueue — неограниченная блокирующая очередь TransferQueue, состоящая из связанного списка.
  • Класс DelayQueue — отложенная неограниченная блокирующая очередь, реализованная с использованием приоритетных очередей.

6.6 Какие интерфейсы наследует интерфейс BlockingQueue?

  • Интерфейс BlockingQueue наследует интерфейс Queue и может использоваться как очередь.

7. Двусторонняя блокировка интерфейса BlockingDeque

7.1 Понимание BlockDeque из принципиальной схемы

  • BlockQueue заполнена, и операции Take на обоих концах заблокированы.

BlockingDeque满了

  • BlockQueue пуст, операция Take на обоих концах заблокирована

BlockQueue为空

7.2 Метод интерфейса BlockingDeque

это блокирующая очередьBlockingQueueи двусторонняя очередьDequeКомбинация интерфейсов. Существуют следующие методы:

BlockingDeque接口方法

Пример:

Попробуйте сделать следующее:

LinkedBlockingDeque queue = new LinkedBlockingDeque();
queue.addFirst("test1");
queue.addFirst(300);
queue.addLast("400");

Порядок элементов в конечной очереди следующий:

300, тест1, 400.

Сначала добавьте test1 в начало очереди, затем поместите 300 в начало головы, чтобы 300 оказалось впереди и стало началом, а затем поместите 400 в конец очереди, чтобы конечный результат был 300, test1 , 400 .

队列种的元素

7.3 Эквивалентные методы BlockDeque и BlockQueue

mark

7.4 Возможности BlockingDeque

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

7.5 Какие интерфейсы наследует интерфейс BlockingDeque?

  • Интерфейс очереди, с функцией очереди
  • Интерфейс Deque, с функцией двусторонней очереди
  • Интерфейс BlockingQueue, который можно использовать в качестве очереди блокировки

7.6 Какие классы реализуют интерфейс BlockDeque?

  • LinkedBlockingDeque

Во-вторых, миссия должна достичь интерфейса TransferQueue.

8.1 Как понять Трансфер?

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

8.2 Случаи из жизни

  • **способ передачи для TransferQueue**
    • Курьер Yuantong хочет доставить 2 курьеров Xiaomi к двери, а курьер Yunda также хочет доставить 2 курьеров Xiaomi к двери. Сяо Мин может взять только одну за раз, и курьер должен подождать, пока Сяо Мин возьмет одну, прежде чем продолжать отдавать вторую.
  • Метод tryTransfer для TransferQueue
    • Курьер Yuantong хочет доставить 2 курьеров Xiaomi к двери, а курьер Yunda также хочет доставить 2 курьеров Xiaomi к двери. Обнаружив, что Сяо Мина нет дома, он отправил курьера прямо на станцию ​​Цайняо.
  • Метод тайм-аута tryTransfer для TransferQueue
    • Курьер Yuantong хочет доставить 2 курьеров Xiaomi к двери, а курьер Yunda также хочет доставить 2 курьеров Xiaomi к двери. Я обнаружил, что Сяо Мина нет дома, поэтому я подождал 5 минут и обнаружил, что Сяо Мин не вернулся, поэтому я отправил курьера прямо на станцию ​​​​новичков.

8.3 Принципиальный анализ TransferQueue

  • transfer(E e)

    Принцип показан на следующем рисунке:

    transfer方法的原理

    • Схематическое объяснение: Поток-производитель Producer Thread пытается передать элемент B потоку-потребителю и, если потока-потребителя нет, помещает элемент B в хвостовой узел. И поток-производитель ожидает, пока элемент B будет использован. Когда элемент B потребляется, поток производителя возвращается.
    • Если в настоящее время потребитель ожидает получения элемента (когда потребитель передает метод take или метод опроса с ограничением времени ожидания), метод передачи может немедленно передать элемент, переданный производителем, потребителю.
    • Если нет потребителей, ожидающих получения элемента, метод передачи помещает элемент в хвостовой узел очереди и ждет, пока элемент не будет использован потребителем, прежде чем вернуться.

  • tryTransfer(E e)

    • Проверьте, может ли элемент, переданный производителем, быть передан непосредственно потребителю.
    • Возвращает false, если ни один потребитель не ожидает получения элемента.
    • Отличие от метода передачи в том, что метод возвращает значение немедленно, независимо от того, получил его потребитель или нет.

  • tryTransfer(E e, long timeout, TimeUnit unit)

    • Метод tryTransfer с ограничением по времени.
    • Попытки передать элемент, переданный производителем, непосредственно потребителю.
    • Если ни один потребитель не использует элемент, подождите указанное время перед возвратом.
    • Возвращает false, если элемент не был использован после тайм-аута.
    • Возвращает true, если элемент был использован в течение периода ожидания.

  • getWaitingConsumerCount()

    • Получите количество потребителей, ожидающих приема элементов, с помощью метода BlockingQueue.take() или метода опроса ограничения времени ожидания. приближение.
    • Возвращает количество потребителей, ожидающих получения элементов.

  • hasWaitingConsumer()

    • Получает информацию о том, есть ли потребители, ожидающие приема элементов с помощью метода BlockingQueue.tabke() или метода опроса ограничения времени ожидания.
    • Возврат true указывает, что есть по крайней мере один ожидающий потребитель.

8.3 Какие интерфейсы наследует интерфейс TransferQueue?

  • Интерфейс BlockingQueue, который можно использовать в качестве очереди блокировки
  • Интерфейс очереди, который можно использовать как очередь

8.4 Какие классы реализуют интерфейс TransferQueue?

  • Интерфейс LinkedTranferQueue

Девять, приоритет — ваш класс PriorityQueue.

9.1 Понимание класса PriorityQueue

  • Должны быть отсортированы в порядке возрастания

本应该按照升序排序

  • Сортировать по воспоминаниям

按照自定义优先级排序

  • PriorityQueue — неограниченная блокирующая очередь, поддерживающая приоритет.

  • Естественный порядок по умолчанию — восходящий.

  • Элементы можно сортировать, создав параметр Comparator.

public PriorityQueue(Comparator<? super E> comparator) {
     this(DEFAULT_INITIAL_CAPACITY, comparator);
}
  • Настраиваемая реализация метода comapreTo() для указания правил упорядочения элементов.
public Comparator<? super E> comparator() {
    return comparator;
}
  • Вставка пустых элементов не допускается.
  • Не гарантируется, что классы, реализующие интерфейс PriorityQueue, будут потокобезопасными, если только они не являются PriorityBlockingQueue.
  • Итераторы PriorityQueue не гарантируют обход элементов в каком-либо конкретном порядке, если требуется упорядоченный обход, рассмотрите возможность использованияArrays.sort(pq.toArray).
  • в колонку(offer,add) и убрать из очереди (poll,remove()) имеет временную сложность O (log (n)).
  • Временная сложность алгоритма удаления (объекта) и содержания (объекта) составляет O (n).
  • Временная сложность алгоритма просмотра, элемента и размера составляет O (1).

9.2 Какие классы наследует класс PriorityQueue?

  • Абстрактный класс AbstractQueue с функцией очереди

9.2 Какие интерфейсы реализует класс PriorityQueue?

  • Интерфейс очереди, который можно использовать как очередь.

Десять двусвязных списков Класс LinkedList

10.1 Структура LinkedList

  • LinkedList реализует интерфейсы List и Deque, поэтому представляет собой структуру списка с двойной связью, которую можно использовать как стек, очередь и двустороннюю очередь.
  • Каждый элемент двустороннего списка имеет три целочисленных значения: элемент, обратная узловая ссылка, прямая узловая ссылка.

LinkedList的结构

Давайте взглянем на класс узла Node.

private static class Node<E> {
    E item; //元素
    Node<E> next; //向后的节点链接
    Node<E> prev; //向前的节点链接

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

10.2 Отличия от ArrayList

  • 1. Эффективность добавления и удаления LinkedList относительно высока, а эффективность поиска и модификации относительно низка.

  • 2. Рекомендуется использовать ArrayList в следующих ситуациях

    • Частый доступ к элементу в списке.
    • Добавляйте элементы только в начало и конец списка.

  • 3. Рекомендуется использовать LinkedList в следующих ситуациях

    • Частое добавление и удаление элементов из начала, середины и конца списка.
    • Доступ к элементам в списке должен осуществляться через итерацию цикла.

10.3 LinkedList не является потокобезопасным

LinkedList не является потокобезопасным, поэтому вы можете использовать следующие методы для обеспечения потокобезопасности.

List list = Collections.synchronizedList(new LinkedList<>());

10.4 Семейное членство в LinkedList

  • LinkedList расширяет класс AbstractSequentialList.

  • LinkedList реализует интерфейс Queue и может использоваться как очередь.

  • LinkedList наследует абстрактный класс AbstractQueue и имеет функцию очереди.

  • LinkedList реализует интерфейс списка и может выполнять операции, связанные со списком.

  • LinkedList реализует интерфейс Deque и может использоваться как двусторонняя очередь.

  • LinkedList реализует интерфейс Cloneable, который позволяет клонировать.

  • LinkedList реализует интерфейс java.io.Serializable, который поддерживает сериализацию и может быть передан через сериализацию.

Одиннадцать, класс параллельной безопасности ConcurrentLinkedQueue

11.1 Понимание ConcurrentLinkedQueue

ConcurrentLinkedQueue原理

  • ConcurrentLinked — это потокобезопасная неограниченная очередь FIFO, состоящая из структуры связанного списка.
  • Когда несколько потоков хотят совместно использовать доступ к коллекции, ConcurrentLinkedQueue — лучший выбор.
  • Вставка нулевых элементов не допускается
  • Поддерживает неблокирующий доступ к одновременно безопасным очередям без создания исключения ConcurrentModifationException.
  • Метод size не является точным, поскольку очередь может добавлять элементы при подсчете коллекции, что приводит к неточным статистическим данным.
  • Массовые операции addAll, removeAll, keepAll, containsAll, equals и toArray не гарантируют атомарности (операции неделимы).
  • Добавление элементов происходит до того, как другие потоки удалят элементы.
  • Использование заключается в следующем:
ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();
BuildingBlockWithName buildingBlock = new BuildingBlockWithName("三角形", "A");
concurrentLinkedQueue.add(buildingBlock);

11.2 Какие классы наследует класс ConcurrentLinkedQueue?

  • Абстрактный класс AbstractQueue с функцией очереди

11.3 Какие интерфейсы реализует класс ConcurrentLinkedQueue?

  • Интерфейс очереди, который можно использовать как очередь

Двенадцать двунаправленных массивов класса ArrayDeque

ArrayDeque原理图

12.1 Понимание ArrayDeque

  • Дека, состоящая из массивов.
  • Нет ограничений по емкости, расширяйте по мере необходимости.
  • Не потокобезопасный.
  • Вставка нулевых элементов запрещена.
  • При использовании в качестве стека он работает быстрее, чем стек, а при использовании в качестве очереди — быстрее, чем LinkList.
  • Временная сложность алгоритма большинства методов составляет O(1).
  • Алгоритмическая временная сложность O(n) для удаления, удаленияFirstOccurrence, removeLastOccurrence, содержит, удаляет и массовые операции

12.2 Как использовать

Создайте ArrayDeque и добавьте элементы в конец arrayDeque.

ArrayDeque arrayDeque = new ArrayDeque();
for (int i = 0; i < 50; i++) {
    arrayDeque.add(buildingBlock); // add方法等价于addLast方法
}

12.3 Какие интерфейсы реализует ArrayDeque

  • Интерфейс Deque - может использоваться для деков

Тринадцать двусторонних параллельных классов ConcurrentLinkedDeque

13.1 Понимание класса ConcurrentLinkedDeque

ConcurrentLinkedDeque原理图

  • Двунаправленная неограниченная очередь блокировки, состоящая из структуры связанного списка.
  • Операции вставки, удаления и доступа могут выполняться одновременно, потокобезопасные классы
  • Вставка нулевых элементов не допускается
  • В параллельном сценарии вычисление размера очереди будет неточным, так как элементы могут быть добавлены в очередь во время вычисления.
  • Массовые операции addAll, removeAll, keepAll, containsAll, equals и toArray не гарантируют атомарности (операции неделимы).

13.2 Пример использования ConcurrentLinkedDeque

Создадим два блока: треугольник, четырехугольник и добавим в очередь:

BuildingBlockWithName buildingBlock1 = new BuildingBlockWithName("三角形", "A");
BuildingBlockWithName buildingBlock2 = new BuildingBlockWithName("四边形", "B");
ConcurrentLinkedDeque concurrentLinkedDeque = new ConcurrentLinkedDeque();
concurrentLinkedDeque.addFirst(buildingBlock1);
concurrentLinkedDeque.addLast(buildingBlock2);
//结果：顺序：三角形、四边形

13.3 Какие интерфейсы реализует ConcurrentLinkedDeque

  • Интерфейс Deque - может использоваться для деков

14. Блокировка массива Класс ArrayBlockingQueue

14.1 Понимание ArrayBlockingQueue

ArrayBlockingQueuey原理图

  • ArrayBlockingQueue — это ограниченная блокирующая очередь, реализованная с помощью массивов.
  • Операции вставки блокируются, когда очередь работает медленно, а операции удаления блокируются, когда очередь пуста.
  • Элементы сортируются по принципу «первым пришел – первым обслужен» (FIFO).
  • По умолчанию потоки не имеют гарантированного доступа к очереди.
  • Справедливый доступ к очереди: доступ к очереди в порядке блокировки, то есть поток, который блокируется первым, получает доступ к очереди первым.
  • Несправедливость несправедлива по отношению к потоку, который ожидает первым.Когда очередь доступна, все заблокированные потоки могут конкурировать за квалификацию для доступа к очереди. Возможно, что заблокированный поток получит доступ к очереди доступа последним.
  • Справедливость снижает пропускную способность.

14.2 Пример использования ArrayBlockingQueue

Создадим два блока: треугольник, четырехугольник и добавим в очередь:

BuildingBlockWithName buildingBlock1 = new BuildingBlockWithName("三角形", "A");
BuildingBlockWithName buildingBlock2 = new BuildingBlockWithName("四边形", "B");
ArrayBlockingQueue arrayBlockingQueue = new ArrayBlockingQueue(100, true);
arrayBlockingQueue.add(buildingBlock1);
arrayBlockingQueue.add(buildingBlock2);

14.3 Какие интерфейсы реализует ArrayBlockQueue

  • Интерфейс Deque - может использоваться для деков

Пятнадцать, связанный список, блокирующий класс LinkedBlockingQueue

15.1 Понимание LinkedBlockingQueue

LinkedBlockingQueue原理

  • LinkedBlockingQueue имеет функции односвязного списка и ограниченной очереди блокировки.
  • Операции вставки блокируются, когда очередь работает медленно, а операции удаления блокируются, когда очередь пуста.
  • Максимальная длина по умолчанию — Integer.MAX_VALUE, что эквивалентно неограниченному (очень большое значение: 2^31-1).

15.2 Пример использования LinkedBlockingQueue

LinkedList linkedList1 = new LinkedList();
linkedList1.add("A");
linkedList1.add("B");
linkedList1.add("C");

15.3 Сценарии применения LinkedBlockingQueue

  • Пропускная способность обычно выше, чем у ArrayBlockingQueue. При создании пула потоков параметр runnableTaskQueue (очередь задач), блокирующая очередь, используемая для сохранения задач, ожидающих выполнения, может выбирать LinkedBlockingQueue. Статический фабричный метод Executors.newFixedThreadPool() использует эту очередь.

15.4 Какие интерфейсы реализует LinkedBlockingQueue

  • LinkedBlockingQueue наследует класс BlockingQueue и может использоваться в качестве очереди блокировки.
  • LinkedBlockingQueue наследует абстрактный класс AbstractQueue и имеет функцию очереди.
  • LinkedBlockingQueue реализует интерфейс java.io.Serializable, который поддерживает сериализацию и может передаваться через сериализацию.

Шестнадцать, двусторонняя блокировка класса LinkedBlockingDeque

16.1 Понимание класса LinkedBlockingDeque

LinkedBlockingDeque原理图

  • По цепочке LinkedBlockingDeque = очередь блокировки + связанный список + двусторонний доступ
  • потокобезопасный.
  • Когда к очереди одновременно присоединяются несколько потоков, конкуренция снижается вдвое, поскольку к записи обращается еще один конец.
  • Размер емкости по умолчанию — Integer.MAX_VALUE. Размер емкости может быть указан.

16.2 Сценарии применения LinkedBlockingDeque

LinkedBlockingDeque можно использовать в режиме «кражи работы».

工作窃取算法: поток простаивает и крадет задачи из конца рабочей очереди других потоков, чтобы помочь ему выполниться.

16.3 Какие интерфейсы реализует LinkedBlockingDeque

  • LinkedBlockingDeque наследует класс BlockingDeque и может использоваться в качестве очереди блокировки.
  • LinkedBlockingDeque наследует абстрактный класс AbstractQueue и имеет функцию очереди.
  • LinkedBlockingDeque реализует интерфейс java.io.Serializable, который поддерживает сериализацию и может быть передан через сериализацию.

Семнадцать, связанный список, блокирующий класс LinkedTransferQueue

17.1 Понимание класса LinkedTransferQueue

LinkedTransferQueue原理图

LinkedTransferQueue = очередь блокировки + структура связанного списка + TransferQueue

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

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

17.2 Интерфейс LinkedTransferQueue имеет на 5 методов больше, чем другие блокирующие очереди

  • transfer(E e)
  • tryTransfer(E e)
  • tryTransfer(E e, long timeout, TimeUnit unit)
  • getWaitingConsumerCount()
  • hasWaitingConsumer()

17.3 Пример кода LinkedTransferQueue

  • Создайте LinkedTransferQueue, и производитель 1 по очереди добавит в очередь A, B и C.

生产者1 依次往队列中添加 A、B、C

  • Производитель 2 добавляет в очередь D, E и F по очереди.

生产者2 依次往队列中添加 D、E、F

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

消费者消费元素

  • результат операции
生产者1     transfer A 
生产者2     transfer D 

2s后...
  
消费者      take A
生产者1     put B 
 
2s后...
     
消费者      take D
生产者2     transfer E 
    
2s后...
  
消费者      take B
生产者1     transfer C
  • Анализ результатов выполнения кода

(1) Сначала потоки-производители 1 и 2 вызывают метод передачи для передачи A и D и обнаруживают, что ни один поток-потребитель не получает их, поэтому они блокируются.

(2) Поток-потребитель забирает A через 2 с, а затем производитель 1 освобождается для продолжения выполнения, передает элемент B и обнаруживает, что потребления потребителем нет, поэтому он ждет.

(3) После того, как поток-потребитель пройдет 2 с, он заберет элемент D из головы очереди, а производитель 2 продолжит выполнение вниз, передаст элемент E и обнаружит, что потребителя нет, поэтому он ждет.

(4) Через 2 с поток-потребитель забирает элемент B из головы очереди, а производитель 1 передает элемент C и ждет, пока его заберет потребитель.

(5) Потребитель больше не потребляет, поэтому и производитель 1, и производитель 2 заблокированы, элемент C и элемент E не забираются, а элемент F производителя 2 не начал передачу, потому что он ожидает. увезли.

(6) Убедитесь, что в очереди действительно есть элементы C и E, а E находится в начале очереди.

队列里面的元素

17.4 Какие интерфейсы реализует LinkedTransferQueue

  • LinkedBlockingDeque наследует класс BlockingQeque и может использоваться в качестве очереди блокировки.
  • LinkedBlockingDeque наследует абстрактный класс AbstractQueue и имеет функцию очереди.

Восемнадцать, прохожий класса SynchronousQueue

18.1 Понимание класса SynchronousQueue

SynchronousQueue原理图

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

  • SynchronousQueue отвечает за передачу данных, сгенерированных производителем, в поток-потребитель.

  • Сам SynchronousQueue не хранит данные, после вызова метода put очередь тоже пустая.

  • Каждая операция размещения должна дождаться завершения операции взятия, иначе элемент не может быть добавлен.

  • Подходит для переходных сценариев.

  • Производительность выше, чем у ArrayBlockingQueue и LinkedBlockingQueue.

18.2 Пример синхронной очереди

Мы создали два потока, один поток для производства и один поток для потребления.

  • Поток производства по очереди ставит три значения A, B и C

生产的线程依次put A、B、C三个值

  • Поток-потребитель использует take для потребления содержимого в очереди блокировки, ожидая 5 секунд перед каждым потреблением.

消费线程每隔5s调用take方法

  • результат операции
t1     put A 
t2     take A 

5秒后...

t1     put B 
t2     take B 

5秒后...

t1     put C 
t2     take C

Резюме: после того, как производственный поток выполнит операцию размещения первого элемента «А», ему нужно дождаться, пока потребительский поток завершит получение «А», прежде чем продолжить выполнение кода.

18.3 Сценарий приложения SynchronousQueue

  • Пропускная способность обычно выше, чем у LinkedBlockingQueue. При создании пула потоков параметр runnableTaskQueue (очередь задач), блокирующая очередь, используемая для сохранения задач, ожидающих выполнения, может выбирать SynchronousQueue. Статический фабричный метод Executors.newCachedThreadPool() использует эту очередь

18.4 Разница между SynchronousQueue и LinkedTransferQueue

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

Девятнадцать, приоритетная блокировка класса PriorityBlockingQueue

19.1 Понимание класса PriorityBlockQueue

PriorityBlockQueue的原理图

  • PriorityBlockQueue = PriorityQueue + BlockingQueue
  • Ранее мы также говорили о принципе PriorityQueue, который поддерживает сортировку элементов.
  • По умолчанию элементы сортируются естественным образом.
  • Метод CompareTo() можно настроить для указания правил упорядочения элементов.
  • Элементы можно сортировать через параметр конструктора Comparator.

19.2 Какие интерфейсы реализует PriorityBlockQueue

  • LinkedBlockingQueue наследует интерфейс BlockingQueue и может использоваться в качестве очереди блокировки.
  • LinkedBlockingQueue наследует абстрактный класс AbstractQueue и имеет функцию очереди.
  • LinkedBlockingQueue реализует интерфейс java.io.Serializable, который поддерживает сериализацию и может передаваться через сериализацию.

Двадцать, блокировка задержки класса DelayQueue

20.1 Понимание DelayQueue

DelayQueue原理图

  • DelayQueue = Delayed + BlockingQueue. Элементы в очереди должны реализовывать интерфейс Delayed.
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {
  • При создании элемента вы можете указать, сколько времени потребуется для получения текущего элемента из очереди. Текущий элемент может быть извлечен из очереди только после истечения задержки.

20.2 Анализ исходного кода

  • При добавлении элементов укажите время задержки перед получением элементов из очереди
public boolean offer(E e, long timeout, TimeUnit unit) {
    return offer(e);
}
  • Метод poll для получения элементов должен дождаться времени задержки перед получением элементов.
if (first == null || first.getDelay(NANOSECONDS) > 0)
    return null;
else
    return q.poll();

poll方法

20.3 Сценарии применения

  • Дизайн системы кэширования: DelayQueue можно использовать для сохранения срока действия кэшированных элементов. Затем используйте поток для циклического запроса очереди DelayQueue.Как только элемент может быть получен из DelayQueue, это означает, что срок действия кеша истек.

  • Планирование запланированных задач: используйте очередь DelayQueue, чтобы сохранить задачи и время выполнения, которые будут выполняться в этот день, и начните выполнение, как только задача будет получена из DelayQueue. Например, TimerQueue в Java реализован с использованием DelayQueue.

20.4 Какие интерфейсы реализует DelayQueue

  • DelayQueue реализует интерфейс BlockingQueue и может использоваться как блокирующая очередь.

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

mark

❝

Привет, я悟空哥,"7 лет опыта разработки проектов, fullstack-инженер, руководитель группы разработчиков, очень любит базовые принципы графического программирования". Я пишу два PDF-файла, а именно: 1. Практический проект Spring Cloud (лучше всего должен пройти), 2. Параллелизм Java должен быть известен и должен быть известен. я по-прежнему手写了2个小程序, апплет вопроса о кисти Java, апплет вопроса о кисти PMP, нажмите на мое официальное меню учетной записи, чтобы открыть! Кроме того, есть 111 архитектурных материалов и 1000 вопросов для собеседования по Java, все они организованы в формате PDF, вы можете обратить внимание на общедоступный аккаунт.«Архитектура чата Гоку»Ответить悟空Получите качественную информацию.

❞

二维码

«Ретвит -> Просмотр -> Нравится -> Избранное -> Комментарий!!!»Это моя самая большая поддержка!

Серия "Параллелизм в Java должен знать, должен знать":

1. Встречный интервьюер | 14 схем | Никогда не бойся, что тебя спросят изменчиво!

2. Программист был презираем женой поздно ночью, потому что принцип CAS был слишком простым?

3. Используйте стандартные блоки, чтобы объяснить принцип ABA | Жена снова его понимает!

4. Самый тонкий во всей сети | 21 картинка показывает вам ненадежность коллекции

5.5000 слов | 24 изображения помогут вам лучше понять 21 вид блокировок в Java

Категории