Java Language
collecties

Invoering

Opmerkingen

Een ArrayList declareren en objecten toevoegen

We kunnen een maken ArrayList (naar aanleiding van de List interface):

List aListOfFruits = new ArrayList();

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

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

Gebruik nu de methode add om een String add te voegen:

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

In het bovenstaande voorbeeld bevat de ArrayList de String "Meloen" op index 0 en de String "Aardbei" op index 1.

We kunnen ook meerdere elementen toevoegen met de addAll(Collection<? extends E> c)

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

Nu wordt "Ui" op index 0 geplaatst in aListOfFruitsAndVeggies , staat "Meloen" op index 1 en "Aardbei" op index 2.

Collecties samenstellen op basis van bestaande gegevens

Standaard collecties

Java Collections-framework

Een eenvoudige manier om een List van individuele gegevenswaarden is door java.utils.Arrays methode Arrays.asList :

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

Alle standaardcollectie-implementaties bieden constructeurs die een andere collectie als argument nemen en alle elementen aan de nieuwe collectie toevoegen op het moment van constructie:

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 Collections-framework

Een ander geweldig raamwerk is Google Guava dat een verbluffende utility-klasse is (die handige statische methoden biedt) voor de bouw van verschillende soorten standaardcollecties Lists en 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");

Collecties in kaart brengen

Java Collections-framework

Op dezelfde manier kan voor kaarten, gegeven een Map<String, Object> map een nieuwe map worden samengesteld met alle elementen als volgt:

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

Framework van Apache Commons Collections

Met behulp van Apache Commons kunt u Map maken met behulp van array in ArrayUtils.toMap en 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"}});

Elk element van de array moet een Map.Entry of een Array zijn, die ten minste twee elementen bevat, waarbij het eerste element als sleutel en het tweede als waarde wordt gebruikt.

Google Guava Collections-framework

Hulpprogramma klasse van Google Guava framework heet 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());

Deelnemen aan lijsten

De volgende manieren kunnen worden gebruikt voor het samenvoegen van lijsten zonder de bronlijst (en) te wijzigen.

Eerste aanpak. Heeft meer regels maar is gemakkelijk te begrijpen

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

Tweede benadering. Heeft een regel minder maar minder leesbaar.

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

Derde benadering. Vereist bibliotheek van Apache Commons-collecties .

ListUtils.union(listOne,listTwo);

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

Referenties. Interfacelijst

Items uit een lijst binnen een lus verwijderen

Het is lastig om items uit een lijst te verwijderen in een lus, dit komt omdat de index en de lengte van de lijst worden gewijzigd.

Op basis van de volgende lijst zijn hier enkele voorbeelden die een onverwacht resultaat geven en enkele die het juiste resultaat geven.

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

NIET CORRECT

Verwijderen in iteratie van for instructie Skips "Banana":

In het codevoorbeeld worden alleen Apple en Strawberry afgedrukt. Banana wordt overgeslagen, omdat het beweegt naar de index 0 zodra Apple is verwijderd, maar tegelijkertijd i wordt verhoogd naar 1 .

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

Verwijderen van de verbeterde for instructie Throws Exception:

Vanwege het herhaaldelijk overnemen en tegelijkertijd wijzigen ervan.

Gooit: java.util.ConcurrentModificationException

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

CORRECT

Verwijderen terwijl lus met behulp van een Iterator

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

De Iterator interface heeft een methode remove() die speciaal voor dit geval is ingebouwd. Deze methode is echter gemarkeerd als "optioneel" in de documentatie en kan een UnsupportedOperationException .

Gooit: UnsupportedOperationException - als de verwijderbewerking niet door deze iterator wordt ondersteund

Daarom is het raadzaam om de documentatie te controleren om te controleren of deze bewerking wordt ondersteund (in de praktijk, tenzij de verzameling onveranderlijk is, verkregen via een externe bibliotheek of het gebruik van een van de methode Collections.unmodifiable...() , de bewerking wordt bijna altijd ondersteund).

Tijdens het gebruik van een Iterator een ConcurrentModificationException gegenereerd wanneer de modCount van de List wordt gewijzigd vanaf het moment dat de Iterator werd gemaakt. Dit kan zijn gebeurd in dezelfde thread of in een app met meerdere threads die dezelfde lijst delen.

Een modCount is een int variabele die het aantal keren telt dat deze lijst structureel is gewijzigd. Een structurele wijziging betekent in wezen een bewerking add() of remove() die wordt aangeroepen op het Collection object (wijzigingen die door Iterator zijn aangebracht, worden niet geteld). Wanneer de Iterator wordt gemaakt, wordt deze modCount en wordt bij elke iteratie van de List gecontroleerd of de huidige modCount hetzelfde is als en wanneer de Iterator is gemaakt. Als er een wijziging is in de waarde modCount , wordt er een ConcurrentModificationException modCount .

Vandaar dat voor de hierboven genoemde lijst een bewerking zoals hieronder geen uitzondering oplevert:

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

Maar het toevoegen van een nieuw element aan de List na het initialiseren van een Iterator een ConcurrentModificationException :

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

Achterwaarts draaien

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

Dit slaat niets over. Het nadeel van deze benadering is dat de uitvoer omgekeerd is. In de meeste gevallen verwijdert u echter items die er niet toe doen. Doe dit nooit met LinkedList .

Vooruitspoelen, de lusindex aanpassen

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

Dit slaat niets over. Wanneer het i de element uit de List wordt verwijderd, wordt het element dat oorspronkelijk op index i+1 is geplaatst, het nieuwe i de element. Daarom kan de lus i verlagen om voor de volgende iteratie het volgende element te verwerken, zonder over te slaan.

Gebruik een "moet-worden-verwijderd" lijst

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

Met deze oplossing kan de ontwikkelaar controleren of de juiste elementen op een schonere manier zijn verwijderd.

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

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

Onaanpasbare verzameling

Soms is het geen goede gewoonte om een interne verzameling bloot te leggen, omdat het kan leiden tot kwetsbaarheid van schadelijke code vanwege het veranderlijke kenmerk. Om 'alleen-lezen'-collecties te bieden, biedt java zijn onaanpasbare versies.

Een niet-wijzigbare verzameling is vaak een kopie van een wijzigbare verzameling die garandeert dat de verzameling zelf niet kan worden gewijzigd. Pogingen om het te wijzigen, resulteren in een uitzondering UnsupportedOperationException.

Het is belangrijk op te merken dat objecten die aanwezig zijn in de collectie nog steeds kunnen worden gewijzigd.

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

De volgende poging om een niet-wijzigbare verzameling te wijzigen, zal een uitzondering veroorzaken:

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

output:

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

Herhalen over collecties

Herhalen over lijst

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

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

Herhalen over kaart

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

Onveranderlijke lege collecties

Soms is het gepast om een onveranderlijke lege verzameling te gebruiken. De klasse Collections biedt methoden om dergelijke collecties op een efficiënte manier te krijgen:

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

Deze methoden zijn generiek en zullen de geretourneerde verzameling automatisch omzetten in het type waaraan deze is toegewezen. Dat wil zeggen dat een aanroep van bijv. emptyList() kan worden toegewezen aan elk type List en evenzo voor emptySet() en emptyMap() .

De collecties die door deze methoden worden geretourneerd, zijn onveranderlijk omdat ze UnsupportedOperationException als u methoden probeert aan te roepen die de inhoud ervan zouden wijzigen ( add , put , enz.). Deze collecties zijn vooral nuttig als vervanging voor resultaten van de lege methode of andere standaardwaarden, in plaats van null of objecten met new .

Collecties en primitieve waarden

Collecties in Java werken alleen voor objecten. Dat wil zeggen, er is geen Map<int, int> in Java. In plaats daarvan moeten primitieve waarden in objecten worden ingepakt , zoals in Map<Integer, Integer> . Java auto-boxing maakt transparant gebruik van deze collecties mogelijk:

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

Helaas is de overhead hiervan aanzienlijk . Een HashMap<Integer, Integer> vereist ongeveer 72 bytes per invoer (bijv. Op 64-bit JVM met gecomprimeerde pointers, en uitgaande van gehele getallen groter dan 256, en uitgaande van 50% belasting van de kaart). Omdat de feitelijke gegevens slechts 8 bytes zijn, levert dit een enorme overhead op. Bovendien vereist het twee niveaus van richting (Kaart -> Invoer -> Waarde) en is het onnodig langzaam.

Er bestaan verschillende bibliotheken met geoptimaliseerde collecties voor primitieve gegevenstypen (die slechts ~ 16 bytes per invoer vereisen bij 50% belasting, dwz 4x minder geheugen en één indirectionniveau minder), die aanzienlijke prestatiesvoordelen kunnen opleveren bij het gebruik van grote collecties primitieve waarden in Java.

Overeenkomende items uit lijsten verwijderen met Iterator.

Hierboven zag ik een voorbeeld om items uit een lijst binnen een lus te verwijderen en ik dacht aan een ander voorbeeld dat dit keer van pas kan komen met de Iterator interface.
Dit is een demonstratie van een truc die van pas kan komen bij het omgaan met dubbele items in lijsten die u wilt verwijderen.

Opmerking: dit wordt alleen toegevoegd aan het verwijderen van items uit een lijst in een lusvoorbeeld :

Laten we dus onze lijsten zoals gebruikelijk definiëren

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

De volgende methode neemt twee Collection-objecten en voert de magie uit van het verwijderen van de elementen in onze removeNameList die overeenkomen met elementen 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
    }
}

Het aanroepen van de methode en het doorgeven van de nameList en de removeNameList als volgt removeNames(nameList,removeNameList);
Zal de volgende uitvoer produceren:

Matrixlijst voordat namen worden verwijderd: James Smith Sonny Huckle Berry Finn Allan
Matrixlijst na het verwijderen van namen: James Smith Finn Allan

Een eenvoudig netjes gebruik voor collecties die van pas kan komen om herhalende elementen in lijsten te verwijderen.

Uw eigen Iterable-structuur maken voor gebruik met Iterator of voor elke lus.

Om ervoor te zorgen dat onze collectie kan worden herhaald met behulp van iterator of voor elke lus, moeten we de volgende stappen nemen:

1. De dingen die we willen herhalen, moeten Iterable en iterator() .
2. Ontwerp een java.util.Iterator door hasNext() , next() en remove() .

Ik heb hieronder een eenvoudige generieke gekoppelde lijstimplementatie toegevoegd die bovenstaande entiteiten gebruikt om de gekoppelde lijst iterabel te maken.

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

uitgang

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

Dit wordt uitgevoerd in Java 7+. Je kunt het ook laten draaien op Java 5 en Java 6 door het volgende te vervangen:

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

met

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

of gewoon een andere versie door de compatibele wijzigingen op te nemen.

Valkuil: uitzonderingen voor gelijktijdige wijziging

Deze uitzondering treedt op wanneer een verzameling wordt gewijzigd terwijl deze wordt herhaald met behulp van andere methoden dan die worden aangeboden door het iterator-object. We hebben bijvoorbeeld een lijst met hoeden en we willen al die hoeden met oorkleppen verwijderen:

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

Als we deze code uitvoeren, wordt ConcurrentModificationException verhoogd, omdat de code de verzameling wijzigt en itereert. Dezelfde uitzondering kan optreden als een van de meerdere threads die met dezelfde lijst werken, probeert de verzameling te wijzigen terwijl anderen erover doorgaan. Gelijktijdige wijziging van verzamelingen in meerdere threads is een vanzelfsprekendheid, maar moet worden behandeld met gebruikelijke tools van de toolbox voor gelijktijdig programmeren, zoals synchronisatiesloten, speciale verzamelingen die zijn aangenomen voor gelijktijdige wijziging, het wijzigen van de gekloonde verzameling vanaf de initiële enz.

Subcollecties

Sublijst weergeven (int fromIndex, int toIndex)

Hier is fromIndex inclusief en toIndex is exclusief.

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

1. Als de lijst niet in het geefbereik bestaat, wordt IndexOutofBoundException gegenereerd.
2. Alle wijzigingen die ooit op de lijst1 zijn aangebracht, hebben invloed op dezelfde wijzigingen in de lijst. Dit worden verzamelde collecties genoemd.
3. Als de fromnIndex groter is dan de toIndex (fromIndex> toIndex), wordt IllegalArgumentException gegenereerd.

Voorbeeld:

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

Output:
Voor sublijst [Hallo1, Hallo2]
Na wijzigingen in de sublijst [Hello1, Hello3, Hello2]

SubSet instellen (vanIndex, naarIndex)

Hier is fromIndex inclusief en toIndex is exclusief.

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

De geretourneerde set genereert een IllegalArgumentException bij een poging om een element buiten zijn bereik in te voegen.

Map subMap (fromKey, toKey)

fromKey is inclusief en toKey is exclusief

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

Als fromKey groter is dan toKey of als deze map zelf een beperkt bereik heeft en fromKey of toKey buiten de grenzen van het bereik ligt, wordt IllegalArgumentException gegenereerd.

Alle collecties ondersteunen collecties met back-up, wat betekent dat wijzigingen in de subcollectie dezelfde wijziging hebben in de hoofdcollectie.