Java Language
samlingar

Introduktion

Anmärkningar

Förklara en ArrayList och lägga till objekt

Vi kan skapa en ArrayList (efter List gränssnitt):

List aListOfFruits = new ArrayList();

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

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

Använd nu metoden add till för att lägga till en String :

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

I exemplet ArrayList kommer ArrayList att innehålla String "Melon" vid index 0 och String "Strawberry" vid index 1.

Vi kan också lägga till flera element med addAll(Collection<? extends E> c)

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

Nu är "Onion" placerat vid 0 index i aListOfFruitsAndVeggies , "Melon" är på index 1 och "Strawberry" är på index 2.

Konstruera samlingar från befintlig data

Standardsamlingar

Java-samlingsramen

Ett enkelt sätt att konstruera en List från enskilda datavärden är att använda java.utils.Arrays metoden Arrays.asList :

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

Alla standardsamlingsimplementeringar tillhandahåller konstruktörer som tar en annan samling som ett argument som lägger till alla element i den nya kollektionen vid konstruktionen:

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

Ramen för Google Guava Collections

Ett annat bra ramverk är Google Guava som är en fantastisk verktygsklass (som ger statiska metoder för bekvämlighet) för konstruktion av olika typer av standardsamlingar Lists och 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");

Kartlägga samlingar

Java-samlingsramen

På liknande sätt för kartor, med en Map<String, Object> map en ny karta konstrueras med alla element enligt följande:

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

Apache Commons-samlingsramen

Med Apache Commons du skapa karta med hjälp av array i ArrayUtils.toMap samt 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"}});

Varje element i matrisen måste vara antingen en karta. Entry eller en matris, som innehåller minst två element, där det första elementet används som nyckel och det andra som värde.

Ramen för Google Guava Collections

Verktygsklass från Google Guava ramverket heter 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());

Gå med i listor

Följande sätt kan användas för att gå med i listor utan att ändra källlistor.

Första tillvägagångssättet. Har fler rader men lätt att förstå

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

Andra metoden. Har en mindre rad men mindre läsbar.

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

Tredje metoden. Kräver Apache commons-collection- bibliotek från tredje part.

ListUtils.union(listOne,listTwo);

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

Referenser. Gränssnittslista

Ta bort objekt från en lista i en slinga

Det är svårt att ta bort objekt från en lista i en slinga, det beror på att listans index och längd ändras.

Med följande lista är några exempel som ger ett oväntat resultat och några som ger rätt resultat.

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

FELAKTIG

Ta bort i iteration av for uttalande Hoppar över "Banana":

Kodprovet kommer endast att skriva ut Apple och Strawberry . Banana hoppas över för att den går till index 0 när Apple raderas, men samtidigt blir i till 1 .

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

Ta bort det förbättrade for uttalande kastar undantag:

På grund av iterating over collection och modifiering av det samtidigt.

Kaster: java.util.ConcurrentModificationException

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

KORREKT

Ta bort medan slingan används med en Iterator

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

Iterator gränssnittet har en metod remove() inbyggd just för detta fall. Men denna metod är markerad som "valfri" i dokumentationen, och den kan kasta en UnsupportedOperationException .

Kastar: UnsupportedOperationException - om borttagningsoperationen inte stöds av denna iterator

Därför är det tillrådligt att kontrollera dokumentationen för att se till att den här åtgärden stöds (i praktiken, såvida inte samlingen är en oförändlig sådan som erhållits genom ett tredje parts bibliotek eller användningen av en av Collections.unmodifiable...() -metoden, operationen stöds nästan alltid).

När du använder en Iterator en ConcurrentModificationException kastas när modCount av List ändras från när Iterator skapades. Detta kunde ha hänt i samma tråd eller i en flertrådad applikation som delar samma lista.

En modCount är en int variabel som räknar antalet gånger den här listan har modifierats strukturellt. En strukturell förändring betyder i huvudsak en add() eller remove() -operation som åberopas på Collection objektet (ändringar gjorda av Iterator räknas inte). När Iterator skapas lagrar den detta modCount och på varje iteration av List kontrollerar om det aktuella modCount är samma som och när Iterator skapades. Om det sker en förändring i modCount värdet kastar det en ConcurrentModificationException .

Därför för den ovan deklarerade listan kommer en operation som nedan inte att kasta något undantag:

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

Men om du lägger till ett nytt element i List efter initialisering av en Iterator kommer det att kasta en ConcurrentModificationException :

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

Itererande bakåt

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

Detta hoppar inte över någonting. Nackdelen med detta tillvägagångssätt är att utgången är omvänd. Men i de flesta fall där du tar bort objekt som inte spelar någon roll. Du bör aldrig göra detta med LinkedList .

Iterera framåt, justera loopindex

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

Detta hoppar inte över någonting. När i : te elementet avlägsnas från List , elementet ursprungligen placerad vid index i+1 blir den nya i : te elementet. Därför kan slingan dekrementera i för att nästa iteration för att bearbeta nästa element, utan att hoppa över.

Använda en "bör-tas bort" -lista

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

Denna lösning gör det möjligt för utvecklaren att kontrollera om rätt element tas bort på ett renare sätt.

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

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

Omodifierbar samling

Ibland är det inte en bra praxis att exponera en intern samling eftersom det kan leda till en sårbar kodskänslighet på grund av dess muterbara egenskap. För att tillhandahålla "skrivskyddade" samlingar tillhandahåller java sina omodifierbara versioner.

En omodifierbar samling är ofta en kopia av en modifierbar samling som garanterar att själva samlingen inte kan ändras. Försök att modifiera det kommer att leda till ett undantag från UnsupportedOperationException.

Det är viktigt att märka att objekt som finns i samlingen fortfarande kan ändras.

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

Följande försök att modifiera en omodifierbar samling kommer att göra ett undantag:

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

produktion:

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

Iterating över samlingar

Iterating över List

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

Iterera över kartan

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

Oändliga tomma samlingar

Ibland är det lämpligt att använda en oföränderlig tom samling. Collections tillhandahåller metoder för att få sådana samlingar på ett effektivt sätt:

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

Dessa metoder är generiska och konverterar automatiskt den returnerade samlingen till den typ den tilldelas. Det vill säga en kallelse av t.ex. emptyList() kan tilldelas valfri typ av List och på samma sätt för emptySet() och emptyMap() .

Samlingarna som returneras med dessa metoder är oföränderliga på så sätt att de kommer att kasta UnsupportedOperationException om du försöker ringa metoder som skulle ändra innehållet ( add , put , etc.). Dessa samlingar är främst användbara som ersättare för tomma metodresultat eller andra standardvärden, istället för att använda null eller skapa objekt med new .

Samlingar och primitiva värden

Samlingar i Java fungerar bara för objekt. Det finns ingen Map<int, int> i Java. I stället måste primitiva värden boxas in i objekt, som i Map<Integer, Integer> . Java-automatisk boxning möjliggör transparent användning av dessa samlingar:

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

Tyvärr är omkostningen av detta betydande . En HashMap<Integer, Integer> kräver cirka 72 byte per post (t.ex. på 64-bitars JVM med komprimerade pekare, och antar heltal större än 256, och antar 50% belastning av kartan). Eftersom de faktiska uppgifterna bara är 8 byte ger detta en enorm omkostnad. Dessutom kräver det två nivåer av indirekt (karta -> post -> värde) det är onödigt långsamt.

Det finns flera bibliotek med optimerade samlingar för primitiva datatyper (som endast kräver ~ 16 byte per post vid 50% belastning, dvs 4x mindre minne och en nivå av indirekt mindre), som kan ge betydande prestationsfördelar när du använder stora samlingar av primitiva värden i Java.

Ta bort matchande objekt från listor med Iterator.

Ovan har jag lagt märke till ett exempel för att ta bort objekt från en lista inom en slinga och jag tänkte på ett annat exempel som kan komma till nytta den här gången med Iterator gränssnittet.
Detta är en demonstration av ett trick som kan komma att vara praktiskt när du hanterar dubbla objekt i listor som du vill bli av med.

Obs! Detta lägger bara till de borttagna artiklarna från en lista i ett slingexempel :

Så låt oss definiera våra listor som vanligt

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

Följande metod tar in två samlingsobjekt och utför magin att ta bort elementen i vår removeNameList som matchar element i 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
    }
}

Anropa metoden och nameList och ta bort removeNameList enligt följande removeNames(nameList,removeNameList);
Kommer att producera följande utgång:

Array List innan du tar bort namn: James Smith Sonny Huckle Berry Finn Allan
Array List efter att ha tagit bort namn: James Smith Finn Allan

En enkel snygg användning för samlingar som kan komma till nytta för att ta bort upprepande element i listor.

Skapa din egen Iterable-struktur för användning med Iterator eller för varje slinga.

För att säkerställa att vår samling kan itereras med iterator eller för varje slinga måste vi ta hand om följande steg:

1. De saker vi vill iterera på måste vara Iterable och exponera iterator() .
2. Designa en java.util.Iterator genom att åsidosätta hasNext() , next() och remove() .

Jag har lagt till en enkel generisk implementering av länkad lista nedan som använder enheterna ovan för att göra den länkade listan iterable.

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

Produktion

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

Detta kommer att köras i Java 7+. Du kan låta den köras på Java 5 och Java 6 också genom att ersätta:

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

med

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

eller bara någon annan version genom att integrera kompatibla ändringar.

Fallgrop: undantag för samtidiga ändringar

Detta undantag inträffar när en samling modifieras medan den itereras över den med andra metoder än de som tillhandahålls av iteratorobjektet. Vi har till exempel en lista över hattar och vi vill ta bort alla de som har öronflikar:

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

Om vi kör denna kod kommer ConcurrentModificationException att höjas eftersom koden ändrar samlingen medan den itereras. Samma undantag kan inträffa om en av de flera trådarna som arbetar med samma lista försöker ändra samlingen medan andra uppdateras över den. Samtidig modifiering av samlingar i flera trådar är en naturlig sak, men bör behandlas med vanliga verktyg från den samtidiga programmeringsverktygslådan, till exempel synkroniseringslås, speciella samlingar antagna för samtidig modifiering, modifiering av den klonade samlingen från initial etc.

Undersamlingar

Lista sublista (int fromIndex, int toIndex)

Här från Index är inkluderande och ToIndex är exklusivt.

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

1. Om listan inte finns i givintervallet kastar den IndexOutofBoundException.
2. Vad ändringar som gjorts på listan1 påverkar samma ändringar i listan. Detta kallas backade samlingar.
3. Om fromnIndex är större än toIndex (fromIndex> toIndex) kastar det IllegalArgumentException.

Exempel:

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

Produktion:
Innan sublist [Hello1, Hello2]
Efter subliständringar [Hello1, Hello3, Hello2]

Ställ subset (frånIndex, toIndex)

Här från Index är inkluderande och ToIndex är exklusivt.

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

Den returnerade uppsättningen kommer att kasta en IllegalArgumentException på ett försök att infoga ett element utanför dess intervall.

Kartsundkarta (frånKey, toKey)

fromKey är inkluderande och toKey är exklusiv

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

Om fromKey är större än tokey eller om den här kartan i sig har ett begränsat intervall, och fråney eller toey ligger utanför gränserna för området kastar den IllegalArgumentException.

Alla samlingar stöder stödjade samlingar innebär att ändringar som gjorts i undersamlingen kommer att ha samma ändring på huvudsamlingen.