Java Language
Kolekcje

Wprowadzenie

Uwagi

Deklarowanie ArrayList i dodawanie obiektów

Możemy utworzyć ArrayList (zgodnie z interfejsem List ):

List aListOfFruits = new ArrayList();

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

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

Teraz użyj metody add aby dodać String :

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

W powyższym przykładzie ArrayList będzie zawierać String „Melon” o indeksie 0 i String „Strawberry” o indeksie 1.

Możemy również dodawać wiele elementów za pomocą addAll(Collection<? extends E> c)

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

Teraz „Cebula” znajduje się w indeksie 0 w aListOfFruitsAndVeggies , „Melon” ma indeks 1, a „Truskawka” w indeksie 2.

Konstruowanie kolekcji na podstawie istniejących danych

Kolekcje standardowe

Framework kolekcji Java

Prostym sposobem na zbudowanie List z indywidualnych wartości danych jest użycie metody java.utils.Arrays Arrays.asList :

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

Wszystkie standardowe implementacje kolekcji zapewniają konstruktory, które przyjmują inną kolekcję jako argument dodający wszystkie elementy do nowej kolekcji w momencie budowy:

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

Ramy kolekcji Google Guava

Innym świetnym szkieletem jest Google Guava która jest niesamowitą klasą użyteczności (zapewniającą wygodne metody statyczne) do budowy różnych typów standardowych kolekcji Lists i 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");

Mapowanie kolekcji

Framework kolekcji Java

Podobnie w przypadku map, biorąc pod uwagę Map<String, Object> map można zbudować nową mapę ze wszystkimi elementami w następujący sposób:

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

Ramy kolekcji Apache Commons

Korzystając z Apache Commons , możesz utworzyć mapę za pomocą tablicy w ArrayUtils.toMap oraz 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"}});

Każdy element tablicy musi być Map.Entry lub Array, zawierający co najmniej dwa elementy, przy czym pierwszy element jest używany jako klucz, a drugi jako wartość.

Ramy kolekcji Google Guava

Klasa użyteczności z Google Guava Framework nosi nazwę 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());

Dołącz do list

Do łączenia list można używać następujących sposobów bez modyfikowania list źródłowych.

Pierwsze podejście Ma więcej linii, ale jest łatwy do zrozumienia

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

Drugie podejście. Ma jedną linię mniej, ale mniej czytelną.

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

Trzecie podejście. Wymaga biblioteki zbiorów wspólnych Apache innej firmy.

ListUtils.union(listOne,listTwo);

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

Bibliografia. Lista interfejsów

Usuwanie elementów z listy w pętli

Usunięcie elementów z listy w pętli jest trudne, ponieważ wynika to ze zmiany indeksu i długości listy.

Biorąc pod uwagę poniższą listę, oto kilka przykładów, które dadzą nieoczekiwany wynik, a niektóre dadzą poprawny wynik.

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

BŁĘDNY

Usuwanie w iteracji for oświadczenia Pomiń „Banan”:

Próbka kodu wydrukuje tylko Apple i Strawberry . Banana jest pomijany, gdyż przenosi się do indeksu 0 raz Apple zostanie usunięty, ale w tym samym czasie i zostanie zwiększona do 1 .

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

Usuwanie w zwiększona for rachunku Zgłasza wyjątek:

Z powodu iteracji nad kolekcją i modyfikowania jej w tym samym czasie.

Zgłasza: java.util.ConcurrentModificationException

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

POPRAWNY

Usuwanie pętli while za pomocą Iterator

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

Interfejs Iterator ma wbudowaną metodę remove() właśnie dla tego przypadku. Jednak ta metoda jest oznaczona jako „opcjonalna” w dokumentacji i może UnsupportedOperationException .

Zgłasza: UnsupportedOperationException - jeśli operacja usuwania nie jest obsługiwana przez ten iterator

Dlatego zaleca się sprawdzenie dokumentacji, aby upewnić się, że ta operacja jest obsługiwana (w praktyce, chyba że kolekcja jest niezmienna, uzyskana za pomocą biblioteki innej firmy lub przy użyciu jednej z metod Collections.unmodifiable...() , operacja jest prawie zawsze obsługiwana).

Podczas korzystania z Iterator modCount jest modCount ConcurrentModificationException gdy modCount List jest zmieniany od momentu utworzenia Iterator . Mogło się to zdarzyć w tym samym wątku lub w aplikacji wielowątkowej współdzielącej tę samą listę.

modCount jest zmienną int , która zlicza liczbę modyfikacji struktury tej listy. Zmiana strukturalna zasadniczo oznacza wywołanie operacji add() lub remove() na obiekcie Collection (zmiany dokonane przez Iterator nie są liczone). Kiedy Iterator jest tworzony, przechowuje to modCount i przy każdej iteracji List sprawdza, czy bieżący modCount jest taki sam jak i kiedy Iterator został utworzony. W przypadku zmiany wartości modCount zgłasza modCount ConcurrentModificationException .

Dlatego dla wyżej zadeklarowanej listy operacja taka jak poniżej nie zgłosi żadnego wyjątku:

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

Ale dodanie nowego elementu do List po zainicjowaniu Iterator spowoduje zgłoszenie Iterator ConcurrentModificationException :

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

Iteracja do tyłu

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

To niczego nie pomija. Wadą tego podejścia jest odwrotność wyników. Jednak w większości przypadków, gdy usuwasz elementy, które nie będą miały znaczenia. Nigdy nie powinieneś tego robić z LinkedList .

Iteracja do przodu, regulacja indeksu pętli

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

To niczego nie pomija. Po usunięciu i tego elementu z List element pierwotnie umieszczony w indeksie i+1 staje się nowym i tym elementem. Dlatego pętla może zmniejszać i , aby następna iteracja przetworzyła następny element bez pomijania.

Korzystanie z listy „należy usunąć”

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

To rozwiązanie umożliwia programistom sprawdzenie, czy poprawne elementy zostały usunięte w czystszy sposób.

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

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

Kolekcja niemodyfikowalna

Czasami nie jest dobrą praktyką ujawnianie wewnętrznej kolekcji, ponieważ może prowadzić do podatności na złośliwy kod ze względu na jego zmienną charakterystykę. Aby zapewnić kolekcje „tylko do odczytu”, Java zapewnia swoje niezmodyfikowane wersje.

Kolekcja niemodyfikowalna jest często kopią kolekcji modyfikowalnej, która gwarantuje, że sama kolekcja nie może zostać zmieniona. Próby jego modyfikacji spowodują wyjątek UnsupportedOperationException.

Należy zauważyć, że obiekty znajdujące się w kolekcji można nadal zmieniać.

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);
    }
}

Następująca próba zmodyfikowania niemodyfikowalnej kolekcji spowoduje zgłoszenie wyjątku:

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);
    }
}

wynik:

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

Iterowanie po kolekcjach

Iterowanie po liście

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());
}

Iterowanie po zestawie

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());
}

Iterowanie po mapie

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());
}

Niezmienne puste kolekcje

Czasami właściwe jest użycie niezmiennej pustej kolekcji. Klasa Collections zapewnia metody skutecznego pozyskiwania takich kolekcji:

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

Te metody są ogólne i automatycznie przekonwertują zwróconą kolekcję na typ, do którego została przypisana. Oznacza to, że wywołanie np. emptyList() może być przypisane do dowolnego typu List i podobnie dla emptySet() i emptyMap() .

Kolekcje zwrócone tymi metodami są niezmienne, ponieważ UnsupportedOperationException jeśli spróbujesz wywołać metody, które zmieniłyby ich zawartość ( add , put itp.). Te kolekcje są przede wszystkim przydatne jako substytuty pustych wyników metod lub innych wartości domyślnych, zamiast używania null lub tworzenia obiektów z new .

Kolekcje i pierwotne wartości

Kolekcje w Javie działają tylko dla obiektów. Tj. W Javie nie ma Map<int, int> . Zamiast tego prymitywne wartości muszą być spakowane w obiekty, jak w Map<Integer, Integer> . Automatyczne boxowanie w Javie umożliwi transparentne korzystanie z tych kolekcji:

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

Niestety koszty tego są znaczne . HashMap<Integer, Integer> wymaga około 72 bajtów na wpis (np. W 64-bitowej JVM ze skompresowanymi wskaźnikami i zakładając liczby całkowite większe niż 256 i zakładając 50% obciążenia mapy). Ponieważ rzeczywiste dane mają tylko 8 bajtów, powoduje to ogromne obciążenie. Ponadto wymaga dwóch poziomów pośrednich (Mapa -> Wejście -> Wartość), jest niepotrzebnie powolny.

Istnieje kilka bibliotek ze zoptymalizowanymi kolekcjami dla prymitywnych typów danych (które wymagają tylko ~ 16 bajtów na wpis przy 50% obciążeniu, tj. 4x mniej pamięci i jeden poziom mniejszego pośrednictwa), które mogą przynieść znaczne korzyści wydajnościowe przy użyciu dużych kolekcji prymitywów wartości w Javie.

Usuwanie pasujących elementów z list za pomocą Iteratora.

Powyżej zauważyłem przykład usuwania elementów z listy w pętli i pomyślałem o innym przykładzie, który może się przydać tym razem przy użyciu interfejsu Iterator .
Jest to pokaz sztuczki, która może się przydać w przypadku zduplikowanych pozycji na listach, których chcesz się pozbyć.

Uwaga: dodaje się to tylko do usuwania elementów z listy w przykładzie pętli :

Zdefiniujmy więc nasze listy jak zwykle

    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));

Poniższa metoda pobiera dwa obiekty Collection i wykonuje magię usuwania elementów w naszej removeNameList które pasują do elementów w 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
    }
}

Wywołanie metody i przekazanie nameList i removeNameList w następujący sposób removeNames(nameList,removeNameList);
Wytworzy następujące dane wyjściowe:

Lista tablic przed usunięciem nazwisk: James Smith Sonny Huckle Berry Finn Allan
Lista tablic po usunięciu nazwisk: James Smith Finn Allan

Proste, zgrabne zastosowanie dla kolekcji, które mogą się przydać do usuwania powtarzających się elementów z list.

Tworzenie własnej struktury Iterable do użytku z Iteratorem lub dla każdej pętli.

Aby mieć możliwość iteracji naszej kolekcji za pomocą iteratora lub pętli dla każdej z nich, musimy wykonać następujące kroki:

1. Rzeczy, na których chcemy się powtarzać, muszą być Iterable i ujawniać iterator() .
2. Zaprojektuj java.util.Iterator , zastępując hasNext() , next() i remove() .

Dodałem poniżej prostą ogólną implementację listy połączonej, która wykorzystuje powyższe jednostki, aby umożliwić iterację listy połączonej.

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 + " ");
        }
    }
}

Wynik

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

To będzie działać w Javie 7+. Możesz sprawić, że będzie działał na Javie 5 i Javie 6 również przez podstawienie:

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

z

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

lub po prostu inną wersję, wprowadzając zgodne zmiany.

Pitfall: wyjątki dotyczące jednoczesnych modyfikacji

Ten wyjątek występuje, gdy kolekcja jest modyfikowana podczas iteracji nad nią przy użyciu metod innych niż te udostępnione przez obiekt iteratora. Na przykład mamy listę czapek i chcemy usunąć wszystkie te, które mają nauszniki:

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);
    }
}

Jeśli uruchomimy ten kod, ConcurrentModificationException zostanie zgłoszony, ponieważ kod modyfikuje kolekcję podczas iteracji. Ten sam wyjątek może wystąpić, jeśli jeden z wielu wątków pracujących z tą samą listą próbuje zmodyfikować kolekcję, podczas gdy inne iterują nad nią. Jednoczesna modyfikacja kolekcji w wielu wątkach jest czymś naturalnym, ale należy ją traktować zwykłymi narzędziami z równoległego zestawu narzędzi programistycznych, takimi jak blokady synchronizacji, specjalne kolekcje przyjęte do jednoczesnej modyfikacji, modyfikacja sklonowanej kolekcji od początkowej itp.

Kolekcje podrzędne

List subList (int fromIndex, int toIndex)

Tutaj fromIndex jest wyłączny, a toIndex jest wyłączny.

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

1. Jeśli lista nie istnieje w podanym zakresie, zgłasza wyjątek IndexOutofBoundException.
2. Wszelkie zmiany dokonane na liście1 wpłyną na te same zmiany na liście. Nazywa się to kolekcjami kopii zapasowych.
3. Jeśli fromnIndex jest większy niż toIndex (fromIndex> toIndex), zgłasza wyjątek IllegalArgumentException.

Przykład:

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); 

Wynik:
Przed podlistą [Hello1, Hello2]
Po zmianie listy podrzędnej [Hello1, Hello3, Hello2]

Ustaw subSet (fromIndex, toIndex)

Tutaj fromIndex jest wyłączny, a toIndex jest wyłączny.

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

Zwrócony zestaw zgłosi wyjątek IllegalArgumentException przy próbie wstawienia elementu poza jego zasięg.

Mapa SubMap (fromKey, toKey)

fromKey jest wyłączny, a toKey jest wyłączny

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

Jeśli fromKey jest większy niż toKey lub jeśli sama mapa ma ograniczony zasięg, a fromKey lub toKey leży poza granicami zakresu, wówczas zgłasza wyjątek IllegalArgumentException.

Wszystkie kolekcje obsługują kolekcje wspierane, co oznacza, że zmiany wprowadzone w kolekcji podrzędnej będą miały tę samą zmianę w kolekcji głównej.