GrabDuck

Java 8 коллекции — urvanov.ru

:

Цикл статей «Учебник Java 8».

Следующая статья — «Java 8 дата и время».
Предыдущая статья — «Java 8 регулярные выражения».

Содержание

Интерфейсы и реализации коллекций

java.util.Collection

java.util.Set

java.util.List

java.util.Queue

java.util.Deque

java.util.Map

Сортировка объектов

java.util.SortedSet

java.util.SortedMap

Другие реализации интерфейсов коллекций

Stream

Стандартные алгоритмы

Интерфейсы и реализации коллекций

Все коллекции в Java реализуют какой-нибудь основной интерфейс.

Списки реализуют интерфейс java.util.List, множества реализуют интерфейс java.util.Set или java.util.SortedSet и так далее.

Ниже приведена иерархия основных интерфейсов коллекций.
Java коллекции

java.util.Collection

Интерфейс java.util.Collection содержит наиболее общие свойства всех коллекций. Он используется в качестве параметра в тех методах, где нужно принимать любой тип коллекций. Например, по соглашению все коллекции имеют конструктор, который принимает интерфейс Collection в качестве параметра. Такой конструктор инициализирует новую коллекцию всеми элементами из указанной коллекции, то есть позволяет вам конвертировать один тип коллекций в другой.

Предположим, что у вас есть Collection<String> c, который может быть List, Set или другим типом Collection. Следующий код создаёт новый экземпляр ArrayList (реализацию интерфейса List), который содержит все элементы из c:

Интерфейс java.util.Collection содержит методы для осуществления базовых операций:

 

Возвращает количество элементов в коллекции.

 

 

Возвращает true, если в коллекции нет ни одного элемента.

 

Возвращает true, если коллекция содержит элемент element.

 

Добавляет элемент в коллекцию. Возвращает true, если элемент был добавлен. Возвращает false, если коллекция не может содержать дублирующихся элементов, и такой элемент уже в ней есть.

 

Удаляет одно вхождение element из коллекции. Возвращает true, если элемент был удалён, false — коллекция не была изменена.

 

Возвращает итератор, позволяющий пройтись по элементам коллекции и удалить некоторые элементы. Iterator представляет собой вот такой интерфейс:

Метод hasNext() возвращает true , если остались ещё элементы. Метод next() возвращает следующий элемент. Метод remove() позволяет удалить последний возвращённый методом next() элемент. Внимание! Во время использования итератора нельзя изменять коллекцию любым другим способом, кроме метода remove() этого итератора, иначе возникнет исключение.

 

Также есть методы, которые оперируют целыми коллекциями:

 

Возвращает true, если коллекция содержит все элементы из c.

 

Добавляет все элементы из c в коллекцию.

 

Удаляет из коллекции все элементы, которые присутствуют в c.

 

 

Оставляет в коллекции только те элементы, которые также присутствуют в коллекции c , удаляя все остальные.

 

Удаляет все элементы из коллекции.

 

Есть также методы, позволяющие преобразовать коллекцию в массив:

Рекомендуется использовать второй метод, так как он позволяет преобразовать в массив определённого типа. Пример: String[] array = collection.toArray(new String[0]);.

 

Начиная с JDK 8 интерфейс Collection также поставляет методы

которые используются для получения последовательных потоков и параллельных потоков из коллекции. Более подробно потоки будут рассмотрены в пункте «Stream».

 

Для прохода по элементам коллекции можно использовать for-each :

 

java.util.Set

java.util.Set — это коллекция, которая не может содержать дублирующихся элементов. Интерфейс Set содержит только методы, унаследованные от java.util.Collection, и добавляет ограничение, что элементы не дублируются. Set накладывает более строгие соглашения на методы equals и hashCode, что позволяет сравнивать экземпляры Set, даже если они различных реализаций. Два экземпляра Set равны, если у них одинаковое количество элементов, и они содержат одинаковые элементы.

Платформа Java предоставляет три реализации интерфейса java.util.Set общего назначения:

  • java.util.HashSet
  • java.util.TreeSet
  • java.util.LinkedHashSet

HashSet— реализация на основе хеш-таблицы. Это наиболее эффективная реализация, но она не гарантирует сохранение порядка элементов при обходе.

TreeSet— реализация на основе красно-чёрных деревьев. Она упорядочивает элементы в соответствии с их значениями, но работает значительно медленнее HashSet.

LinkedHashSet — реализация на основе хеш-таблицы, но дополнительно пролинкованная связанным списком. Эта реализация избавляет от хаотичного порядка элементов и лишь незначительно хуже по эффективности HashSet-а.

Есть ещё две реализации java.util.Set специального назначения: java.util.EnumSet и java.util.concurrent.CopyOnWriteArraySet. Реализация java.util.EnumSet предназначена специально для перечислений, всегда используйте её, когда нужно создать Set, содержащий значения одного и того же перечисления. EnumSet внутренне представляет собой битовый вектор, он очень компактный и быстрый. Реализация CopyOnWriteArraySet хранит свои элементы в массиве и создаёт новый массив при выполнении любой операции добавления, удаления или замены элемента. Она потокобезопасна, при изменении CopyOnWriteArraySet все созданные до этого итераторы остаются в рабочем состоянии. CopyOnWriteArraySet подходит для множеств, которые редко меняются, но по которым часто проходит операция итерации.

С помощью Set можно удалить из любой коллекции дублирующиеся элементы. Например, мы хотим удалить дублирующиеся элементы из коллекции c:

 

java.util.List

Интерфейс java.util.List представляет собой упорядоченную коллекцию. List может содержать дублирующиеся элементы.

В дополнение к методам java.util.Collection интерфейс java.util.List содержит методы для:

  • Доступ/удаление/добавление элементов по позиции.
  • Поиск элемента
  • Расширенный итератор, позволяющий возвращаться к предыдущему элементу и вставлять новые элементы.
  • Метод subList позволяет выполнять операции над частью списка.

Java содержит два класса, реализующих интерфейс List: java.util.ArrayList и java.util.LinkedList.

Есть реализация специального назначения java.util.concurrent.CopyOnWriteArrayList. Она работает аналогично CopyOnWriteArraySet, то есть для каждой операции добавления, замены или удаления элемента создаётся новый массив, хранящий элементы списка. Итерация по CopyOnWriteArrayList никогда не приводит к java.util.ConcurrentModificationException. Есть ещё синхронизированная реализация java.util.Vector.

Методы интерфейса java.util.Collection работают так, как от них ожидается. Метод remove для списка всегда удаляет первое вхождение элемента, а методы add и addAll добавляют элементы в конец.

Так же как и интерфейс Set, интерфейс List предполагает более строгую реализацию equals и hashCode, так что два списка могут сравниваться, даже если они имеют разные реализации. Два списка равны, если они содержат одинаковые элементы в одинаковом порядке.

Ниже описаны операции, работающие с позициями элементов. Все операции, которые принимают индекс элемента в качестве параметра, бросают исключение java.lang.IndexOutOfBoundsException, если индекс выходит за границы списка.

 

Возвращает элемент по индексу.

 

Заменяет элемент по указанному индексу. Возвращает старый элемент.

 

Вставляет элемент в позицию по указанному индексу.

 

Удаляет элемент по указанному индексу.

 

Вставляет все элементы из коллекции c в позицию по указанному индексу.

 

Возвращает индекс элемента o, либо -1, если нет элемента с таким индексом.

 

В List также присутствует метод получения итератора для списков:

Этот итератор наследуется от обычного итератора, но также имеет метод previous(), позволяющий вернуться к предыдущему элементу, и метод hasPrevious(), позволяющий проверить наличие предыдущего элемента для текущей позиции итерации. Вызовы next() и previous() можно чередовать, но нужно быть осторожным, так как первый вызов previous() после череды вызовов next() вернёт то же значение, что и последний вызов next(), а первый вызов next() после череды previous() вернёт то же значение, что и последний вызов previous(). Методы previousIndex() и nextIndex() используются для получения индекса элементы, который будет возвращён следующим вызовом previous() и next() соответственно. Если мы находимся в самом начале списка, то есть следующий вызов next() вернёт первый элемент, то вызов previousIndex() вернёт -1. Если же мы находимся в конце списка, то есть hasNext() возвращает false, то nextIndex() вернёт значение list.size(). Он также имеет дополнительные методы set и add , которые позволяют заменить последний возвращённый элемент и добавить новый элемент соответственно.

 

Метод subList:

Возвращает часть списка между fromIndex (включая) и toIndex (исключая). Изменения в возвращаемом списке отражаются в исходном списке. Например, с помощью кода list.subList(from, to).clear(); можно удалить элементы из исходного списка. Поведение возвращённого списка становится непредсказуемым, если элементы в этом диапазоне будут удалены или добавлены в исходный список, все изменения нужно делать через возвращённый список, будьте внимательны.

java.util.Queue

Интерфейс java.util.Queue представляет собой очередь.

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

Основные реализации: java.util.LinkedList, java.util.PriorityQueue.

Пакет java.util.concurrent содержит интерфейс java.util.concurrent.BlockingQueue, который расширяет интерфейс Queue и добавляет методы, ожидающие появление элемента при получении элемента, и методы, ожидающие появления свободного места при добавлении элемента.

Классы, реализующие BlockingQueue:

Структура интерфейса Queue
Вид операции Бросает исключение Возвращает специальное значение
Добавление элемента add(e) offer(e)
Удаление элемента remove() poll()
Проверка элемента element() peek()

По названию, как видно, определить тип метода невозможно. Можно либо запомнить, либо добавить эту страницу в закладки и всё время сверяться с ней.

Методы add и offer добавляют элементы в хвост очереди.

Методы remove() и poll() удаляют головной элемент из очереди и возвращают удалённый элемент.

Методы element() и peek() возвращают головной элемент, но не удаляют его.

Queue обычно реализует FIFO (first-in-first-out), но это не обязательно. Некоторые реализации могут использовать очередь на основе приоритетов и и другие. Некоторые реализации ограничивают количество элементов в очереди, тогда add бросает исключение java.lang.IllegalStateException при превышении предела, а offer возвращает false.

Метод remove() бросает исключение java.util.NoSuchElementException , если очередь пуста, а метод poll() возвращает в этом случае null.

Обычно Queue не позволяет хранить элементы со значением null, так как null используется в качестве специального возвращаемого значения некоторых методов. Исключением является LinkedList, который позволяет хранить null по историческим причинам.

Реализации Queue обычно не предлагают методов hashCode() и equals(), основанных на элементах. Вместо этого они обычно наследуют стандартные реализации этих методов от Object.

java.util.Deque

Интерфейс java.util.Deque представляет собой очередь с двумя концами, то это линейная коллекция элементов в возможности добавления и удаления элементов с обоих концов.

Deque можно использовать и в качестве очереди и в качестве стека.

Стандартные реализации: java.util.ArrayDeque, java.util.LinkedList.

Специальная реализация: java.util.concurrent.LinkedBlockingDeque.

Вид операции Первый элемент (Начало) Последний элемент (конец)
Добавление элемента
addFirst(e)
offerFirst(e)
addLast(e)
offerLast(e)
Удаление элемента
removeFirst()
pollFirst()
removeLast()
pollLast()
Проверка элемента
getFirst()
peekFirst()
getLast()
peekLast()

java.util.Map

Интерфейс java.util.Map представляет собой карту/отображение/справочник или как там ещё можно перевести. Он отображает ключи на значения. Map не может содержать дублирующиеся ключи. Каждый ключ отображается не более чем на одно значение. В отличие от других интерфейсов коллекций этот интерфейс НЕ наследуется от интерфейса java.util.Collection.

В платформе Java есть три стандартные реализации Map: HashMap, TreeMap, LinkedHashMap. Их производительность и особенности аналогичны реализациям Set: HashSet, TreeSet, LinkedHashSet.

Есть реализации специального назначения: java.util.EnumMap, java.util.WeakHashMap, java.util.IdentityHashMap. Реализация EnumMap предназначена специально для карт со значениями перечисления одного вида в качестве ключей. WeakHashMap использует слабые ссылки на свои ключи, что позволяет сборщику мусора удалить пару ключ-значение, если на них нет больше ссылок, кроме как внутри самого WeakHashMap. IdentityHashMap — реализация на основе хеш-таблицы. При сравнении ключей и значений он использует сравнение ссылок, а не сравнение объектов, в отличие от остальных реализаций.

Основные методы:

 

Связывает значение value с ключом key. Возвращает предыдущее связанное значение либо null. Метод также может вернуть null, если предыдущее связанное значение было null (Некоторые реализации карт поддерживают значения null ). Используйте метод boolean containsKey(Object key) , чтобы различать подобные ситуации.

 

Возвращает значение, которое связано с ключом key. Возвращает null, если нет ассоциации с ключом key. Может также вернуть null, если key связан со значением null (Некоторые реализации карт поддерживают значения null ). Используйте метод boolean containsKey(Object key) , чтобы различать подобные ситуации.

 

Удаляет связку ключ-значение для ключа key. Возвращает значение, которое было связано с этим ключом или null, если не было связки с таким ключом. Может также вернуть null, если key был связан со значением null (Некоторые реализации карт поддерживают значения null). Используйте метод boolean containsKey(Object key) , чтобы различать подобные ситуации.

 

 

Возвращает true, если карта содержит связку со значением для ключа key.

 

Возвращает true, если карта содержит хотя бы одну связку со значением value. Для большинства реализаций этот метод может потребовать линейное относительно размера карты время.

 

Возвращает количество связок ключ-значение в карте.

 

Копирует все связки из m в карту.

 

Удаляет все связки из карты.

 

 

Возвращает Set, содержащий ключи из Map. Последующие изменения в Map отражаются в возвращённом Set. Удаление элемента из Set удаляет связку из Map.

 

Возвращает Set, содержащий все связки из карты. Изменения в возвращённом Set отражаются на исходном Map, так же как и изменения в исходном Map отражаются в этом Set. Этот возвращённый Set поддерживает удаление элементов, но не поддерживает добавление.

 

Возвращает коллекцию, содержащую значения из Map. Изменения в исходном Map отражаются в возвращённой коллекции и наоборот. Коллекция поддерживает удаление элементов, что удаляет связку из карты, но не поддерживает операции добавления.

Сортировка объектов

Список List может быть отсортирован с помощью метода:

Если List состоит из элементов String, то они будут отсортированы в алфавитном порядке. Если он состоит из элементов Date, то список будет отсортирован в хронологическом порядке. Но как это происходит? String и Date реализуют интерфейс java.lang.Comparable. Реализации интерфейса java.lang.Comparable предоставляют естественный порядок сортировки для класса, который позволяет сортировать объекта класса автоматически. Приведённая ниже таблица описывает основные классы платформы Java, реализующие интерфейс Comparable:

Классы, реализующие Comparable
Класс Естественный порядок
Byte Знаковый числовой
Character Беззнаковый числовой
Long Знаковый числовой
Integer Знаковый числовой
Short Знаковый числовой
Double Знаковый числовой
Float Знаковый числовой
BigInteger Знаковый числовой
BigDecimal Знаковый числовой
Boolean Boolean.FALSE < Boolean.TRUE
File Зависимый от системы лексикографический порядок от пути к файлу.
String Лексикографический
Date Хронологический
CollationKey Зависимый от региональных настроек лексикографический

Если вы пытаетесь сортировать список, элементы которого не реализуют интерфейс Comparable, то Collections.sort(list) бросит исключение java.lang.ClassCastException. Так же Collections.sort(list, comparator) бросит исключение java.lang.ClassCastException, если вы попытаетесь отсортировать список, элементы которого не могут сравниваться посредством этого comparator-а. Элементы, которые могут сравниваться друг с другом называют взаимно сравнимые. Несмотря на то что элементы разных типов могут быть взаимно сравнимыми, ни один из классов, перечисленных здесь, не допускает межклассового сравнения.

Интерфейс java.lang.Comparable состоит из следующего метода:

Метод compareTo сравнивает текущий объект с указанным объектом и возвращает отрицательное число, ноль или положительное число, если наш объект меньше, равен или больше переданного в параметрах соответственно. Если переданный объект не может сравниваться с нашим объектом, то метод бросает исключение java.lang.ClassCastException.

Пример:

Этот пример показывает следующее:

  • Объекты Name неизменяемые. Неизменяемые объекты очень полезны, особенно при использовании объектов в качестве элементов Set-ов или ключей Map-ов. Эти коллекции будут работать некорректно, если вы будете изменять содержимое их элементов или ключей во время выполнения.
  • Конструктор проверяет свои аргументы на null. Это гарантирует, что все объекты Name будут нормально сконструированы, и ни один из методов никогда не бросит исключения java.lang.NullPointerException.
  • Метод hashCode переопределён. Важно переопределять этот метод для любого класса, который переопределяет метод equals. (Равные объекты должны иметь одинаковые хеш-коды.)
  • Метод equals возвращает false, если переданный объект равен null или неподходящего типа. Метод compareTo бросает исключение в подобных ситуациях. Оба этих поведения требуются согласно контракту этих методов.
  • Метод toString переопределён так, чтобы он выводил объект Name в понятном для человека формате. Старайтесь всегда переопределять метод toString, особенно если объекты планируется помещать в коллекции. Многие коллекции имеют toString, использующий методы toString у своих элементов, ключей и значений.

Метод compareTo объекта Name реализует стандартный алгоритм сортировки имён, где фамилия идёт перед именем, что соответствует ожиданию естественной сортировки. Это заводило бы в тупик, на самом деле, если бы естественный порядок не совпадал с естественным!

Пример программы, создающей массив элементов класса Name и сортирующей их:

Если запустить эту программу, то она выведет в консоль:

Метод compareTo должен следовать четырём важным правилам (здесь sgn(expression) означает знак выражения):

  • Для всех x и y должно выполняться равенство sgn(x.compareTo(y)) == -sgn(y.compareTo(x)). (Если x.compareTo(y) бросает исключение, то y.compareTo(x) также должно бросать исключение.)
  • Сравнение должно быть транзитивным ( x.compareTo(y)>0 && y.compareTo(z)>0 означает, что x.compareTo(z)>0).
  • x.compareTo(y)==0 означает, что sgn(x.compareTo(z)) == sgn(y.compareTo(z)) для любых z.
  • Очень рекомендуется, чтобы (x.compareTo(y)==0) == (x.equals(y)), то есть compareTo не должен работать вразнобой с equals.

При необходимости сортировать объекты в отличном от естественного, нужно использовать интерфейс java.util.Comparator:

Метод compare сравнивает два аргумента, возвращая отрицательное число, ноль или положительное число, если первый аргумент меньше, равен или больше второго соответственно. Если типы переданных аргументов не подходят для этого Comparator-а, то метод compare бросает исключение java.lang.ClassCastException.

Большая часть сказанного про java.lang.Comparable относится и к java.util.Comparator. Метод compare должен придерживаться тех же четырёх правил, что и метод compareTo у Comparable.

Предположим, что у нас есть класс Employee:

Давайте предположим, что естественный порядок сортировки экземпляров Employee — это их сортировка по Name (как в предыдущем примере). К сожалению, начальник просил выводит список сотрудников по трудовому стажу. Это означает, что нам нужно сделать немного дополнительной работы:

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

Некоторые программисты иногда используют другой способ:

Всегда используйте первый способ, так как второй способ не гарантирует правильную работу. Причина этого в том, что метод compareTo может вернуть отрицательный int, если его аргумент меньше объекта, для которого он вызван. Есть одно отрицательное значение для int , которое остаётся отрицательным, если к нему применять унарный минус:

Comparator, который мы написали выше может сортировать List, но он не может использоваться в сортированных коллекциях, например TreeSet, так как он генерирует порядок сортировки, несовместимый с equals. Это означает, что этот Comparator указывает равными те объекты, которые методы equals указывает как разные. Например, два сотрудника, которые были наняты в один день, будут равны. При сортировке в списке List это не имеет значения, но при использовании Comparator-а для упорядоченной коллекции, это будет фатально. Если вы будете использовать этот Comparator, чтобы вставить несколько сотрудников, нанятых в один и тот же день в TreeSet, то будет добавлен только первый из них, а второй будет пригнорирован, как дублирующий.

Чтобы исправить эту проблему, нужно скорректировать Comparator так, чтобы он производил порядок, совместимый с equals. Другими словами, нужно сделать так, чтобы равными были только те элементы, который равны для метода equals. Для этого нужно выполнять два сравнения: наше сравнение по дате найма, затем сравнение по атрибуту, которой уникально идентифицирует объект. Для уникальной идентификации в нашем случае идеально подходит номер сотрудника:

Вы, возможно, захотите заменить последний return на более простой:

Делайте это только в том случае, если вы абсолютно уверены, что ни один сотрудник не будет иметь отрицательного номера. Этот трюк обычно работает, потому что знаковое число достаточно велико для того, чтобы представить разницу между двумя произвольными знаковыми числами. Если i является большим положительным числом, а j является большим отрицательным числом, то i - j приведёт к переполнению и вернёт отрицательное число. Много людей обожглись на этом.

java.util.SortedSet

Интерфейс java.util.SortedSet это java.util.Set, который поддерживает свои элементы в отсортированном по возрастанию виде согласно естественному порядку или согласно Comparator-у, который бел передан в конструктор. В дополнение к обычным операциям java.util.Set-а интерфейс java.util.SortedSet добавляет три вида операций:

  • Range-view — работа с частью Set-а.
  • Конечные точки — возвращают первый и последний элемент в множестве.
  • Доступ к Comparator-у, который используется для сортировки множества, если есть.

Интерфейс java.util.SortedSet наследуется от java.util.Set и ведёт себя так же, но с двумя исключениями:

  • Итератор обходит SortedSet в соответствии с порядком сортировки.
  • Метод toArray возвращает отсортированный массив.

По соглашению все реализации интерфейса java.util.Collection общего назначения имеют стандартный конструктор, который принимает Collection в качестве параметра. Реализации SortedSet не являются исключением. В TreeSet этот конструктор создаёт экземпляр, который сортирует эти элементы в соответствии с их естественным порядком. Однако было бы гораздо лучше динамически проверять, была ли коллекция экземпляром SortedSet, и сортировать TreeSet в соответствии с тем же Comparator-ом или естественным порядком. Специально для этого есть конструктор, который принимает SortedSet и возвращает новый экземпляр TreeSet, который содержит те же самые элементы, отсортированные в соответствии с тем же самым критерием. Заметьте, что определяется на этапе компиляции, а не на этапе выполнения, так как используется перегрузка конструкторов.

Реализации SortedSet также по соглашению имеют конструктор, который принимает java.util.Comparator и возвращает пустое множество, которое сортируется в соответствии с указанным Comparator-ом. Если в конструктор передаётся null, то используется естественный порядок сортировки.

Операции работы с частью множества аналогичны операциям работы с частью списков, но есть одна большая разница. Подмножество остаётся валидным даже в том случае, если исходное множество было изменено напрямую. Это осуществимо, так как конечные точки подмножества являются абсолютными точками из элементов, а не индексами элементов, как это было для списков.

Сортированные множества имеют три методы получения подмножества. Первый метод — subSet. Он имеет два параметра, в которых указываются сами элементы диапазона подмножества. Эти элементы должны быть сравнимы с элементами в множестве, используя Comparator SortedSet-а или естественного порядка его элементов, смотря что используется. Начальный элемент включается в подмножество, а конечный не включается в подмножество.

Пример:

Удаление всех элементов, начинающихся в буквы “f”:

Сколько слов начинаются с каждой буквы:

Предположим, что мы хотим увидеть закрытый интервал, который содержит обе конечный точки, вместо открытого интервала. Если тип элемента позволяет вычислить следующее за данным значение в пространстве элементов, то нам всего лишь нужно вызвать subSet от lowEndpoint до следующего за highEndpoint элемента. Несмотря на то что это не совсем очевидно, следующий элемент за строкой s в естественном порядке класса String будет s + "\0", то есть s и символ null.

Таким образом получим следущий код, который вычисляет, сколько слов между "doorbell" и "pickle", включительно, хранится в нашем множестве:

Тот же приём можно использовать, чтобы получить открытый интервал, который не содержит ни одну из конечный точек:

Есть также два метода: headSet и tailSet. Эти методы принимают в качестве параметра только один объект. Метод headSet возвращает подмножество от начала до указанного объекта, исключая указанный объект. Второй возвращает множество от указанного объекта (включительно) до конца SortedSet-а. Пример:

SortedSet имеет методы для получения первого и последнего элементов в множестве: first и last.

Интерфейс SortedSet также содержит метод Comparator<? super E> comparator() , который возвращает Comparator, используемый для сортировки элементов множества, или null, если используется естественный порядок сортировки.

java.util.SortedMap

Интерфейс java.util.SortedMap представляет собой java.util.Map, который хранит свои элементы отсортированными по возрастанию ключей, в соответствии с естественным порядком или указанным Comparator-ом.

Интерфейс java.util.SortedMap содержим методы из java.util.Map и дополнительные:

  • Range view — работа с частью SortedMap.
  • Конечные точки — получение первого и последнего ключа карты.
  • Доступ к Comparator-у, если он есть.

Операции SortedMap, унаследованные от Map, действуют аналогично, но имеют две особенности:

  • Итератор проходит по элементам в соответствии с порядком сортировки.
  • Методы toArray у коллекций ключей, значений и элементов возвращают отсортированные массивы.

Согласно соглашению все реализации Map содержат конструктор, который принимает Map в качестве параметра. Реализации SortedMap тоже имеют такой конструктор. В java.util.TreeMap этот конструктор создаёт экземпляр, который упорядочивает свои элеметы в соответствии с естественным порядком сортировки ключей. Однако было бы лучше динамически проверять, что переданный Map является экземпляром SortedMap, и сортировать его с тем же критерием ( Comparator-ом или естественным порядком сортировки). TreeMap содержит ещё один конструктор, который принимает SortedMap и создаёт TreeMap, содержащий связки из переданного SortedMap, отсортированные по тому же критерию. Заметьте, что это определяется на этапе компиляции, так как используется перегрузка конструкторов.

Другие реализации интерфейсов коллекций

Класс java.util.Collections имеет специальные методы, позволяющие любую коллекцию обернуть в синхронизированную коллекцию, которая использует исходную коллекцию, но добавляет синхронизацию:

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

Также можно обернуть коллекцию, получив неизменяемую коллекцию, элементы которой нелья добавлять, удалять или заменять (возникнет java.lang.UnsupportedOperationException). Для этого нужно использовать следующие методы класса Collections:

Можно получить коллекцию с динамически проверяемым во время выполнения типом:

Любой массив можно превратить в неизменяемый список с помощью метода java.util.Arrays.asList:

С помощью метода Collections.nCopies можно создать неизменяемый список, содержащий указанное количество копий элемента:

Можно создать неизменяемое множество, состоящее только из одного элемента Collections.singleton:

С помощью методов Collections.emptySet() , Collections.emptyList() , Collections.emptyMap() можно создать пустые коллекции:

Stream

Предположим, что мы создаём приложение социальной сети, и члены этой социальной сети представляются классом Person:

Следующий пример выводит все имена:

То же самое с помощью потоков и агрегатных операций:

В этом примере версия со stream-ами длиннее, но для более сложных задач версии с потоками будут более лаконичны.

Канал (pipeline) — это последовательность агрегатных операций. Следующий пример выводит членов мужского пола из коллекции roster в канал (pipeline), который состоит из агрегатных операций filter и forEach:

Сравните этот пример со следующим, который делает то же самое, но с циклом for-each:

Канал (pipeline) состоит из следу.щих компонентов:

  • Источник, в роли которого может выступать коллекция, массив, генерирующая функция или канал ввода/вывода.
  • Ноль или более промежуточных операций. Промежуточная операция, например filter, порождает новый stream. Операция filter возвращает новый stream, который содержит элементы, удовлетворяющие условию. В этом примере используется лямбда-выражение e -> e.getGender() == Person.Sex.MALE. Оно возвращает true, если поле gender объекта e содержит значение Person.Sex.MALE.
  • Терминальная операция, например forEach, создаёт не-stream результат, например значение примитивного типа, коллекцию или не возвращает никаких значений совсем. В этом примере параметром forEach является лямбда-выражение e -> System.out.println(e.getName()).

Следующий пример вычисляет средний возраст всех членов мужского пола, содержащихся в коллекции roster с каналом (pipeline), содержащим агрегатные операции filter, mapToInt и average:

Операция mapToInt возвращает новый stream типа IntStream (который является stream-ом, содержащим только int). Операция применяет функцию, переданную в параметр, к каждому элементу stream-а. В этом примере функция Person::getAge является ссылкой на метод получения возраста. В результате mapToInt возвращает stream, содержащий возрасты всех членов мужского пола из колекции roster.

Операция average вычисляет среднее значение элементов из stream-а типа IntStream. Она возвращает объект типа java.util.OptionalDouble. Если stream не содержит элементов, то average возвращает пустой экземпляр java.util.OptionalDouble, и вызов метода getAsDouble приведёт к исключению java.util.NoSuchElementException.

JDK содержит множество терминальных операций (average, sum, min, max, count и другие), которые возвращают одно значение на основе содержимого stream-а. Такие операции называются редукционными операциями (reduction operations). JDK также содержит редукционные операции, которые возвращают коллекцию вместо одного значения. Многие редукционные операции выполняют конкретную задачу, например нахождение среднего значения или группировка элементов по категориям. Однако JDK содержит редукционные операции общего назначения reduce и collect, которые и будут рассмотрены более детально.

Метод stream.reduce — редукционная операция (reduction operation) общего назначения.

Рассмотрите следующий канал (pipeline):

И сравните его со следующим, использующим операцию Stream.reduce:

В этом примере операция reduce принимает два аргумента:

  • identity: начальное значение редукции и результат по умолчанию для случая, когда нет элементов в stream. В этом примере 0.
  • accumulator: функция с двумя параметрами: частичный результат редукции (в этом примере сумма обработанных чисел до этого момента) и следующий элемент stream-а . Он возвращает частичный результат. В этом примере функция accumulator-а является лямбда-выражением, которое складывает два Integer-а и возвращает полученный результат.

Операция reduce всегда возвращает новое значение. Однако функция accumulator-а возвращает новое значение каждый раз, когда она обрабатывает элемент из stream. Предположим, что мы ходим превратить эти элементы в более сложный объект, например коллекцию. Если мы будет для этого использовать reduce , то каждая обработка элемента будет вызывать создание новой коллекции, что неэффективно.

В отличие от метода reduce, который всегда создаёт новое значение при обработке элемента, метод collect меняет существующее значение.

Рассмотрим поиск средних значений в stream. Нам понадобится общее количество элементов и сумма этих элементов. Однако как и reduce и все другие редукционные методы, метод collect возвращает только одно значение. Мы можем создать новый тип данных, который будет хранить общее количество элементов и сумму этих элементов:

Следующий pipeline использует класс Averager и метод collect для вычисления среднего возраста всех членов мужского пола:

Операция collect в этом примере принимает три аргумента:

  • supplier: фабричная функция, которая создаёт экземпляры. Для операции collect она создаёт экземпляры результирующего контейнера. В этом примере экземпляры класса Average.
  • accumulator: функция включает элемент из steam в число членов результирующего контейнера. В этом примере она модифицирует контейнер Average, увеличивая переменную count на единицу и добавляя элемент из stream-а к полю total.
  • combiner: функция, которая принимает два результирующих контейнера и объединяет их содержимое. В этом примере меняет контейнер Average, увеличивая переменную count на переменную count из другого экземпляра Average и добавляя total одного экземпляра к total другого экземпляра.

Обратите внимание на следующее:

  • supplier — лямбда выражение (или ссылка на метод) в отличие от значения identity в методе reduce.
  • Функции accumulator и combiner не возвращают значений.
  • Вы можете использовать операции collect с параллельными stream-ами. (Если вы запустите метод collect с параллельным stream, то JDK создаст новый поток, когда функция combiner создаёт новый объект, а значит вам не нужно беспокоиться о синхронизации)

Несмотря на то что в JDK есть операция average для вычисления среднего значения элементов в stream, вы можете использовать collect и свой класс, если вам нужно вычислить несколько значений из элементов stream-а.

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

Эта версия collect принимает один парамер типа Collector. Этот класс содержит три функции, которые могут использоваться в качестве аргументов операции collect.

Класс java.util.stream.Collectors содержит много полезный редукционных операций, включая сбор элементов в коллекцию и суммирование элементов по различным критериям. Эти редукционные операции возвращают экземпляры класса java.util.stream.Collector, а значит вы можете использовать их в качестве параметра операции collect.

Пример использует Collectors.toList, который собирает элементы stream-а в новый экземпляр List. Как и большинство методов класса Collectors, метод toList возвращает экземпляр Collector, а не саму коллекцию.

Следующий пример группирует элементы roster по полу:

Операция groupingBy в этом примере принимает два параметра: функция, по которой происходит группировка, и экземпляр Collector. Параметр Collector называется downstream collector. Этот пример использует коллектор mapping, который применяет функцию Person::getName к каждому элементу в stream. В результате получаем stream, который содержит только имена членов roster. Канал (pipeline), содержащий один или более downstream collector-ов, как в этом примере называется многоуровневой редукцией (multilevel reduction).

Следующий пример получает суммарный возраст членов каждого пола:

Операция reducing принимает три параметра:

  • identity. Одновременно является начальным элементом редукции и результатом по умолчанию, когда в stream нет элементов. В этом примере identity равен 0.
  • mapper: Операция reducing применяет функцию ко всем элементам в stream. В нашем примере функция получает возраст каждого члена.
  • operation: функция используется для редукции значений, возвращённых mapper-ом. В этом примере значения складываются.

Следующий пример получает средний возраст членов каждого пола:

Параллельные вычисления включают в себя разделение проблемы на подпроблемы и последующее решение этих подпроблем одновременно, а затем объединение результатов решений этих подпроблем. В Java есть Fork/Join Framework, который облегчает реализацию параллельных вычислений в ваших приложениях. Однако с этим фреймворком вам приходится указывать, как разделять проблему. С агрегатными операциями Java осуществляет такое разделение и объединение результатов за вас.

Одна сложность в реализации параллелизама в приложениях, использующих коллекции, — коллекции не являются потокобезопасными, что означает, что несколько потоков не могут манипулировать коллекцией без вмешательства в поток (thread interference) и ошибок консистентности памяти (memory consistency errors). Collections Framework предоставляет специальные обёртки, которые делают синхронизацию для любой коллекции, что делает их потокобезопасными. Однако синхронизация приводит к конкуренции потоков. Вы хотите избежать конкуренции потоков, так как это мешает параллельной работы потоков. Агрегатные операции и параллельные потоки позволяют реализовать параллелизм с непотокобезопасносными коллекциями, так как вы не меняете коллекцию, пока вы работаете с ней.

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

Вы можете выполнять stream-ы последовательно или параллельно. При выполнении stream-ов параллельно Java разделяет stream на несколько substream-ов. Агрегатные операции проходят по этим substream-ам параллельно и затем объединяют результат.

Когда вы создаёте stream, то stream всегда последовательный, если не указано обратное. Чтобы создать параллельный stream, вызовите метод java.util.Collection.parallelStream, либо вы можете вызвать java.util.stream.BaseStream.parallel. Например, следующая инструкция вычисляет средний возраст всех мужских участников параллельно:

Рассмотрим ещё раз следующий пример, который группирует членов по половой принадлежности. Этот пример вызывает метод collect, который преобразует коллекцию roster в Map:

Следующий код эквивалентен, но работает параллельно:

Это называется конкурентной редукцией (concurrent reduction). Платформа Java осуществляет конкурентную редукцию, если выполняются следующие три пункта для конкретного канала (pipeline), который содержит операцию collect:

Этот пример возвращает экземпляр java.util.concurrent.ConcurrentMap, вместо java.util.Map, и вызывает groupingByConcurrent вместо groupingBy. В отличие от groupingByConcurrent, операция groupingBy работает медленнее с параллельными stream-ами. Так же операция Collectors.toConcurrentMap работает быстрее с параллельными stream-ами, чем операция Collectors.toMap.

Порядок обработки элементов в pipeline-ом зависит от того, параллельный был stream или нет, источника stream, промежуточных операций. Например, рассмотрите следующий пример, который выводит элементы экземпляра ArrayList с помощью forEach несколько раз:

Пример состоит из пяти каналов (pipelines). Его вывод похож на следующее:

Этот пример делает следующее:

  • Первый pipeline выводит элементы списка listOfIntegers в том порядке, в котором они были добавлены в список.
  • Второй pipeline выводит элементы listOfIntegers после их сортировки методом Collections.sort.
  • Третий и четвёртый pipeline-ы пишут элементы списка в случайном порядке. Запомните, что операции stream-а используют внутренний обход элементов при обработке stream-а, а значит, когда вы выполняете stream параллельно, компилятор Java и среда выполнения определяют порядок обработки элементов stream, чтобы увеличить производительность параллельных вычислений, если другое не указано операцией.
  • Пятый pipeline использует метод forEachOrdered, который обрабатывает элементы stream-а в порядке, определяемом источником, независимо от параллельного или последовательно выполнения stream. В этом случае вы можете потерять преимущества параллелизма.

Метод или выражение имеет побочный эффект, если в дополнение к возврату значения они меняют состояние компьютера. Примеры включают изменяемые редукции (операции, использующие collect ), вызывающие System.out.println. JDK обрабатывает некоторые побочные эффекты в каналах (pipeline). В частности метод collect разработан так, что он осуществляет общие операции со stream, которые имеют побочные эффекты, безопасным для параллельных вычислений способом. Операции вроде forEach и peek разработаны для побочных эффектов; лямбда-выражения, которые возвращают void, например вызывающие System.out.println, не могут делать ничего другого, кроме как порождать побочные эффекты. Но даже с этим вам следует использовать операции forEach и peek с осторожностью. Также никогда не передавайте в качестве параметров лямбда-выражения, которые имеют побочные эффекты, в операции filter и map.

Все промежуточные операции ленивые. Выражение, метод или алгоритм ленивый, если его значение вычисляется только тогда, когда оно нужно. Промежуточные операции ленивые, так как они не начинают вычисление содержимого sream-а до начала терминальной операции. Ленивая обработка stream-ов позволяет компилятору Java и среде выполнения оптимизировать процесс вычислений. Например, в канале (pipeline) вроде filter-mapToInt-average операция average может получить несколько первых чисел из stream-а, созданного mapToInt, который получает элементы из filter. Операция average будет повторять этот процесс до тех пор, пока она не получит все необходимые элементы из stream-а, а затем вычислит среднее.

Лямбда-выражения в stream-ах не должны мешать друг другу. Вмешательство (interference) возникает, когда источник stream-а меняется во время обработки каналом (pipeline) stream-а. Например, следующий код пытается соединить строки в списке listOfStrings. Однако он приводит к исключению ConcurrentModificationException:

Пример соединяет строки, содержащиеся в listOfStrings, в Optional<String> с помощью операции reduce , которая является терминальной. Однако pipeline вызывает промежуточную операцию peek, которая пытается добавить новый элемент в listOfStrings. Запомните, что промежуточные операции ленивые. Это означает, что канал (pipeline) в этом примере начинает своё выполнение, когда вызывается операция get, и заканчивает выполнение, когда операция get завершается. Аргумент операции peek пытается изменить источник stream-а во время выполнения pipeline, что приводит к возникновению исключения ConcurrentModificationException.

Избегайте использования лямбда-выражений, которые сохраняют своё состояние, в качестве параметров операций stream-ов. Следующий пример добавляет элементы из списка listOfIntegers в новый экземпляр List с промежуточной операцией map. Он делает это дважды: первый раз последовательным stream-ом, а второй раз параллельным stream-ом. Сам пример:

Лямбда-выражение e -> {parallelStorage.add(e); return e; } сохраняет состояние. Его результат может меняться при каждом выполнении его кода. Этот пример выведет в консоль следующее:

Операция forEachOrdered обрабатывает элементы в порядке, указаном stream-ом, независимо от параллельного или последовательного выполнения stream-а. Однако когда stream выполняется параллельно, операция map обрабатывает элементы stream-а в порядке, указанным компилятором и средой Java. В результате порядок добавления элементов может меняться при каждом запуске кода. Никогда не используйте сохраняющие состояние лямбда-выражения в операциях stream.

Заметка: Этот пример вызывает метод synchronizedList, так что List parallelStorage потокобезопасен. Запомните, что коллекции не являются потокобезопасными. Это означает, что они не должны обрабатываться несколькими потоками одновременно. Предположим, что мы не вызвали метод synchronizedList при создании parallelStorage:

Пример будет вести себя ошибочно, так как несколько потоков пытаются менять parallelStorage без механизма синхронизации. В результате пример мог бы вывести что-то вроде этого:

Стандартные алгоритмы

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

 

Методы Collections.sort сортируют содержимое списка в соответствии с естественным порядком, либо в соответствии с указанным компаратором.

Пример:

 

 

Метод Collections.shuffle перемешивает содержимое списка случайным образом.

 

Метод Collections.reverse меняет порядок элементов в списке на обратный.

 

Метод Collections.fill заменяет все элементы списка на obj.

 

Метод Collections.copy копирует все элементы из списка src в список dest. Список dest должен содержать количество элементов как минимум равное количеству элементов src.

 

Меняет местами два элемента в списке.

 

Метод Collections.addAll добавляет все указанные элементы в коллекцию c.

 

Методы Collections.binarySearch ищут вхождение элемента в списке с помощью бинарного поиска и естественного порядка сортировки или компаратора. Список должен быть отсортирован по возрастанию в помощью используемого компаратора или в естественном порядке (зависимости от того, что используется при поиске). Если есть несколько искомых элементов, то может вернуться индекс любого из них. Если искомый объект не найден, то возвращается (-(insertion point) - 1) , где insertion point — позиция, куда следовало бы вставить элемент.

 

Метод Collections.frequency возвращает количество элементов o в коллекции c. Для сравнения используется метод equals.

 

Возвращает true , если две коллекции не имеют ни одного общего элемента.

 

Цикл статей «Учебник Java 8».

Следующая статья — «Java 8 дата и время».
Предыдущая статья — «Java 8 регулярные выражения».


Поделиться: