Java Language
Коллекции

Вступление

замечания

Объявление ArrayList и добавление объектов

Мы можем создать ArrayList (после интерфейса List ):

List aListOfFruits = new ArrayList();

List<String> aListOfFruits = new ArrayList<String>();

List<String> aListOfFruits = new ArrayList<>();

Теперь используйте метод add для добавления String :

aListOfFruits.add("Melon");
aListOfFruits.add("Strawberry");

В приведенном выше примере ArrayList будет содержать String «Дыня» с индексом 0 и String «Клубника» по индексу 1.

Также мы можем добавить несколько элементов с помощью addAll(Collection<? extends E> c)

List<String> aListOfFruitsAndVeggies = new ArrayList<String>();
aListOfFruitsAndVeggies.add("Onion");
aListOfFruitsAndVeggies.addAll(aListOfFruits);

Теперь «Лук» помещается в индекс 0 в aListOfFruitsAndVeggies , «Дыня» находится в индексе 1, а «Клубника» - с индексом 2.

Построение коллекций из существующих данных

Стандартные коллекции

Структура коллекций Java

Простым способом построения List из отдельных значений данных является использование метода java.utils.Arrays Arrays.asList :

List<String> data = Arrays.asList("ab", "bc", "cd", "ab", "bc", "cd");

Все стандартные реализации коллекции предоставляют конструкторы, которые берут другую коллекцию в качестве аргумента, добавляя все элементы в новую коллекцию во время построения:

List<String> list = new ArrayList<>(data); // will add data as is
Set<String> set1 = new HashSet<>(data); // will add data keeping only unique values
SortedSet<String> set2 = new TreeSet<>(data); // will add data keeping unique values and sorting
Set<String> set3 = new LinkedHashSet<>(data); // will add data keeping only unique values and preserving the original order

Система коллекций Google Guava

Еще одна отличная основа - это Google Guava который является удивительным классом полезности (предоставляющим удобные статические методы) для построения различных типов стандартных коллекций. Lists и Sets :

 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 ...
 List<String> list1 = Lists.newArrayList("ab", "bc", "cd");
 List<String> list2 = Lists.newArrayList(data);
 Set<String> set4 = Sets.newHashSet(data);
 SortedSet<String> set5 = Sets.newTreeSet("bc", "cd", "ab", "bc", "cd");

Составление карт

Структура коллекций Java

Аналогично для карт, учитывая Map<String, Object> map новая карта может быть построена со всеми элементами следующим образом:

Map<String, Object> map1 = new HashMap<>(map);
SortedMap<String, Object> map2 = new TreeMap<>(map);

Общий раздел

Используя Apache Commons вы можете создать Map using array в ArrayUtils.toMap а также MapUtils.toMap :

 import org.apache.commons.lang3.ArrayUtils;
 ...
 // Taken from org.apache.commons.lang.ArrayUtils#toMap JavaDoc

 // Create a Map mapping colors.
 Map colorMap = MapUtils.toMap(new String[][] {{
     {"RED", "#FF0000"},
     {"GREEN", "#00FF00"},
     {"BLUE", "#0000FF"}});

Каждый элемент массива должен быть либо Map.Entry, либо Array, содержащий как минимум два элемента, где первый элемент используется как ключ, а второй - как значение.

Система коллекций Google Guava

Класс полезности из системы Google Guava называется Maps :

 import com.google.common.collect.Maps;
 ...
 void howToCreateMapsMethod(Function<? super K,V> valueFunction,
           Iterable<K> keys1, 
           Set<K> keys2, 
           SortedSet<K> keys3) {
     ImmutableMap<K, V> map1 = toMap(keys1, valueFunction); // Immutable copy
     Map<K, V> map2 = asMap(keys2, valueFunction); // Live Map view
     SortedMap<K, V> map3 = toMap(keys3, valueFunction); // Live Map view
 }

Stream.of("xyz", "abc").collect(Collectors.toList());

Arrays.stream("xyz", "abc").collect(Collectors.toList());

Регистрация списков

Следующие способы могут использоваться для объединения списков без изменения списка источников.

Первый подход. Имеет больше строк, но легко понять

List<String> newList = new ArrayList<String>();
newList.addAll(listOne);
newList.addAll(listTwo);

Второй подход. Имеет одну меньшую строку, но менее читаемую.

List<String> newList = new ArrayList<String>(listOne);
newList.addAll(listTwo);

Третий подход. Требуется сторонняя библиотека коллекций коллекций Apache .

ListUtils.union(listOne,listTwo);

List<String> newList = Stream.concat(listOne.stream(), listTwo.stream()).collect(Collectors.toList());

Рекомендации. Список интерфейсов

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

Излишне удалять элементы из списка в цикле, это связано с тем, что индекс и длина списка изменены.

Учитывая следующий список, вот несколько примеров, которые приведут к неожиданному результату, а некоторые - к правильному результату.

List<String> fruits = new ArrayList<String>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Strawberry");

НЕПРАВИЛЬНО

Удаление в итерации for утверждения Пропускает «Банан»:

Образец кода будет печатать только Apple и Strawberry . Banana пропускается, потому что он перемещается в индекс 0 когда Apple удаляется, но в то же время i увеличиваю до 1 .

for (int i = 0; i < fruits.size(); i++) {
    System.out.println (fruits.get(i)); 
    if ("Apple".equals(fruits.get(i))) {
         fruits.remove(i);
    }     
}

Удаление в расширении for оператора Throws Exception:

Из-за итерации над сборкой и ее модификацией в одно и то же время.

Броски: java.util.ConcurrentModificationException

for (String fruit : fruits) { 
    System.out.println(fruit);
    if ("Apple".equals(fruit)) {
        fruits.remove(fruit);
    }
}

ПРАВИЛЬНЫЙ

Удаление во время цикла с использованием Iterator

Iterator<String> fruitIterator = fruits.iterator();
while(fruitIterator.hasNext()) {     
    String fruit = fruitIterator.next();     
    System.out.println(fruit);
    if ("Apple".equals(fruit)) {
        fruitIterator.remove();
    } 
}

Интерфейс Iterator имеет метод remove() построенный только для этого случая. Однако этот метод помечен как «необязательный» в документации, и он может вызывать UnsupportedOperationException .

Выбрасывает: UnsupportedOperationException - если операция удаления не поддерживается этим итератором

Поэтому рекомендуется проверить документацию, чтобы убедиться, что эта операция поддерживается (на практике, если коллекция не является неизменной, полученной через стороннюю библиотеку или использование одного из методов Collections.unmodifiable...() операция почти всегда поддерживается).

При использовании Iterator возникает modCount ConcurrentModificationException когда modCount из List изменяется с момента создания Iterator . Это могло произойти в том же потоке или в многопоточном приложении, использующем один и тот же список.

modCount - это переменная int которая подсчитывает количество структурных изменений этого списка. Структурное изменение по существу означает операцию add() или remove() , вызываемую в объекте Collection (изменения, сделанные Iterator , не учитываются). Когда Iterator создан, он сохраняет этот modCount и на каждой итерации List проверяет, modCount ли текущий modCount тем, как и когда был создан Iterator . Если modCount значение modCount оно выдает modCount ConcurrentModificationException .

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

Iterator<String> fruitIterator = fruits.iterator();
fruits.set(0, "Watermelon");
while(fruitIterator.hasNext()){
    System.out.println(fruitIterator.next());
}

Но добавление нового элемента в List после инициализации Iterator вызовет исключение ConcurrentModificationException :

Iterator<String> fruitIterator = fruits.iterator();
fruits.add("Watermelon");
while(fruitIterator.hasNext()){
    System.out.println(fruitIterator.next());    //ConcurrentModificationException here
}

Итерация назад

for (int i = (fruits.size() - 1); i >=0; i--) {
    System.out.println (fruits.get(i));
    if ("Apple".equals(fruits.get(i))) {
         fruits.remove(i);
    }
}

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

Итерация вперед, корректировка индекса цикла

for (int i = 0; i < fruits.size(); i++) {
    System.out.println (fruits.get(i)); 
    if ("Apple".equals(fruits.get(i))) {
         fruits.remove(i);
         i--;
    }     
}

Это ничего не пропускает. Когда i й элемент удаляется из List , элемент, первоначально расположенный в индексе i+1 становится новым i м элементом. Поэтому цикл может уменьшать i чтобы следующая итерация обрабатывала следующий элемент без пропусков.

Использование списка «должно быть удалено»

ArrayList shouldBeRemoved = new ArrayList();
for (String str : currentArrayList) {
    if (condition) {
        shouldBeRemoved.add(str);
    }
}
currentArrayList.removeAll(shouldBeRemoved);

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

List<String> filteredList = 
    fruits.stream().filter(p -> !"Apple".equals(p)).collect(Collectors.toList());

fruits.removeIf(p -> "Apple".equals(p));

Немодифицированная коллекция

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

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

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

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MyPojoClass {
    private List<Integer> intList = new ArrayList<>();

    public void addValueToIntList(Integer value){
        intList.add(value);
    }
    
    public List<Integer> getIntList() {
        return Collections.unmodifiableList(intList);
    }
}

Следующая попытка изменить немодифицируемую коллекцию приведет к исключению:

import java.util.List;

public class App {

    public static void main(String[] args) {
        MyPojoClass pojo = new MyPojoClass();
        pojo.addValueToIntList(42);
        
        List<Integer> list = pojo.getIntList();
        list.add(69);
    }
}

выход:

Exception in thread "main" java.lang.UnsupportedOperationException
    at java.util.Collections$UnmodifiableCollection.add(Collections.java:1055)
    at App.main(App.java:12)

Итерирование над коллекциями

Итерирование по списку

List<String> names  = new ArrayList<>(Arrays.asList("Clementine", "Duran", "Mike"));

names.forEach(System.out::println);

names.parallelStream().forEach(System.out::println);

for (String name : names) {
    System.out.println(name);
}

for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));
}

//Creates ListIterator which supports both forward as well as backward traversel
ListIterator<String> listIterator = names.listIterator();

//Iterates list in forward direction
while(listIterator.hasNext()){
    System.out.println(listIterator.next());
}

//Iterates list in backward direction once reaches the last element from above iterator in forward direction
while(listIterator.hasPrevious()){
    System.out.println(listIterator.previous());
}

Итерирование по множеству

Set<String> names = new HashSet<>(Arrays.asList("Clementine", "Duran", "Mike"));

names.forEach(System.out::println);

for (Iterator<String> iterator = names.iterator(); iterator.hasNext(); ) {
    System.out.println(iterator.next());
}

for (String name : names) {
    System.out.println(name);
}

Iterator iterator = names.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

Итерация по карте

Map<Integer, String> names = new HashMap<>();
names.put(1, "Clementine");
names.put(2, "Duran");
names.put(3, "Mike");

names.forEach((key, value) -> System.out.println("Key: " + key + " Value: " + value));

for (Map.Entry<Integer, String> entry : names.entrySet()) {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}
    
// Iterating over only keys
for (Integer key : names.keySet()) {
    System.out.println(key);
}
// Iterating over only values
for (String value : names.values()) {
    System.out.println(value);
}

Iterator entries = names.entrySet().iterator();
while (entries.hasNext()) {
    Map.Entry entry = (Map.Entry) entries.next();
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}

Неизменяемые пустые коллекции

Иногда целесообразно использовать неизменяемую пустую коллекцию. Класс Collections предоставляет методы для эффективного сбора таких коллекций:

List<String> anEmptyList = Collections.emptyList();
Map<Integer, Date> anEmptyMap = Collections.emptyMap();
Set<Number> anEmptySet = Collections.emptySet();

Эти методы являются общими и автоматически преобразуют возвращенную коллекцию в тип, которому она назначена. То есть, вызов, например, emptyList() может быть назначен любому типу List а также для emptySet() и emptyMap() .

Коллекции, возвращаемые этими методами, неизменны тем, что они будут вызывать UnsupportedOperationException если вы попытаетесь вызвать методы, которые изменили бы их содержимое ( add , put и т. Д.). Эти коллекции в первую очередь полезны в качестве замены для результатов пустых методов или других значений по умолчанию, вместо того, чтобы использовать null или создавать объекты с new .

Коллекции и примитивные ценности

Коллекции в Java работают только для объектов. Т.е. в Java нет Map<int, int> . Вместо этого примитивные значения должны быть помещены в объекты, как в Map<Integer, Integer> . Java-бокс позволит прозрачному использованию этих коллекций:

Map<Integer, Integer> map = new HashMap<>();
map.put(1, 17); // Automatic boxing of int to Integer objects
int a = map.get(1); // Automatic unboxing.

К сожалению, накладные расходы на это существенны . Для HashMap<Integer, Integer> потребуется около 72 байт на запись (например, на 64-битной JVM со сжатыми указателями и при условии, что целые числа больше 256 и предполагают 50% нагрузки на карту). Поскольку фактические данные составляют всего 8 байтов, это приводит к большим накладным расходам. Кроме того, для этого требуется два уровня косвенности (Map -> Entry -> Value), это излишне медленно.

Существует несколько библиотек с оптимизированными коллекциями для примитивных типов данных (для которых требуется только ~ 16 байт на запись при нагрузке 50%, т.е. на 4 раза меньше памяти и на один уровень косвенности меньше), что может принести значительные преимущества при использовании больших коллекций примитивных значения в Java.

Удаление совпадающих элементов из списков с помощью Iterator.

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

Примечание. Это добавляется только к удалению элементов из списка в примере цикла :

Итак, давайте определим наши списки как обычно

    String[] names = {"James","Smith","Sonny","Huckle","Berry","Finn","Allan"};
    List<String> nameList = new ArrayList<>();

    //Create a List from an Array
    nameList.addAll(Arrays.asList(names));
    
    String[] removeNames = {"Sonny","Huckle","Berry"};
    List<String> removeNameList = new ArrayList<>();

    //Create a List from an Array
    removeNameList.addAll(Arrays.asList(removeNames));

Следующий метод принимает два объекта Collection и выполняет магию удаления элементов в нашем removeNameList которые соответствуют элементам в nameList .

private static void removeNames(Collection<String> collection1, Collection<String> collection2) {
      //get Iterator.
    Iterator<String> iterator = collection1.iterator();
    
    //Loop while collection has items
    while(iterator.hasNext()){
        if (collection2.contains(iterator.next()))
            iterator.remove(); //remove the current Name or Item
    }
}

Вызов метода и передача в nameList и removeNameList следующим образом removeNames(nameList,removeNameList);
Произведет следующий вывод:

Список массивов перед удалением имен: James Smith Sonny Huckle Berry Finn Allan
Список массивов после удаления имен: James Smith Finn Allan

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

Создание собственной структуры Iterable для использования с циклами Iterator или for-each.

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

1. Материал, который мы хотим повторить, должен быть Iterable и выставить iterator() .
2. hasNext() java.util.Iterator , переопределив hasNext() , next() и remove() .

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

package org.algorithms.linkedlist;
 
import java.util.Iterator;
import java.util.NoSuchElementException;
 
 
public class LinkedList<T> implements Iterable<T> {
 
    Node<T> head, current;
 
    private static class Node<T> {
        T data;
        Node<T> next;
 
        Node(T data) {
            this.data = data;
        }
    }
 
    public LinkedList(T data) {
        head = new Node<>(data);
    }
 
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }
 
    private class LinkedListIterator implements Iterator<T> {
 
        Node<T> node = head;
 
        @Override
        public boolean hasNext() {
            return node != null;
        }
 
        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            Node<T> prevNode = node;
            node = node.next;
            return prevNode.data;
        }
 
        @Override
        public void remove() {
            throw new UnsupportedOperationException("Removal logic not implemented.");
        }
    }
 
    public void add(T data) {
        Node current = head;
        while (current.next != null)
            current = current.next;
        current.next = new Node<>(data);
    }
 
}
 
class App {
    public static void main(String[] args) {
 
        LinkedList<Integer> list = new LinkedList<>(1);
        list.add(2);
        list.add(4);
        list.add(3);
 
        //Test #1
        System.out.println("using Iterator:");
        Iterator<Integer> itr = list.iterator();
        while (itr.hasNext()) {
            Integer i = itr.next();
            System.out.print(i + " ");
        }
 
        //Test #2
        System.out.println("\n\nusing for-each:");
        for (Integer data : list) {
            System.out.print(data + " ");
        }
    }
}

Выход

using Iterator:
1 2 4 3
using for-each:
1 2 4 3 

Это будет работать в Java 7+. Вы можете запустить его на Java 5 и Java 6, заменив:

LinkedList<Integer> list = new LinkedList<>(1);

с

LinkedList<Integer> list = new LinkedList<Integer>(1);

или любую другую версию путем включения совместимых изменений.

Pitfall: исключения одновременной модификации

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

List<IHat> hats = new ArrayList<>();
hats.add(new Ushanka()); // that one has ear flaps
hats.add(new Fedora());
hats.add(new Sombrero());
for (IHat hat : hats) {
    if (hat.hasEarFlaps()) {
        hats.remove(hat);
    }
}

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

Подразделы

Список subList (int fromIndex, int toIndex)

Здесь fromIndex включен, а toIndex является эксклюзивным.

List list = new ArrayList(); 
List list1 = list.subList(fromIndex,toIndex); 

1. Если список не существует в диапазоне выдачи, он генерирует IndexOutofBoundException.
2. Все изменения, внесенные в список1, будут влиять на те же изменения в списке. Это называется резервными коллекциями.
3. Если fromnIndex больше, чем toIndex (fromIndex> toIndex), он выдает исключение IllegalArgumentException.

Пример:

List<String> list = new ArrayList<String>();
List<String> list = new ArrayList<String>();
list.add("Hello1"); 
list.add("Hello2"); 
System.out.println("Before Sublist "+list); 
List<String> list2 = list.subList(0, 1);
list2.add("Hello3"); 
System.out.println("After sublist changes "+list); 

Выход:
Перед Sublist [Hello1, Hello2]
После изменений подписок [Hello1, Hello3, Hello2]

Установите subSet (fromIndex, toIndex)

Здесь fromIndex включен, а toIndex является эксклюзивным.

Set set = new TreeSet(); 
Set set1 = set.subSet(fromIndex,toIndex);

Возвращенный набор будет вызывать исключение IllegalArgumentException при попытке вставить элемент за пределы его диапазона.

MapMapMap (fromKey, toKey)

fromKey является инклюзивным, а toKey является эксклюзивным

Map map = new TreeMap();
Map map1 = map.get(fromKey,toKey);

Если fromKey больше, чем toKey, или если сама эта карта имеет ограниченный диапазон, а fromKey или toKey лежит за пределами диапазона, тогда он выдает исключение IllegalArgumentException.

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