collections

Collections

Motivation

Massendatenverarbeitung

Arrays nicht erweiterbar

Vererbungshierarchie

Collections-Vererbungshierarchie

`Collection<T>`

public interface Collection<E> extends Iterable<E> {

    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);   // getSharedElements
    void clear();
    boolean equals(Object o);
    int hashCode();
}

boolean returnwert ⟹ hat sich Collection geändert

Konstruktoren

jede Collection hat zumindest 2 Konstruktoren:

public CollectionImpl(): erzeugt eine leere Collection
public CollectionImpl(Collection c): erzeugt eine neue Collection, welche alle Elemente der übergebenen enthält

List<Integer> original = new ArrayList<>();
original.add(10);
original.add(20);
original.add(30);
List<Integer> copy = new ArrayList<>(original);
original.set(1, 42);

original: [10, 42, 30]
copy: [10, 20, 30]

`List<E>`

Indexbasierter Zugriff

nicht sortiert, aber sortierbar

geordnet: Zuletzt eingefügtes Element am Ende

public interface List<E> extends Collection<E> {

    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    default void sort(Comparator<? super E> c) { ... }
    List<E> subList(int fromIndex, int toIndex);
}

Implementierungen

ArrayList: Liste wird durch Array realisiert.
Bei Bedarf wird das Array vergrößert
LinkedList: Wie in 2.Klasse implementiert

List<String> words = new ArrayList<>();
words.add("Apfel");
words.add("Biene");
words.add("Honig");

[Apfel, Biene, Honig]

words.add(1, "Imker");

[Apfel, Imker, Biene, Honig]

for (String word : words)
     word.toUpperCase();

Collections.sort(words);
words.sort(null);

[Apfel, Biene, Honig, Imker]

`Set<T>`

enthält nur unique Elemente
keine neuen Methoden

Implementierungen

HashSet: verwendet einen Hashtable; schnell
TreeSet: speichert Elemente sortiert; langsam
LinkedHashSet: verwendet zusätzlich eine LinkedList
⟹ geordnet; mittelschnell

Collection<Integer> set = new HashSet<>();
set.add(404);
set.add(201);
set.add(-37);
set.add(-37);

[404, -37, 201]

Collection<String> set = new TreeSet<>();
set.add("POS");
set.add("AM");
set.add("NVS");

[AM, NVS, POS]

Collection<String> set = new LinkedHashSet<>();
set.add("POS");
set.add("AM");
set.add("NVS");

[POS, AM, NVS]

Problem

public class Dog {
    private String name;

    public Dog(String name) {
        this.name = name;
    }
}

Collection<Dog> dogs = new HashSet<>();
dogs.add(new Dog("Ecco"));
dogs.add(new Dog("Ecco"));
int size = dogs.size();

Hashing

Set<User> users = getAllUsers();
User user = new User(input);
if (users.contains(user))
    ...

==: user muss exakt dasselbe Objekt wie im Set sein
equals: User hat 7 Instanzvariablen ⟹ langsam
Hashing: user.hashCode() wird berechnet; hat ein Element in users den gleichen Hashcode; könnte es das richtige sein ⟹ jetzt equals

Kollisionen

hashing

John Smith und Sandra Dee haben gleichen hash

Wird nun Sandra Dee gesucht, so wird nur in Bucket 152 gesucht

Beispiel

class Student {

    private int katalognummer;
    private String name;

    public int hashCode() {
        return katalognummer;
    }
}

gleiche KatNr ⟹ vielleicht gleiche Schüler
andere KatNr ⟹ unterschiedliche Schüler
gleiche Schüler ⟹ gleiche KatNr
unterschiedliche Schüler ⟹

`hashCode` / `equals` - Contract

a.hashCode() == b.hashCode(): Objekte vielleicht equal
a.hashCode() != b.hashCode(): Objekte unterschiedlich
a.equals(b): a.hashCode() == b.hashCode()
!a.equals(b): a != b

Mutablity

Collection<Dog> dogs = new HashSet<>();
Dog ecco = new Dog("Ecco")
dogs.add(ecco);
dogs.add(new Dog("Snoopy"));
ecco.setName("Snoopy");

⚠️ Set korrupt ⚠️

Daten in einem Set sollten immutable sein

wie String
Instanzvariable private final
setter returnen neue Objekte

`TreeSet<T>`

public class Student {

    private String name;
    private int id;

    public Student(String name, int id) {
        this.name = name;
        this.id = id;
    }
}

Set<Student> students = new TreeSet<>();
Student student = new Student("Alfred", 1);
students.add(student);

java.lang.ClassCastException: 
    class Student cannot be cast to class java.lang.Comparable

`Comparable<T>`

public interface Comparable<T> {
    /**
    *   this < o  ==> < 0
    *   this == o ==>  0
    *   this > o  ==> > 0
    */
    public int compareTo(T o);
}

definiert eine natural order
beim Einfügen in ein TreeSet gecalled
beim Sortieren einer List / eines Arrays gecalled

Implementierung

public class Student implements Comparable<Student>{

    @Override
    public int compareTo(Student o) {
        int result = Integer.compare(id, o.id);
        if (result != 0) 
            return result;
        return name.compareTo(o.name);
    }

Set<Student> students = new TreeSet<>();
students.add(new Student("Alfred", 1));
students.add(new Student("Bernd", 2));
students.add(new Student("Agatha", 1));

[{Agatha, id=1}, {Alfred, id=1}, {Bernd, id=2}]

public int compareTo(Student o) {
    return Comparator.comparingInt(Student::getId)
            .thenComparing(Student::getName)
            .compare(this, o);
}

`NavigableSet<T>`

public interface NavigableSet<E> extends SortedSet<E> {

    E lower(E e);   // returnt < e
    E floor(E e);   // returnt <=e
    E ceiling(E e); // returnt >=e
    E higher(E e);  // returnt > e
    E pollFirst();  // return min
    E pollLast();   // return max
    SortedSet<E> subSet(E fromElement, E toElement);    // from < all < to
    SortedSet<E> headSet(E toElement);      // min < all < to
    SortedSet<E> tailSet(E fromElement);    // from <= all < max
}

Ermöglicht äquivalent zu SQL die höchsten / niedrigsten Werte zu selektieren

`Comparator<T>`

public interface Comparator<T> {

    /**
    *   o1 < o2  ==> < 0
    *   o1 == o2 ==>  0
    *   o1 > o2  ==> > 0
    */
    int compare(T o1, T o2);
}

OO - Repräsentation von Sortierregeln

zum Überschreiben der natural Order

oder falls keine vorhanden ist

Anwendung

List<String> caesars = 
        Arrays.asList("Cäsar", "Augustus", "Justinian", "Nero");

[Cäsar, Augustus, Justinian, Nero]

Collections.sort(caesars);

[Augustus, Cäsar, Justinian, Nero]

Comparator<String> byLength = new Comparator<>() {
    @Override
    public int compare(String o1, String o2) {
        return Integer.compare(o1.length(), o2.length());
    }
};
caesars.sort(byLength);
System.out.println(caesars);

[Nero, Cäsar, Augustus, Justinian]

Map / Dictionary / Assoziatives Array

🐍
dictionary = {'POS': 'SCRE', 'AM': 'RIEE', 'E': 'NEUL'}
dicionary['POS'] # -> 'SCRE'

array["POS"]

🚫 incompatible types: java.lang.String cannot be converted to int

map.put("POS", "SCRE");
map.get("POS") -> "SCRE"

Speichern von key / value - Paaren

`Map<K, V>`

public interface Map<K, V> {

    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    default V getOrDefault(Object key, V defaultValue) { ... }
    default V putIfAbsent(K key, V value) { ... }
}

Implementierungen

HashMap
Keys werden in einem HashSet gespeichert: TreeMap
Keys werden in einem TreeSet gespeichert: LinkedHashMap
Keys werden in einem LinkedHashSet gespeichert

Iterieren

Set<K> keySet()
Liefert alle keys: Collection<V> values()
Liefert alle values: Set<Map.Entry<K, V>> entrySet()
Liefert alle key / value - Paare

Wichtige Methoden

if (map.contains(key))
    result = map.get(key);
else
    result = defaultValue;

return map.getOrDefault(key, defaultValue);

if (!map.contains(key))
    map.put(key, newValue);

map.putIfAbsent(key, newValue);

`Queue<T>`

Warteschlange, FIFO (oder FILO)

Teilweise mit beschränkter Kapazität

public interface Queue<E> extends Collection<E> {

    boolean add(E e);       // full  -> Exception
    boolean offer(E e);     // full  -> false
    E remove();             // empty -> Exception     
    E poll();               // empty -> null
    E element();            // empty -> Exception
    E peek();               // empty -> null
}

`PriorityQueue<T>`

remove/poll entfernt immer Minimum

Queue<String> queue = new PriorityQueue<>();
queue.add("NVS");
queue.add("AM");
queue.add("D");
queue.add("POS");
System.out.println(queue);

⚠️ [AM, NVS, D, POS] ⚠️

StringJoiner joined = new StringJoiner(", "); 
while(!queue.isEmpty())
    joined.add(queue.remove());
System.out.println(joined);

AM, D, NVS, POS

collections

Collections

Motivation

Vererbungshierarchie

Collection<T>

Konstruktoren

List<E>

Implementierungen

Set<T>

Implementierungen

Problem

Hashing

Kollisionen

Beispiel

hashCode / equals - Contract

Mutablity

TreeSet<T>

Comparable<T>

Implementierung

NavigableSet<T>

Comparator<T>

Anwendung

Map / Dictionary / Assoziatives Array

Map<K, V>

Implementierungen

Iterieren

Wichtige Methoden

Queue<T>

PriorityQueue<T>

`Collection<T>`

`List<E>`

`Set<T>`

`hashCode` / `equals` - Contract

`TreeSet<T>`

`Comparable<T>`

`NavigableSet<T>`

`Comparator<T>`

`Map<K, V>`

`Queue<T>`

`PriorityQueue<T>`