Kolekcje

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

apohllo@agh.edu.pl

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

konsultacje: wtorek 15:30 - 18:00, pokój 4.61

Plan

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

Interfejs Collection

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

Interfejs Collection posiada najważniejsze wywołania związane z obsługą różnych typów kolekcji.

Interfejs Collection cd.

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

Kolekcje bez typu

class Car {}
class Rocket {}

Collection cars = new LinkedList();
Car car1 = new Car();
Rocket rocket1 = new Rocket();
cars.add(car1);
cars.add(rocket1);
System.out.println(cars.contains(car1));           
System.out.println(cars.contains(rocket1));        
System.out.println(cars.contains(new Rocket()));

Kolekcje bez typu (bez parametru w nawiasach ostrych) pozwalają przechowywać dowolne wartości referencyjne. W jednej kolekji można zatem umieszczać obiekty z klas zupełnie ze sobą niepowiązanych. Późniejsze wykorzystanie obiektu z takiej kolekcji wymaga jednak rzutowania na odpowiedni typ. Ponieważ jednak nie mamy gwarancji, że w danej kolekcji są obiekty tylko tego typu, rzutowanie takie może zakończyć się błędem.

Kolekcje z typem

class Car {
    public void drive(){}
}
class Rocket {}

var cars = new LinkedList<Car>();
Car car1 = new Car();
Rocket rocket1 = new Rocket();
cars.add(car1);
//cars.add(rocket1);    
Car car2 = cars.get(0);
car2.drive();

Kolekcje z typem (przykładowo kolekcja cars posiada typ Car) pozwalają na składowanie wyłącznie obiektów danego typu (włączając w to obiekty typów dziedziczących lub implementujących dany interfejs). Dzięki temu kompilator może określić typ zwracanego biektu i nie ma potrzeby rzutowania go. Co więcej do takiej kolekcji nie można dodać obiektów typu niekompatybilnego.

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

Metoda addAll pozwala dodać do danej kolekcji wszystkie elementy z innej kolekcji.

for(Car car : cars1){
    cars2.remove(car);
}
// prościej
cars2.removeAll(cars1);
cars2.remove(cars1);

remove, size, isEmpty i singleton

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

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

Metoda removeAll ma podobną semantykę do addAll, ale ma inną semantykę od remove - tzn. w przypadku remove zostanie usunięte tylko jedno wystąpienie danego obiektu (nawet jeśli występuje wielokrotnie), a removeAll usunie wszystkie wystąpienia powtarzającego się obiektu. Warunkiem poprawności działania tych metod jest poprawne zaimplementowanie metody equals.

Ponadto removeAll akceptuje kolekcję - jeśli zatem chcemy usunąć jeden powtarzający się element, musimy zamienić go na kolekcję, za pomocą wywołania Collections.singleton.

toArray

Collection<Car> cars1 = new LinkedList<>();
Car car = new Car();
cars1.add(car);
cars1.add(car);
cars1.add(new Car());

Car[] carsAsArray1 = cars1.toArray();

Object[] carsAsArray2 = cars1.toArray();  
Car[] carsAsArray3 = cars1.toArray(new Car[0]);

Wywołanie toArray, które dostępne jest w interfejsie Collection pozwala zamienić daną kolekcję na tablicę. Jeśli jednak chcemy zrzutować na tablicę określonego typu, musimy skorzystać z wywołania z argumentem akceptującym pustą tablicę odpowiedniego typu.

singleton i opcjonalne metody

Collection<Car> oneCar = Collections.singleton(new Car());
oneCar.add(new Car());

Nie wszystkie metody w interfejsach są realnie dostępne. Metody opcjonalne mogą rzucić wyjątek UnsupportedOperationException.

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

List<String> words = Arrays.asList("jeden", "dwa", "trzy");
System.out.println(words.get(0));          
System.out.println(words.set(0,"zero"));   
System.out.println(words.get(0));          
System.out.println(words.add("dwa"));

words.get(5)

Próba pobrania wartości dla indeksu, który przekracza jej rozmiar skutkuje wyjątkiem ArrayIndexOutOfBoundsException.

Kolekcja zwracana przez Arrays.asList() jest niemodyfikowalna, dlatego przy próbie dodania obiektu rzucany jest wyjątek UnsupportedOperationException.

List<String> words = Arrays.asList("jeden", "dwa", "jeden");
System.out.println(words.indexOf("jeden"));    
System.out.println(words.lastIndexOf("jeden"));

List<String> words = new LinkedList<>();
words.add("jeden");
words.add("dwa");
words.add("trzy");
System.out.println(words); 
words.subList(1,3).clear();       
System.out.println(words); 
words.subList(0,1).add("sześć");
System.out.println(words);

Collections: sort, min, max

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

Collections.sort(words, new Comparator<String>() {
    public int compare(String a, String b) {
        if(a.length() == b.length()){
            return a.compareTo(b);
        }
        return a.length() - b.length();
    }
});

System.out.println(Collections.min(words));
System.out.println(Collections.max(words));

Lista liczb

List<Integer> numbers = new LinkedList<>();
numbers.add(3);
numbers.add(2);
numbers.add(1);
numbers.add(0);
numbers.add(0);
//numbers.remove(0);
numbers.remove(new Integer(0));
numbers

Wywołanie remove(int) usuwa element o określonym indeksie. Dlatego jeśli mamy listę liczb, musimy użyć typu otokowego aby usunąć żądany element.

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

• ArrayList - lista oparta o tablice
• LinkedList - lista oparta o listę dwukierunkową
• CopyOnWriteArrayList - tworzy kopię listy, w momencie modyfikacji w danym wątku
• Vector, Stack - przestarzałe, ponieważ synchronizacja metod operujących na tych strukturach nie rozwiązuje żadnych problemów współbieżności, a wpływa negatywnie na wydajność operacji. Jeśli chcemy coś synchronizować, to zazwyczaj jest to cała kolekcja operacji, a nie pojedyncze operacje na danej strukturze. Synchronizowanie metod tych klas nie rozwiązuje więc tego problemu.

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
  • forEachRemaining

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
    default void forEachRemaining(Consumer<? super E> action){ ... }
}

Interfejs Iterable<E>

• zwraca iterator
• pozwala "chodzić" po swoich elementach

public interface Iterable<E> {
    Iterator<E> iterator();
    default Spliterator<T> spliterator();
    default void forEach(Consumer<? super T> action);
}

Wyjątek ConcurrentModificationException

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

iterator.next();
iterator.remove();

Interfejs Set

• przechowuje elementy bez powtórzeń
• wymaga poprawnej definicji metod equals
• klasy implementujące wymagają poprawnej implementacji hashCode, implementacji interfejsu Comparable lub akceptują "zewnętrzną" definicję komparatora

x.equals(y) -> x.hashCode() == y.hashCode()

• SortedSet dodatkowo definiuje metody takie jak first, last, headSet, tailSet oraz subSet. Innymi słowy nadaje porządek elementom zbioru.
• NavigableSet dodaje metody takie jak higher (excl.), floor (incl.), lower (excl.), ceiling (incl.) oraz metody pozwalające na przeglądanie elementów w odwrotnym kierunku. Ponadto rozszerza definicję np. headSet o to, że akceptuje parametr incl./excl., która zwraca NavigableSet.
• HashSet wymaga do działania poprawnej implementacji metody hashCode.
• LinkedHashSet zapamiętuje kolejność elementów, co objawia się w sposobie iterowania po tym zbiorze.

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

1

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

import static java.lang.System.out;

SortedSet<String> numbers = new TreeSet<>(Arrays.asList("dwa", "jeden", "trzy"));
out.println(numbers.headSet("jeden"));
out.println(numbers.tailSet("jeden"));
out.println(numbers.tailSet("jeden\0"));
out.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

• HashSet - oparta o tablicę hashującą implementacja zbioru
• LinkedHashSet - zapamiętuje kolejność dodawania elementów
• EnumSet - znacznie bardziej wydajna implementacja, ponieważ metody realizowane są jako operacje tablicach bitów
• TreeSet - wymaga określenia porządku elementów
• CopyOnWriteArraySet - struktura bezpieczna ze względu na wątki, w tym sensie, że metody modyfikujące zawartość prowadzą do utworzenia nowej kopii. W ogólnym przypadku stosowana w scenariuszach, w których operacje odczytu znacząco przeważają nad operacjami modyfikacji.

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

• SortedMap analogicznie do SortedSet pozwala iterować uwzględniając kolejność kluczy. Posiada analogiczne metody, np. firstKey, lastKey, headMap itd.
• NavigableMap pozwala dodatkowo pobierać klucz lub parę klucz-wartość mniejszą bądź większą od zadanej wartości, słownik o odwrotnej kolejności kluczy, itp.
• LinkedHashMap natomiast analogicznie jak LinkedHashSet zachowuje kolejność dodawania par do słownika.

put, get, remove

Map<String,Integer> numbers = new HashMap<>();
numbers.put("jeden", 1);
numbers.put("dwa", 2);
numbers.put("trzy", 3);
out.println(numbers.get("dwa"));            
out.println(numbers.remove("dwa"));
out.println(numbers.get("dwa"))

2
2
null

containsKey, containsValue

Map<String,Integer> numbers = new HashMap<>();
numbers.put("jeden", 1);
numbers.put("dwa", 2);
numbers.put("trzy", 3);
out.println(numbers.containsKey("jeden"));        
out.println(numbers.containsKey("cztery"));       
out.println(numbers.containsValue(1));            
out.println(numbers.containsValue(4));

true
false
true
false

keySet, values, entrySet

Map<String,Integer> numbers = new HashMap<>();
numbers.put("jeden", 1);
numbers.put("dwa", 2);
numbers.put("trzy", 3);
out.println(numbers.keySet());
out.println(numbers.values());

[jeden, trzy, dwa]
[1, 3, 2]

for(Map.Entry<String,Integer> entry : numbers.entrySet()){
    out.println("" + entry.getKey() + " : " + entry.getValue());
}

jeden : 1
trzy : 3
dwa : 2

numbers.remove("dwa");
numbers

{jeden=1, trzy=3}

numbers.keySet().remove("jeden");
numbers

{trzy=3}

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.put("łał", 4);
out.println(numbers.firstKey());
out.println(numbers.lastKey());

dwa
łał

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

• HashMap - implementacja ogólnego przeznaczenia, wymaga hashCode
• ConcurrentHashMap - implementacja bezpieczna ze względu na wątki z tego względu, że iterowanie nie rzuci wyjątku ConcurrentModificationException jeśli mapa zostanie zmodyfikowana. Niemniej jednak wynik iteracji może nie odzwierciedlać aktualnego stanu kolekcji. Ponadto dostęp do określonego klucza odzwierciedla stan zakończonej operacji jego modyfikacji. Metody modyfikujące wiele kluczy przy odczycie będą dawały przybliżoną wartość zawartości tej struktury (tzn. mogą zawierać jeszcze jakieś klucze, gdy operacja clear jest w toku).
• ConcurrentSkiListMap - bezpieczna ze względu na wątki implementacja interfejsu ConcurrentNavigableMap. Semantyka operacji współbieżnych analogiczna jak w przypadku ConcurrentHashMap.
• EnumMap - implementacja nalogiczna jak EnumSet.
• TreeMap - implementacja ogólnego przeznaczenia interfejsu NavigableMap
• IdentityHashMap - opiera się na porównaniu za pomocą == a nie equals do porównywania kluczy.
• WeakHashMap - wpisy mogą być usunięte, jeśli dana mapa jest jedynym sposobem "dotarcia" do danego klucza (ale nie wartości). Przydatna w implementacji struktur takich jak cache.
• Hashtable - analogicznie jak Vector i Stack synchronizuje na poszczególnych operacjach.

Metody pomocnicze Collections

• binarySearch - wyszukiwanie połówkowe
• checkedCollection - operacje modyfikacji są weryfikowane w czasie wykonania, a nie kompilacji
• disjoint - sprawdza rozłączność dwóch kolekcji
• emptyList - zwraca pustą listę
• fill - wypełnia listę dostarczonymi wartościami
• max - zwraca element największy
• rotate - przenosi elementy w kierunku końca
• synchronizedList - metody są synchronizowane, iterowanie wymaga synchronizacji na widoku
• unmodifiableList - zwraca niemodyfikowalny widok danej listy