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
  • strumienie - Streams

Interfejs Collection

  • najbardziej wysokopoziomowy interfejs
  • mapa nie jest kolekcją (w Javie)
  • podstawowe operacje
    • add
    • addAll
    • remove
    • removeAll
    • retainAll
    • clear
    • isEmpty
    • size
    • contains
    • containsAll
    • toArray
    • singleton
    • iterator

Kolekcje bez typu

Collection cars = new LinkedList();
Car car1 = new Car();
Rocket rocket1 = new Rocket();
cars.add(car1);
cars.add(rocket);
cars.contains(car1);           // => true
cars.contains(rocket1);        // => true
cars.contains(new Rocket());   // => false

Kolekcje z typem

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

add, addAll, remove, removeAll

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

remove, size, empty i singleton

Collection<Car> cars1 = new LinkedList<>();
Car car = new Car();
cars1.add(car);
cars1.add(car);
cars1.remove(car);
cars1.size();
cars1.add(car);
cars1.add(car);
cars1.removeAll(Collections.singleton(car));
cars1.isEmpty();

toArray

Collection<Car> cars1 = new LinkedList<>();
Car car = new Car();
cars1.add(car);
cars1.add(car);
cars1.add(new Car());
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

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

List

  • uporządkowany zbiór obiektów
  • obiekty mogą się powtarzać
  • obiekty posiadają indeks
  • metody List
    • get
    • set
    • indexOf
    • lastIndexOf
    • subList
  • metody Collections
    • sort
    • min, max
  • metody Arrays
    • asList
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
List<String> words = Arrays.asList("jeden", "dwa", "jeden");
words.indexOf("jeden");        // => 0
words.lastIndexOf("jeden");    // => 2
List<String> words = new LinkedList<>();
words.add("jeden");
words.add("dwa");
words.add("jeden");
words.subList(1,3).clear();       
words                                     // ["jeden"]

Collections: sort, min, max

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

Lista liczb

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

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());
}
// krócej
for(Car car : cars1){
    System.out.println(car);
}

Interfejs Iterator<E>

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

Interfejs Iterable<E>

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

Wyjątek ConcurrentModificationException

List<String> cars = new LinkedList<>(Arrays.asList("jeden", "dwa", "trzy"))
Iterator<String> iterator = cars.iterator();
cars.remove("jeden");
iterator.next();
iterator.next();
iterator.remove();

Interfejs Set

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

equals i hashCode

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

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

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
  • pozwala na szybki dostęp do elementów
  • metody:
    • put
    • get
    • remove
    • containsKey
    • containsValue
    • keySet
    • values
    • entrySet

put, get, remove

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

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

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

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`

Interfejs Stream i techniki funkcyjne

  • interfejs Collection został rozszerzony o metodę streams
  • metoda ta została wprowadzona aby ograniczyć wsteczną niekompatybilność
  • metoda ta jest domyślna w interfejsie Collection
  • metoda zwraca elemet typu Stream
  • interfejs Stream umożliwia wykonywania metod funkcyjnych:
    • allMatch
    • anyMatch
    • collect
    • concat
    • count
    • distinct
    • empty
    • filter
    • findAny
    • findFirst
    • flatMap
    • forEach
    • map
    • itd.

fliter, map i collect

import java.util.stream.*;

Collection<String> numbers = Arrays.asList(1, 2, 3, 4, 5, 6);
numbers.stream().filter(e -> e % 2 == 0).
                 map(e -> e.toString()).
                 collect(Collectors.toList());

map

import java.util.stream.*;

Collection<String> numbers = Arrays.asList("jeden", "dwa", "trzy", "cztery");
numbers.stream().map(String::length).
                 collect(Collectors.joining(", "));

forEach

Collection<String> numbers = Arrays.asList("jeden", "dwa", "trzy", "cztery");
numbers.stream().forEach(System.out::println);
// jeden
// dwa
// trzy
// cztery

map i reduce

Collection<String> numbers = Arrays.asList("jeden", "dwa", "trzy", "cztery");
double sum = numbers.stream().map(String::length).
                              reduce(0, (x,y) -> { return x + y; });
System.out.println(sum / numbers.size());

Pytania?