Множества и очереди

Типы данных и исключения в Java

Jim White

Java Developer

Интерфейс Set

  • Set — тоже разновидность Collection
    • Не допускает дублирующихся объектов
      • Гарантирует уникальность каждого элемента
    • Объекты Set в целом неупорядочены (и поэтому не имеют индекса)
  • List — как органайзер для таблеток: каждый объект занимает своё место в ячейке
  • Set — как мешок с объектами: содержимое хранится в произвольном порядке

List — как органайзер для таблеток: объекты хранятся по индексу в определённом месте

Set — как мешок: объекты хранятся произвольно и без порядка

1 Изображения предоставлены Wikimedia Commons
Типы данных и исключения в Java

List и Set: сравнение

  • Когда использовать Set
    • Гарантирует уникальность элементов
    • Ускоряет поиск
      • Проверка наличия объекта в Set
    • Экономичнее по памяти при росте коллекции
    • Удобен для проверки членства в кэшах
      • Пример: поиск уникальных слов в документе
Типы данных и исключения в Java

List и Set: сравнение

  • Когда использовать List
    • Сохраняет порядок элементов и допускает дубликаты
    • Эффективнее при доступе к элементам по позиции
    • Эффективнее при добавлении/удалении элементов по индексу
    • Подходит там, где важен порядок элементов
      • Например: шаги последовательности или треки в плейлисте
Типы данных и исключения в Java

Реализации Set

  • Существует множество реализаций Set
    • HashSet — одна из наиболее популярных
  • HashSet
    • Неупорядоченный набор объектов
    • Быстрее других реализаций Set при вставке, удалении и поиске
    • Как правило, потребляет больше памяти, чем другие реализации Set
    • Допускает хранение одного значения null

HashSet — неупорядоченный набор объектов, допускающий одно значение null

Типы данных и исключения в Java

Создание HashSet

  • Для создания HashSet используйте обобщённый параметризованный конструктор
    HashSet<String> set = new HashSet<String>();
  • HashSet находится в пакете java.util
    • Требует импорта
    • import java.util.HashSet
Типы данных и исключения в Java

Методы HashSet

  • Используйте .add() и .remove() для добавления и удаления объектов
  • Для замены объекта вызовите .remove(), затем .add()
  • Используйте .contains() для проверки существования объекта
  • Дубликаты игнорируются
  • Допускает null
  • Порядок элементов не гарантируется
set.add("France");
set.add("Japan");
set.add("Brazil");
set.add("Egypt");
set.add(null); // null is allowed
set.remove("Brazil");

boolean z =
  set.contains("France"); // z is true
set.add("Japan"); // Ignored
System.out.println(set);

[null, Japan, Egypt, France]
Типы данных и исключения в Java

Интерфейс Queue

  • Структура данных Queue обрабатывает объекты в порядке FIFO («первым пришёл — первым ушёл»)
    • Первый добавленный объект удаляется первым
    • Как очередь у кассы
    • Имеет головной и хвостовой элемент

Схема очереди с обозначенными головой (началом) и хвостом (концом)

  • Существует несколько реализаций Queue
    • Схожи по поведению и операциям
Типы данных и исключения в Java

ArrayBlockingQueue

  • Популярная реализация Queue
    • Под капотом — массив
  • Внимание: ArrayBlockingQueue находится в пакете java.util.concurrent
    • Не в пакете java.util
Типы данных и исключения в Java

Создание ArrayBlockingQueue

  • Для создания ArrayBlockingQueue используйте обобщённый параметризованный конструктор
    • Конструктор принимает ёмкость — максимальное количество объектов
import java.util.concurrent;  // At the top of the class

// Create new queue that can store 4 Strings
ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<String>(4);
Типы данных и исключения в Java

Методы ArrayBlockingQueue

  • Используйте .add(object) или .offer(object) для добавления в хвост
    • .add(object) генерирует исключение, если Queue заполнена
    • .offer(object) игнорирует новый объект при заполненной очереди
ArrayBlockingQueue<String> queue 
    = new ArrayBlockingQueue<String>(4);
queue.offer("France");
queue.offer("Japan");
queue.offer("Brazil");
queue.offer("Egypt");
queue.offer("China"); // Ignores China

// Causes IllegalStateException
// queue.add("China");

System.out.println(queue);

[France, Japan, Brazil, Egypt]
Типы данных и исключения в Java

Методы ArrayBlockingQueue

  • Используйте .remove() или .poll() для удаления из головы
    • .remove() генерирует исключение, если Queue пуста
    • .poll() возвращает null, если Queue пуста
  • Не допускает null
ArrayBlockingQueue<String> queue 
    = new ArrayBlockingQueue<String>(4);
String x = queue.poll(); // x is null
// Causes NoSuchElementException
// String y = queue.remove();

queue.offer("France");
String next = queue.poll();
System.out.println(next);

France
Типы данных и исключения в Java

Давайте потренируемся!

Типы данных и исключения в Java

Preparing Video For Download...