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 cd.

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

Kolekcje bez typu

In [ ]:
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 z typem

In [ ]:
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();

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);
cars2.remove(cars1);

remove, size, isEmpty i singleton

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

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();
In [ ]:
Object[] carsAsArray2 = cars1.toArray();  
Car[] carsAsArray3 = cars1.toArray(new Car[0]);

singleton i opcjonalne metody

In [ ]:
Collection<Car> oneCar = Collections.singleton(new Car());
oneCar.add(new Car());

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");
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"));
In [ ]:
words.get(5)
In [ ]:
List<String> words = Arrays.asList("jeden", "dwa", "jeden");
System.out.println(words.indexOf("jeden"));    
System.out.println(words.lastIndexOf("jeden"));
In [ ]:
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

In [ ]:
List<String> words = Arrays.asList("jeden", "dwa", "trzy");
Collections.sort(words);        
words
In [ ]:
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();
    }
});
In [ ]:
System.out.println(Collections.min(words));
System.out.println(Collections.max(words));

Lista liczb

In [ ]:
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

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
    • forEachRemaining
In [ ]:
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
In [ ]:
public interface Iterable<E> {
    Iterator<E> iterator();
    default Spliterator<T> spliterator();
    default void forEach(Consumer<? super T> action);
}

Wyjątek ConcurrentModificationException

In [ ]:
List<String> cars = new LinkedList<>(Arrays.asList("jeden", "dwa", "trzy"));
Iterator<String> iterator = cars.iterator();
iterator.next();
cars.remove("jeden");
iterator.next();
In [ ]:
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()

In [ ]:

equals i hashCode

In [33]:
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();
Out[33]:
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

In [34]:
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

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 [35]:
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

In [36]:
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

In [37]:
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]
In [38]:
for(Map.Entry<String,Integer> entry : numbers.entrySet()){
    out.println("" + entry.getKey() + " : " + entry.getValue());
}
jeden : 1
trzy : 3
dwa : 2
In [39]:
numbers.remove("dwa");
numbers
Out[39]:
{jeden=1, trzy=3}
In [40]:
numbers.keySet().remove("jeden");
numbers
Out[40]:
{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

In [42]:
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

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

Pytania?