Java Language
collezioni

introduzione

Osservazioni

Dichiarazione di una lista di array e aggiunta di oggetti

Possiamo creare un ArrayList (seguendo l'interfaccia List ):

List aListOfFruits = new ArrayList();

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

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

Ora, usa il metodo add per aggiungere una String :

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

Nell'esempio precedente, ArrayList conterrà la String "Melon" nell'indice 0 e la String "Strawberry" nell'indice 1.

Inoltre possiamo aggiungere più elementi con il addAll(Collection<? extends E> c)

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

Ora "Onion" è posto a 0 indice in aListOfFruitsAndVeggies , "Melon" è nell'indice 1 e "Strawberry" è nell'indice 2.

Costruire collezioni da dati esistenti

Collezioni standard

Quadro di collezioni Java

Un modo semplice per costruire un List dai singoli valori di dati è utilizzare il metodo java.utils.Arrays Arrays.asList :

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

Tutte le implementazioni di raccolta standard forniscono costruttori che accettano un'altra raccolta come argomento aggiungendo tutti gli elementi alla nuova raccolta al momento della costruzione:

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

Framework Google Guava Collections

Un altro grande quadro è Google Guava che è straordinaria classe di utilità (fornisce metodi statici di convenienza) per la costruzione di diversi tipi di collezioni standard di Lists e 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");

Raccolta di mappe

Quadro di collezioni Java

Allo stesso modo per le mappe, data una Map<String, Object> map una nuova mappa può essere costruita con tutti gli elementi come segue:

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

Quadro delle collezioni Apache Commons

Usando Apache Commons puoi creare una mappa usando una matrice in ArrayUtils.toMap e 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"}});

Ogni elemento dell'array deve essere un Map.Entry o una Array, contenente almeno due elementi, in cui il primo elemento viene utilizzato come chiave e il secondo come valore.

Framework Google Guava Collections

La classe di utilità del framework Google Guava si chiama 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());

Iscriviti alle liste

I seguenti modi possono essere utilizzati per unire gli elenchi senza modificare la / e lista / i di origine.

Primo approccio Ha più linee ma è facile da capire

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

Secondo approccio Ha una linea in meno ma meno leggibile.

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

Terzo approccio. Richiede libreria di raccolta di risorse di Apache di terze parti.

ListUtils.union(listOne,listTwo);

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

Riferimenti. Elenco delle interfacce

Rimozione di elementi da un elenco all'interno di un ciclo

È difficile rimuovere gli elementi da un elenco mentre si è all'interno di un ciclo, ciò è dovuto al fatto che l'indice e la lunghezza dell'elenco vengono modificati.

Dato il seguente elenco, ecco alcuni esempi che daranno un risultato inaspettato e alcuni che daranno il risultato corretto.

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

NON CORRETTO

La rimozione di iterazione for dichiarazione Salta "Banana":

L'esempio di codice stampa solo Apple e Strawberry . Banana viene saltato perché si muove all'indice 0 , una volta Apple viene eliminato, ma allo stesso tempo i viene incrementato di 1 .

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

Rimozione nella maggiore for dichiarazione genera un'eccezione:

A causa dell'iterazione della raccolta e della modifica allo stesso tempo.

Lanci: java.util.ConcurrentModificationException

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

CORRETTA

Rimozione durante il ciclo usando un Iterator

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

L'interfaccia Iterator ha un metodo remove() costruito solo per questo caso. Tuttavia, questo metodo è contrassegnato come "facoltativo" nella documentazione e potrebbe generare un UnsupportedOperationException .

Genera: UnsupportedOperationException - se l'operazione di rimozione non è supportata da questo iteratore

Pertanto, è consigliabile controllare la documentazione per assicurarsi che questa operazione sia supportata (in pratica, a meno che la raccolta non sia immutabile ottenuta attraverso una libreria di terze parti o l'uso di uno dei metodi Collections.unmodifiable...() , l'operazione è quasi sempre supportata).

Durante l'utilizzo di Iterator viene generata modCount ConcurrentModificationException quando viene modificato il modCount List da quando è stato creato Iterator . Questo potrebbe essere accaduto nella stessa discussione o in un'applicazione multithreading che condividesse la stessa lista.

Un modCount è una variabile int che conta il numero di volte in cui questo elenco è stato modificato strutturalmente. Una modifica strutturale significa essenzialmente un'operazione add() o remove() invocata sull'oggetto Collection (le modifiche apportate da Iterator non vengono conteggiate). Quando viene creato l' Iterator , memorizza questo modCount e ad ogni iterazione List controlla se il modCount corrente è uguale a quando è stato creato l' Iterator . Se c'è una modifica nel valore modCount , lancia una ConcurrentModificationException .

Quindi per la lista sopra dichiarata, un'operazione come sotto non genererà alcuna eccezione:

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

Ma aggiungendo un nuovo elemento alla List dopo aver inizializzato un Iterator verrà Iterator una ConcurrentModificationException :

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

Iterazione all'indietro

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

Questo non salta nulla. Lo svantaggio di questo approccio è che l'output è invertito. Tuttavia, nella maggior parte dei casi, rimuovi gli articoli che non contano. Non dovresti mai farlo con LinkedList .

Iterazione in avanti, regolazione dell'indice del loop

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

Questo non salta nulla. Quando l' i -esimo elemento viene rimosso dalla List , l'elemento originariamente posizionato in corrispondenza dell'indice i+1 diventa il nuovo i -esimo elemento. Pertanto, il ciclo può decrementare i in modo che l'iterazione successiva elabori l'elemento successivo, senza saltare.

Utilizzando una lista "dovrebbe-essere-rimosso"

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

Questa soluzione consente allo sviluppatore di verificare se gli elementi corretti vengono rimossi in modo più pulito.

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

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

Collezione non modificabile

A volte non è una buona pratica esporre una raccolta interna in quanto può portare a una vulnerabilità di codice dannoso a causa della sua caratteristica mutevole. Per fornire raccolte "di sola lettura", java fornisce le sue versioni non modificabili.

Una collezione non modificabile è spesso una copia di una collezione modificabile che garantisce che la collezione stessa non può essere alterata. I tentativi di modificarlo generano un'eccezione UnsupportedOperationException.

È importante notare che gli oggetti presenti all'interno della collezione possono ancora essere modificati.

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

Il seguente tentativo di modificare una collezione non modificabile genererà un'eccezione:

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

produzione:

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

Iterating over Collections

Iterare sulla lista

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

Iterating over Set

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

Iterazione sulla mappa

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

Collezioni immutabili vuote

A volte è opportuno utilizzare una collezione vuota immutabile. La classe Collections fornisce metodi per ottenere tali raccolte in modo efficiente:

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

Questi metodi sono generici e convertiranno automaticamente la raccolta restituita nel tipo a cui è assegnata. Cioè, una emptyList() ad esempio emptyList() può essere assegnata a qualsiasi tipo di List e allo stesso modo per emptySet() e emptyMap() .

Le raccolte restituite da questi metodi sono immutabili in quanto generano UnsupportedOperationException se si tenta di chiamare metodi che potrebbero cambiare il loro contenuto ( add , put , ecc.). Queste raccolte sono principalmente utili come sostituti per i risultati del metodo vuoto o altri valori predefiniti, invece di utilizzare null o creare oggetti con new .

Collezioni e valori primitivi

Le raccolte in Java funzionano solo per gli oggetti. Cioè non c'è Map<int, int> in Java. Invece, i valori primitivi devono essere racchiusi negli oggetti, come in Map<Integer, Integer> . L'auto-boxing Java abiliterà l'uso trasparente di queste raccolte:

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

Sfortunatamente, il sovraccarico di questo è sostanziale . Una HashMap<Integer, Integer> richiederà circa 72 byte per voce (es. Su JVM a 64 bit con puntatori compressi e assumendo numeri interi maggiori di 256 e assumendo il 50% di carico della mappa). Poiché i dati effettivi sono solo 8 byte, questo genera un sovraccarico enorme. Inoltre, richiede due livelli di riferimento indiretto (Mappa -> Voce -> Valore) è inutilmente lento.

Esistono diverse librerie con raccolte ottimizzate per tipi di dati primitivi (che richiedono solo ~ 16 byte per voce con il 50% di carico, ovvero 4x meno memoria, e un livello di riferimento indiretto inferiore), che possono produrre notevoli vantaggi in termini di prestazioni quando si utilizzano grandi collezioni di primitive valori in Java.

Rimozione degli elementi corrispondenti dagli elenchi utilizzando Iterator.

Sopra ho notato un esempio per rimuovere elementi da una lista all'interno di un loop e ho pensato ad un altro esempio che potrebbe tornare utile questa volta usando l'interfaccia di Iterator .
Questa è una dimostrazione di un trucco che potrebbe rivelarsi utile quando si ha a che fare con articoli duplicati negli elenchi di cui si vuole sbarazzarsi.

Nota: questa operazione si aggiunge solo alla rimozione di elementi da un elenco all'interno di un esempio di ciclo :

Quindi definiamo i nostri elenchi come al solito

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

Il seguente metodo prende in due oggetti Collection ed esegue la magia di rimuovere gli elementi nel nostro removeNameList che corrispondono agli elementi in 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
    }
}

Chiamando il metodo e passando il nameList e il removeNameList come segue removeNames(nameList,removeNameList);
Produrrà il seguente risultato:

Elenco di matrici prima di rimuovere i nomi: James Smith Sonny Huckle Berry Finn Allan
Elenco di matrici dopo aver rimosso i nomi: James Smith Finn Allan

Un uso semplice e intuitivo per le raccolte che può rivelarsi utile per rimuovere elementi ripetitivi all'interno degli elenchi.

Creazione della propria struttura Iterable da utilizzare con Iterator o for-each loop.

Per garantire che la nostra raccolta possa essere iterata utilizzando iteratore o ciclo per-one, dobbiamo occuparci dei seguenti passaggi:

1. Le cose che vogliamo iterare devono essere Iterable ed esporre iterator() .
2. Progettare un java.util.Iterator hasNext() override di hasNext() , next() e remove() .

Ho aggiunto una semplice implementazione di liste collegate generiche sotto che utilizza le entità sopra per rendere iterabile l'elenco collegato.

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

Produzione

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

Questo verrà eseguito in Java 7+. Puoi farlo girare su Java 5 e Java 6 anche sostituendo:

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

con

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

o semplicemente qualsiasi altra versione incorporando le modifiche compatibili.

Trappola: eccezioni di modifica simultanea

Questa eccezione si verifica quando una raccolta viene modificata mentre viene iterata su metodi diversi da quelli forniti dall'oggetto iteratore. Ad esempio, abbiamo un elenco di cappelli e vogliamo rimuovere tutti quelli che hanno i padiglioni auricolari:

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

Se eseguiamo questo codice, ConcurrentModificationException verrà generato poiché il codice modifica la raccolta durante l'iterazione. La stessa eccezione può verificarsi se uno dei thread multipli che lavorano con lo stesso elenco sta provando a modificare la raccolta mentre altri lo iterano su di esso. La modifica simultanea di raccolte in più thread è una cosa naturale, ma dovrebbe essere trattata con gli strumenti usuali della toolbox di programmazione simultanea come i blocchi di sincronizzazione, le raccolte speciali adottate per la modifica simultanea, la modifica della raccolta clonata dall'iniziale ecc.

Collezioni secondarie

List subList (int fromIndex, int toIndex)

Qui fromIndex è inclusivo e toIndex è esclusivo.

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

1. Se l'elenco non esiste nell'intervallo give, genera IndexOutofBoundException.
2. Qualsiasi modifica apportata alla lista1 avrà conseguenze sulle stesse modifiche nella lista. Si tratta di raccolte supportate.
3. Se fromnIndex è maggiore di toIndex (fromIndex> toIndex) genera IllegalArgumentException.

Esempio:

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

Produzione:
Prima della sottolista [Hello1, Hello2]
Dopo le modifiche di sottolista [Hello1, Hello3, Hello2]

Imposta sottoset (daIndex, aIndex)

Qui fromIndex è inclusivo e toIndex è esclusivo.

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

Il set restituito genererà un IllegalArgumentException nel tentativo di inserire un elemento al di fuori del suo intervallo.

Mappa sottocappa (daKey, toKey)

fromKey è inclusivo e toKey è esclusivo

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

Se fromKey è maggiore di toKey o se questa mappa ha un intervallo limitato e fromKey o toKey si trova al di fuori dei limiti dell'intervallo, genera IllegalArgumentException.

Tutte le raccolte supportano le raccolte di spalle, le modifiche apportate alla sotto collezione avranno lo stesso cambiamento nella raccolta principale.