Kolekcje

Interfejsy i klasy służące do przechowywania obiektów


dr inż. Aleksander Smywiński-Pohl

apohllo@o2.pl

http://apohllo.pl/dydaktyka/programowanie-obiektowe

Plan

  • kolekcje - Collection
  • listy - List
  • iteratory - Iterator, Iterable
  • zbiory - Set
  • słowniki - Map

Interfejs Collection

  • najbardziej wysokopoziomowy interfejs
  • mapa nie jest kolekcją (w Javie)
  • podstawowe operacje
    • add
    • addAll
    • remove
    • removeAll
    • retainAll
    • clear
    • isEmpty

Interfejs Collection cd.

  • podstawowe operacje
    • size
    • contains
    • containsAll
    • toArray
    • singleton
    • iterator

Kolekcje bez typu

In [ ]:
Collection cars = new LinkedList();
Car car1 = new Car();
Rocket rocket1 = new Rocket();
cars.add(car1);
cars.add(rocket1);
cars.contains(car1);           // => true
cars.contains(rocket1);        // => true
cars.contains(new Rocket());   // => false

Kolekcje z typem

In [ ]:
class Car {}
class Rocket {}

Collection<Car> cars = new LinkedList<>();
Car car1 = new Car();
Rocket rocket1 = new Rocket();
cars.add(car1);
cars.add(rocket1);         // błąd kompilacji

add, addAll, remove, removeAll

In [ ]:
Collection<Car> cars1 = new LinkedList<>();
cars1.add(new Car());
cars1.add(new Car());
cars1.add(new Car());
Collection<Car> cars2 = new LinkedList<>();
In [ ]:
for(Car car : cars1){
    cars2.add(car);
}
// prościej
cars2.addAll(cars1);
In [ ]:
for(Car car : cars1){
    cars2.remove(car);
}
// prościej
cars2.removeAll(cars1);

remove, size, empty i singleton

In [5]:
class Car {}
Collection<Car> cars1 = new LinkedList<>();
Car car = new Car();
cars1.add(car);
cars1.add(car);
cars1.remove(car);
cars1.size();
Out[5]:
1
In [6]:
class Car {}
Collection<Car> cars1 = new LinkedList<>();
Car car = new Car();
cars1.add(car);
cars1.add(car);
cars1.removeAll(Collections.singleton(car));
cars1.isEmpty();
Out[6]:
true

toArray

In [ ]:
Collection<Car> cars1 = new LinkedList<>();
Car car = new Car();
cars1.add(car);
cars1.add(car);
cars1.add(new Car());
In [ ]:
Car[] carsAsArray1 = cars1.toArray();             // to nie zadziała
Object[] carsAsArray2 = cars1.toArray();          // to zadziała
Car[] carsAsArray3 = cars1.toArray(new Car[0]);   // i to też

singleton i opcjonalne metody

In [ ]:
Collection<Car> oneCar = Collections.singleton(new Car());
oneCar.add(new Car());
In [ ]:
oneCar.add(new Car());
|  java.lang.UnsupportedOperationException thrown: 
|        at AbstractCollection.add (AbstractCollection.java:267)
|        at (#77:1)

Interfejs List

  • uporządkowany zbiór obiektów
  • obiekty mogą się powtarzać
  • obiekty posiadają indeks

Interfejs List

  • metody List
    • get
    • set
    • indexOf
    • lastIndexOf
    • subList
  • metody Collections
    • sort
    • min, max
  • metody Arrays
    • asList

In [ ]:
List<String> words = Arrays.asList("jeden", "dwa", "trzy");
words.get(0);          // => "jeden"
words.set(0,"zero");   // => "jeden"
words.get(0);          // => "zero"
words.add("dwa");      // UnsupportedOperationException
In [ ]:
List<String> words = Arrays.asList("jeden", "dwa", "jeden");
words.indexOf("jeden");        // => 0
words.lastIndexOf("jeden");    // => 2
In [9]:
List<String> words = new LinkedList<>();
words.add("jeden");
words.add("dwa");
words.add("jeden");
//words.subList(1,3).clear();       
//words                                     // ["jeden"]
words.subList(0,1).add("sześć")
words
Out[9]:
jeden
sześć
dwa
jeden

Collections: sort, min, max

In [ ]:
List<String> words = Arrays.asList("jeden", "dwa", "trzy");
Collections.sort(words);           // "dwa", "jeden", "trzy"
In [ ]:
Collections.min(words);   // "dwa"
Collections.max(words);   // "trzy"

Lista liczb

In [ ]:
List<Integer> numbers = new LinkedList<>();
numbers.add(3);
numbers.add(2);
numbers.add(1);
numbers.add(0);
numbers.remove(0);
numbers.remove(new Integer(0));
numbers

Implementacje interfejsu List

Klasa Reprezentacja Uwagi
`ArrayList` tablica implementacja ogólnego przeznaczenia
`LinkedList` lista dwukierunkowa efektywne wstawianie i usuwanie
`CopyOnWriteArrayList` tablica bezpieczna zw. na wątki
`Vector` tablica synchronizowane metody, przestarzała
`Stack` tablica dodaje metody `push`, `pop`, `peek`, przestarzała

Wzorzec Iterator

In [ ]:
Collection<Car> cars1 = new LinkedList<>();
Car car = new Car();
cars1.add(car);
cars1.add(car);
Iterator<Car> iterator = cars1.iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}
In [ ]:
// krócej
for(Car car : cars1){
    System.out.println(car);
}

Interfejs Iterator<E>

  • służy do definiowania iteratorów
  • metody:
    • next
    • hasNext
    • remove
In [ ]:
public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

Interfejs Iterable<E>

  • zwraca iterator
  • pozwala "chodzić" po swoich elementach
In [ ]:
public interface Iterable<E> {
    java.util.Iterator<E> iterator();
}

Wyjątek ConcurrentModificationException

In [3]:
List<String> cars = new LinkedList<>(Arrays.asList("jeden", "dwa", "trzy"))
Iterator<String> iterator = cars.iterator();
cars.remove("jeden");
iterator.next();
java.util.ConcurrentModificationException
	at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:966)
	at java.util.LinkedList$ListItr.next(LinkedList.java:888)
	at java_util_ListIterator$next.call(Unknown Source)
	at org.codehaus.groovy.runtime.callsite.CallSiteArray.defaultCall(CallSiteArray.java:48)
	at org.codehaus.groovy.runtime.callsite.AbstractCallSite.call(AbstractCallSite.java:113)
	at org.codehaus.groovy.runtime.callsite.AbstractCallSite.call(AbstractCallSite.java:117)
	at Script3.run(Script3.groovy:4)
	at org.scijava.plugins.scripting.groovy.GroovyScriptEngine.eval(GroovyScriptEngine.java:303)
	at org.scijava.plugins.scripting.groovy.GroovyScriptEngine.eval(GroovyScriptEngine.java:122)
	at javax.script.AbstractScriptEngine.eval(AbstractScriptEngine.java:264)
	at org.scijava.script.ScriptModule.run(ScriptModule.java:159)
	at org.scijava.module.ModuleRunner.run(ModuleRunner.java:167)
	at org.scijava.jupyter.kernel.evaluator.Worker.run(Worker.java:109)
	at org.scijava.thread.DefaultThreadService$2.run(DefaultThreadService.java:220)
	at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
	at java.lang.Thread.run(Thread.java:745)
Out[3]:
No Outputs
In [ ]:
iterator.next();
iterator.remove();

Interfejs Set

  • przechowuje elementy bez powtórzeń
  • wymaga poprawnej definicji metod equals i hashCode

equals i hashCode

In [ ]:
class Car {
    private String vin;
    
    public Car(String vin){
        this.vin = vin;
    }
    
    public boolean equals(Object other){
        //...
        Car that = (Car) other;
        return this.vin.equals(that.vin);
    }
    
    public int hashCode(){
        return this.vin.hashCode();
    }
}

Car car1 = new Car("ABC");
Car car2 = new Car("ABC");
Set<Car> cars = new HashSet<>();
cars.add(car1);
cars.add(car2);
cars.size();

Interfejs SortedSet

  • SortedSet przechowuje elementy w sposób uporządkowany
  • wymaga aby obiekty imeplementowały interfejs Comparable lub aby przekazano do niego obiekt implementujący interfejs Comparator
  • metody:
    • headSet
    • tailSet
    • subSet
    • first
    • last

Przykład

In [ ]:
SortedSet<String> numbers = new TreeSet<>(Arrays.asList("dwa", "jeden", "trzy"));
println(numbers.headSet("jeden"));
println(numbers.tailSet("jeden"));
println(numbers.tailSet("jeden\0"));
println(numbers.subSet("dwa\0","trzy"));
[dwa]
[jeden, trzy]
[trzy]
[jeden]

Implementacje interfejsu Set

Klasa Reprezentacja Uporządkowanie Ograniczenia Wydajność dostępu Wydajność iteracji Uwagi
`HashSet` tablica haszująca brak brak O(1) O(pojemność) implementacja ogólnego przeznaczenia
`LinkedHashSet` powiązana tablica haszująca kolejność wstawiania brak O(1) O(n) zachowuje kolejność
`EnumSet` pole bitowe deklaracja wartości `enum` O(1) O(n) tylko wartości `enum`
`TreeSet` drzewo czerwono-czarne sortowanie rosnące porównywalność O(log(n)) O(n) `Comparable` lub `Comparator`
`CopyOnWriteArraySet` tablica kolejność wstawiania brak O(n) O(n) bezpieczna zw. na wątki

Interfejs Map

  • implementuje strukturę słownika
  • odwzorowuje klucze na wartości
  • można to interpretować jako tablicę indeksowaną kluczami, które nie muszą być liczbami
  • (zazwyczaj) pozwala na szybki dostęp do elementów

Interfejs Map

  • metody:
    • put
    • get
    • remove
    • containsKey
    • containsValue
    • keySet
    • values
    • entrySet

put, get, remove

In [ ]:
Map<String,Integer> numbers = new HashMap<>();
numbers.put("jeden", 1);
numbers.put("dwa", 2);
numbers.put("trzy", 3);
numbers.get("dwa");            // => 2
numbers.remove("dwa");         // => 2
numbers.get("dwa")             // => null

containsKey, containsValue

In [ ]:
Map<String,Integer> numbers = new HashMap<>();
numbers.put("jeden", 1);
numbers.put("dwa", 2);
numbers.put("trzy", 3);
numbers.containsKey("jeden");        // => true
numbers.containsKey("cztery");       // => false
numbers.containsValue(1);            // => true
numbers.containsValue(4);            // => false

keySet, values, entrySet

In [ ]:
Map<String,Integer> numbers = new HashMap<>();
numbers.put("jeden", 1);
numbers.put("dwa", 2);
numbers.put("trzy", 3);
numbers.keySet();                        // => Set: "jeden", "trzy", "dwa"
numbers.values();                        // => Collection 1, 3, 2
for(Map.Entry<String,Integer> entry : numbers.entrySet()){
    System.out.println("" + entry.key + " : " + entry.value);
}
// jeden : 1
// trzy : 3
// dwa : 2
numbers.keySet().remove("jeden")
numbers                                  // => {trzy=3, dwa=2}

Interfejs SortedMap

  • rozszerza interfejs Map
  • elementy są sortowane względem wartości kluczy
  • wymaga elementów typu Comparable lub przekazania obiektu Comparator
  • metody:
    • firstKey
    • lastKey
    • headMap
    • tailMap
    • subMap

firstKey, lastKey

In [ ]:
SortedMap<String,Integer> numbers = new TreeMap<>();
numbers.put("jeden", 1);
numbers.put("dwa", 2);
numbers.put("trzy", 3);
numbers.firstKey();               // "dwa"
numbers.lastKey();                // "trzy"

Implementacje interfejsu Map

Klasa Reprezentacja klucze `null` wartości `null` uwagi
`HashMap` tablica haszująca tak tak implementacja ogólnego przeznaczenia
`ConcurrentHashMap` tablica haszująca nie nie implementacja bezpieczna zw. na wątki
`ConcurrentSkipListMap` tablica haszująca nie nie jw., interfejs `ConcurrentNavigableMap`
`EnumMap` tablica nie nie klucze to wartości `enum`
`LinkedHashMap` tablica haszująca tak tak zachowuje kolejność wstawiania
`TreeMap` drzewo czerwono-czarne nie tak posortowana wg wartości kluczy
`IdentityHashMap` tablica haszująca tak tak do porównywania używa ==
`WeakHashMap` tablica haszująca tak tak korzysta ze słabych referencji dla kluczy
`Hashtable` tablica haszująca nie nie przestarzała, synchronizowane metody
`Properties` tablica haszująca nie nie rozszerza `Hashtable` o metody klasy `String`

Pytania?