FHNW: oopI2
Notizen und andere wichtige Merkmale aus dem Modul oopI2 an der FHNW (FS 16).
Notizen und andere wichtige Merkmale aus dem Modul oopI2 an der FHNW (FS 16).
12
0.0 (0)
K. L.
K. L.
Diese Lernkarten behandeln fortgeschrittene Konzepte der objektorientierten Programmierung im Bereich der Datenstrukturen und Algorithmen auf Universitätsniveau. Sie konzentrieren sich auf verschiedene Interfaces und Eigenschaften von Collections wie ArrayList, LinkedList, HashMap, TreeMap, und deren Implementierungen in Java. Die Karteikarten erklären die Hierarchie der Collections, die Operationen und deren Komplexität, sowie die Besonderheiten von Suchalgorithmen und die Handhabung von Duplikaten. Entwickler und Studierende der Informatik profitieren von diesen Lernkarten, um ein tieferes Verständnis der Datenstrukturen und deren effizienten Einsatz in der Softwareentwicklung zu erlangen.
Flashcards
12
Students
3
Language
German
Category
Computer Science
Level
University
Created / Updated
27.02.2016 / 26.05.2019
Für was wird das Interface Iterable verwendet?
Keyboard commands:
= turn,
= for-/backward,
= scroll
Iterable defines the contract that a class has to fulfill for its instances to be usable with the foreach statement.
(O'Reilly: Java Generics and Collections)
Was zeichnet Implementationen vom Interface Set aus?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Beinhaltet keine Duplikate:
Es gibt keine e1.equals(e2); wenn e1 und e2 Elemente von einem Set sind.
- Hierarchie bis zu Set:
Iterable > Collection > Set
Was sind Eigenschaften von HashSet?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Es ist eine konkrete Klasse
- HashMap wird im Hintergrund verwendet.
- Leitet von AbstractCollection > AbstractSet ab
- Implementiert das Set Interface und sorgt dafür das keine Duplikate existieren können.
- Verwendet eine HashMap Instanz im Hintergrund und garantiert deswegen keine einheitliche Reihenfolge beim iterieren.
- Auf add, remove, contains und size O(1)
- Sie ist nicht synchronized implementiert: Mehrere Threads können concurrently darauf zugreifen.
Was sind Eigenschaften von LinkedHashSet?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Hash Table mit einer Implementation des Set Interfaces, welche eine voraussehbare Reihenfolge bei der Iteration hat.
- Differenz zu HashSet: Es verwaltet eine doppelte LinkedList für die Reihenfolge.
- Die Reihenfolge entspricht der Insertion-Order.
- Durch das Set Interface erlaubt es keine Duplikate.
- Sie ist nicht synchronized implementiert.
Was sind die Eigenschaften einer LinkedHashMap?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- HashMap mit einer LinkedList, welche eine voraussehbare Reihenfolge bei der Iteration gewährleistet.
- Differenz zu HashMap: Es verwaltet eine doppelte LinkedList für die Reihenfolge.
- Die Reihenfolge entspricht der Insertion-Order.
- Sie ist nicht synchronized implementiert.
Was sind Eigenschaften von einer HashMap?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Hash Table basierend auf das Map Interface.
- Erlaubt null als Key und Value.
- Die Reihenfolge der Einträge ist willkürlich und kann sich im Laufe der Zeit (hinzufügen/entfernen) verändern.
- Performance bei der Suche: O(1) + O(n)
n = Länge der Kollisionsliste
Was sind Eigenschaften von TreeSet?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Die Elemente sind nach ihrer natürlichen Ordnung geordnet oder von einem Comparator, welcher bei der Erstellung mitgegeben werden kann.
- Sortierung von links nach rechts
- Anzahl Ebenen: Etwa \(\log_2(n)\)
- Komplexität einer Suche, add, remove und contains: \(O(\log n)\)
- Das Interface von Set erlaubt keine Duplikate
- Sie ist nicht synchronized implementiert
Was sind Eigenschaften einer TreeMap?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Die Elemente sind nach ihrer natürlichen Ordnung geordnet oder von einem Comparator, welcher bei der Erstellung mitgegeben werden kann.
- Sortierung von links nach rechts
- Anzahl Ebenen: Etwa \(\log_2(n)\)
- Komplexität einer Suche, add, remove und contains: \(O(\log n)\)
- Der Wert wird überschrieben, falls derselbe Key bereits verwendet wird. Keys müssen Unique sein.
- Sie ist nicht synchronized implementiert
Was sind Eigenschaften einer LinkedList?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Sie ist doppelt verlinkt
- Sie erlaubt alle Elemente und null
- Komplexität bei Operationen: O(n)
- Sie leitet von AbstractCollection > AbstractList > AbstractSequentialList ab
- Sie implmenetiert Iterable, Collection, Queue, Dequeue und List
- Sie ist nicht synchronized implementiert
Was sind Eigenschaften von ArrayDeque?
Keyboard commands:
= turn,
= for-/backward,
= scroll
- Keine Kapazitäteinschränkung: Sie wächst wenn nötig.
- Null Elemente sind nicht erlaubt
- Nicht thread-safe: Falls kein synchronized Wrapper zur Verfügung gestellt wird erlaubt es kein concurrent Zugriff.
- Die meisten Operationen dauern konstant O(1). contains und alles was mit remove funktioniert, dauert O(n).
- In der Regel ist diese Klasse schneller als ein Stack und schneller als eine LinkedList, wenn sie als Queue eingesetzt wird.
Was sind Eigenschaften von ArrayList?
- Die Grösse passt sich laufend an.
- Es erlaubt alle Elemente und auch null
- Operationen wie size, isEmpty, get, set, iterator laufen konstant O(1)
- Elemente hinzufügen dauert O(n) wobei n die Anzahl zu hinzufügenden Elemente ist.
- Andere Operationen (Suche z.B.) dauern O(n) wobei n die Anzahl Elemente in der Liste ist.
Wie sieht die Java Collection Hierarchy etwa aus? Was für Arten von Collection gibt es?
Wie stehen die Datenstrukturen zueinander?
- Collection (Interface)
- List (Interface)
- AbstractList
- ArrayList
- AbstractSequentialList
- LinkedList (i Deque, i Queue)
- AbstractList
- Set (Interface)
- AbstractSet
- HashSet
- TreeSet (i SortedSet)
- AbstractSet
- AbstractCollection
- ArrayDeque (i Queue, i Deque)
- List (Interface)
- Map (Interface)
- AbstractMap
- HashMap
- TreeMap (i SortedMap)
- AbstractMap
-
- 1 / 12
-
Flashcards
Für was wird das Interface Iterable verwendet?
Iterable defines the contract that a class has to fulfill for its instances to be usable with the foreach statement.
(O'Reilly: Java Generics and Collections)
Was zeichnet Implementationen vom Interface Set aus?
- Beinhaltet keine Duplikate:
Es gibt keine e1.equals(e2); wenn e1 und e2 Elemente von einem Set sind.
- Hierarchie bis zu Set:
Iterable > Collection > Set
Was sind Eigenschaften von HashSet?
- Es ist eine konkrete Klasse
- HashMap wird im Hintergrund verwendet.
- Leitet von AbstractCollection > AbstractSet ab
- Implementiert das Set Interface und sorgt dafür das keine Duplikate existieren können.
- Verwendet eine HashMap Instanz im Hintergrund und garantiert deswegen keine einheitliche Reihenfolge beim iterieren.
- Auf add, remove, contains und size O(1)
- Sie ist nicht synchronized implementiert: Mehrere Threads können concurrently darauf zugreifen.
Was sind Eigenschaften von LinkedHashSet?
- Hash Table mit einer Implementation des Set Interfaces, welche eine voraussehbare Reihenfolge bei der Iteration hat.
- Differenz zu HashSet: Es verwaltet eine doppelte LinkedList für die Reihenfolge.
- Die Reihenfolge entspricht der Insertion-Order.
- Durch das Set Interface erlaubt es keine Duplikate.
- Sie ist nicht synchronized implementiert.
Was sind die Eigenschaften einer LinkedHashMap?
- HashMap mit einer LinkedList, welche eine voraussehbare Reihenfolge bei der Iteration gewährleistet.
- Differenz zu HashMap: Es verwaltet eine doppelte LinkedList für die Reihenfolge.
- Die Reihenfolge entspricht der Insertion-Order.
- Sie ist nicht synchronized implementiert.
Was sind Eigenschaften von einer HashMap?
- Hash Table basierend auf das Map Interface.
- Erlaubt null als Key und Value.
- Die Reihenfolge der Einträge ist willkürlich und kann sich im Laufe der Zeit (hinzufügen/entfernen) verändern.
- Performance bei der Suche: O(1) + O(n)
n = Länge der Kollisionsliste
Was sind Eigenschaften von TreeSet?
- Die Elemente sind nach ihrer natürlichen Ordnung geordnet oder von einem Comparator, welcher bei der Erstellung mitgegeben werden kann.
- Sortierung von links nach rechts
- Anzahl Ebenen: Etwa \(\log_2(n)\)
- Komplexität einer Suche, add, remove und contains: \(O(\log n)\)
- Das Interface von Set erlaubt keine Duplikate
- Sie ist nicht synchronized implementiert
Was sind Eigenschaften einer TreeMap?
- Die Elemente sind nach ihrer natürlichen Ordnung geordnet oder von einem Comparator, welcher bei der Erstellung mitgegeben werden kann.
- Sortierung von links nach rechts
- Anzahl Ebenen: Etwa \(\log_2(n)\)
- Komplexität einer Suche, add, remove und contains: \(O(\log n)\)
- Der Wert wird überschrieben, falls derselbe Key bereits verwendet wird. Keys müssen Unique sein.
- Sie ist nicht synchronized implementiert
Was sind Eigenschaften einer LinkedList?
- Sie ist doppelt verlinkt
- Sie erlaubt alle Elemente und null
- Komplexität bei Operationen: O(n)
- Sie leitet von AbstractCollection > AbstractList > AbstractSequentialList ab
- Sie implmenetiert Iterable, Collection, Queue, Dequeue und List
- Sie ist nicht synchronized implementiert
Was sind Eigenschaften von ArrayDeque?
- Keine Kapazitäteinschränkung: Sie wächst wenn nötig.
- Null Elemente sind nicht erlaubt
- Nicht thread-safe: Falls kein synchronized Wrapper zur Verfügung gestellt wird erlaubt es kein concurrent Zugriff.
- Die meisten Operationen dauern konstant O(1). contains und alles was mit remove funktioniert, dauert O(n).
- In der Regel ist diese Klasse schneller als ein Stack und schneller als eine LinkedList, wenn sie als Queue eingesetzt wird.
Was sind Eigenschaften von ArrayList?
- Die Grösse passt sich laufend an.
- Es erlaubt alle Elemente und auch null
- Operationen wie size, isEmpty, get, set, iterator laufen konstant O(1)
- Elemente hinzufügen dauert O(n) wobei n die Anzahl zu hinzufügenden Elemente ist.
- Andere Operationen (Suche z.B.) dauern O(n) wobei n die Anzahl Elemente in der Liste ist.
Wie sieht die Java Collection Hierarchy etwa aus? Was für Arten von Collection gibt es?
Wie stehen die Datenstrukturen zueinander?
- Collection (Interface)
- List (Interface)
- AbstractList
- ArrayList
- AbstractSequentialList
- LinkedList (i Deque, i Queue)
- AbstractList
- Set (Interface)
- AbstractSet
- HashSet
- TreeSet (i SortedSet)
- AbstractSet
- AbstractCollection
- ArrayDeque (i Queue, i Deque)
- List (Interface)
- Map (Interface)
- AbstractMap
- HashMap
- TreeMap (i SortedMap)
- AbstractMap
