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.
Cartes-fiches
12
Utilisateurs
3
Langue
Allemand
Catégorie
Informatique
Niveau
Université
Créé / Mis à jour
27.02.2016 / 26.05.2019
Für was wird das Interface Iterable verwendet?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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?
Commandes clavier:
= tourner,
= avant/arrière,
= faire défiler
- 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
-
Cartes-fiches
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
