ALP 3 Zusammenfassung
ADT - abstract data type
Ein Datentyp der nur über Schnittstellen (Methoden) manipuliert werden kann.
Ein direkter Zugriff auf die Daten findet nicht statt. Objekte dieses Datentyps sind sogenannte abstrakte Datenobjekte (ADO - abstract data object). Es muss gewährleistet sein, dass die ADO nicht die Kapselung durch Referenzen durchbrechen können.
Vorteile:
- mehr Sicherheit
- größere Komfort durch Abstraktion (Datenimplemtation)
- größere Flexibilität, weil Quelltext unabhängig verändert werden kann, solange die Signatur beibehalten wird.
Module
keene Ahnung
Pakete
- Pakete schaffen eigene Namensräume und vermeiden somit die Kollision von Klassennamen
- bessere Strukturierung
- Erlauben Abkapselung von Programmteilen
Schnittstellen / Interfaces
- Sichtbarkeit immer public
- Attribute stets static und final und müssen mit einem Wert belegt sein
Java
Implementation:
interface [Schnittstellenname}[<Generizität>] {
... Deklaration...
}
Java und die konfuse Parameterübergabe
- Java übergibt grundsätzlich Kopien an Methoden
- Wenn Objekte übergeben werden, wird eine Kopie des Zeigers auf das Objekt übergeben
- Es ist also möglich Objekte zu manipulieren, nicht aber den übergebenen Pointer auf ein anderes Objekt zeigen zu lassen
- Beispielaufgabe in der Probeklausur
Haskell
class Schnittstellenname Typvariablenplatzhalter where
Funktionsname :: Signatur
instance Schnittstellenname Typvariable where
... Funktionsimplementierung ...
Beispiel
data Elements t = Elements [t] deriving Show
class Enum t => Queue t where
add :: (Elements t) -> t -> (Elements t)
pop :: (Elements t) -> (t, (Elements t))
instance Queue Integer where
add (Elements x) y = Elements (x ++ [y])
pop (Elements (x:xs)) = (x, Elements xs)
- keine Datenabstraktion!
- Datenabstraktion mit Modulen
(pro Schnittstelle 1 Modul, 1 Modul für gemeinsame Schnittstelle)
module Modulname [(Exportdatentypen)] where
import Modulname [,Modulname]
[data Datenname Datentyp = Definition [deriving Show]]
... Modulimplementierung ...
--end Modulname
Typen
statischer Typ: deklartierter Variablentyp
(z.B. List)
dynamischen Typ: aktueller Typ des Verweises
(z.B. LinkedList)
Software Patterns
- abstract factory
- Definition von Konstruktoren im Interface
- wird eingesetzt bei GUI-Programmierung (für Themes)
- Vorteile
- Isolation von konkreten Klassen
- Nachteile
- neue Klassen lassen sich umständlich hinzufügen, da die abstrakte Fabrik, sowie die konkrete Implentation verändert werden muss
asdf
Polymorphie
Überladen (overloading)
- verschiedene Signaturen (verschiedene Parameter) für Methoden/Funktionen
Überschreiben (overriding)
- gleicher Methodename in der Unterklasse + gleiche Signatur
- es wird jeweils zur Laufzeit die Methode des dynamischen Typs aufgerufen
- Kovarianz: Rückgabetypen und Exceptionstypen müssen Untertypen der Oberklasse sein (in Java!)
- Kontravarianz: Argumenttypen können Untertypen sein (in Java nicht mögliche, führt zu overloading)
- Beispiele:
overloading
public void test(int x) { ... }
public void test(int x, int y) { .. }
overriding
____________ ____________
|Class A | <<------------ |Class B |
|method( t : T )| <<------------ |method( t : T )|
____________ ____________
|Class A | <<------------ |Class B |
|method( t : T )| <<------------ |method( t : T*)|
____________ ____________
|Class A | <<------------ |Class B |
|method( t*: T*)| ------------>> |method( t : T )|
- Generizität (parametrische Polymorphie)
- Invarianz: Die Typparameter sind eindeutig. Dies erlaubt alles was man mit so einem Typparameter machen will (autoboxing, boxing, unboxing, autounboxing)
- Kovarianz: ist die obere Schranke der Vererbungshierarchie. D.h. die Typparameter verhalten sich in der Vererbungshierarchie gleich.
- Kontravarianz: untere Schranke in der Vererbungshierarchie der Typparameter. Dies bedeutet, dass zur Laufzeit keine Annahme ueber den uebergebenen Datentyp gemacht werden koennen. Quasi ist dann obere Schranke vom Typ Object.
- Beispiel:
class TreeSet<E> ..... {
boolean contains(Object o) // kann jeder Typ sein -> Objekt
boolean containsAll(Collection<?> c) // die Collection kann von jedem
// Argumenttyp sein
boolean addAll(Collection<? extends E> c). // beim Hinzufügen muss die Collection
// Verträglich mit dem Argumenttyp der
// aktuellen Instanz sein (also auch
// Untertyp davon)
// -> nur Lesezugriff auf c
TreeSet(Comparator<? super E> comp) // comperator muss von einer Oberklasse
// von E sein -> nur Schreibzugriff auf comp
}
- Vererbung (Einschlusspolymorphie)
Spezifikation von Datenstrukturen
formale Spezifikation: Deklariert durch Voraussetzung (Precondition) und dem Effekt (Postcondition) und Invariante
Modell: Einfache abstrakte Beschreibung der Daten so wie die Operationen auf diesen, ohne auf die eventuell komplexere Realisierung (Datenstrukur) Bezug zunehmen.
Beispiel: Eine Menge von Strings wird einfach als Liste dargestellt: M = [String]
- abstrakte Invariante: Eventuelle Kapazitätsbeschränkung
- abstrakte Vorraussetzung (Preceondition):
- abstrakter Effekt (Postcondition)
Repräsentation: Die konkrete Darstellung der Daten mit Hilfe einer geeigneten Datenstrukur. Wichtig für eine effiziente, leistungsfähige Implementierung.
Beispiel: Die Menge wird als Verkettete Liste, Stack, oder Queue dargestellt.
- Invariante: Konkrete Invariante => abstrakte Invariante
- Precondition: Abstrakter Vorr. => konkrete Vorraussetzung (es kann in der Implementierung mehr gefordert werden, aber es muss mindestens die abstrakte Vorraussetzung gelten)
- Postcondition: Konkreter Effekt => abstrakten Effekt (die Implementierung darf mehr leisten, aber nicht weniger)
- Abstraktionsfunktion: abs : Rep -> Modell ist also eine Funktion welche aus den konkreten Datenobjekten das zugehörige abstrakte Modell zurückgibt: Beispiel: Sei das Modell eine geordnete Liste, welche mit Hilfe eines Binärbaums implementiert wird, so ist die Abstraktionsfunktion die Funktion welche Alle Knoten des Baums zurückgibt (Traversierung)
Folgen
ADT "Folge"
- Modell: [T]
- Invariante: eventuell Längenbeschränkung
- Operationen unterschiedlich:
Keller | Liste (fkt.) | Schlange | Liste (imp.)
-----------------------------------------------------------------
length | length | length | length, size
empty | empty | empty | empty
push | cons | append | append
| | | insert*
| | | add*
top | head | front | get*
pop | tail | remove | remove*
| cat | | cat
| | | cut*
iterate | iterate | iterate | iterate
----------------------------------------------------------------
Stack<E> | Queue<E> | List<E>
| ArrayList<E>
| Vector<E>
(*eventuell mit Positionsangabe)
- Keller/Stapel (stack)
- Komplexität aller Operationen O(1)
- Anwendung: Spreicherverwaltung, Auswerten von Ausdrücken, Entrekursivierung, u.v.a.
- Entrekursivierung: Umwandlung Rekursion in Iteration
- Schlangen
- Komplexität aller Operationen O(1)
- Repräsentationen
- Feld zyklisch benutzt (Längenbeschränkung!)
- lineares/zyklisches Geflecht einfach verkettet
- Anwendungen: Ressourcenverwaltung, Baum- und Graphtraversierung, Verwaltung realer Warteschlangen, Simulation zeitdiskreter System u.v.a
- Doppelkopfschlagen (double ended queues/"deques")
- hinzufügen und entfernen an beiden Enden
- imperative Listen
- Komplexität teils O(1) teils O(n)
- beliebig manipulierbare Folge mit Positionen 0,1,2...
- Repräsentationen
- wechselnde Felder variabler Länge
- zyklisches Geflecht doppelt verkettet mit innerer Klasse
- Anwendung: Repräsentation "höherer" ADT, Simulation zeitdiskreter Systeme, u.v.a
Traversierung von Folgen
Durchlaufen aller Elemente und dabei mit jedem Element etwas machen (Bsp.: map, foldl, filter)
- Implementierung in Java mit Klasse für Funktion
Traversierung / Iteratoren
externer Iterator
User weiß, in welcher Reihenfolge die Elemente herauskommen
- nicht wiederverwendbar
- Mehrere Iteratoren gleichzeitig einsetzbar
- Änderungen an der Liste kann undefinierten Effekten für den Iterator führen
- flexibler Einsatz für den User
- elegnate Lösung für for-Schleifen in Java: for( T elem : list ) { ...
interner Iterator
Nicht transparent für den User, es wird intern über die Struktur iteriert, um irgendetwas
mit mit den Elementen zu machen
- reguläre Funktion
- sicher & komfortabel
- weniger flexibel als externer
- Beispiel: fold, map
Relationen
Modell:
Menge von Tupeln (Key,Data)
in Pseudo-Haskell: type Rel k d = {(k,d)}
rechtseindeutig: type Rel k d = k -> d
Operationen:
empty, lookup, add, edit, delete, iterate
Representation:
- Hashing
- Bitliste
- binäre Suchbäume
- B-Bäume (2.3-Bäume): Knoten enthalten nur Schlüssen, Daten stehen in den Blättern
Mengen
Modell:
{T} mit Basistyp T. Wenn T linear geordnet ist, dann geordnete Menge
Invariante: eventuell Umfangsbeschränkung
Operationen: add, remove, contains, sowie Schnitt, Differenz, Vereinigung
Repräsentation:
linear:
- unsortierte/sortierte Folge (Feld, linked list)
- Bitfeld
- Streuspeicherung (Hashing)
Bäume:
Unsortierte Folgen:
Komplexität der Operationen:
- contains: O(n)
- add: O(n) für Mengen und O(1) wenn Duplikate zugelassen sind
- remove: O(n)
Sortierte Folgen
:
Für linear geordnete Mengen. Haben eine erweiterte Invariante (Sortierung!)
Komplexität der Operationen:
- contains: O(log n) (binäre Suche, nur für Felder) im Geflecht: O(n)
- add: O(n)
- remove: O(n)
Bitfelder:
Zur Repräsentation natürlicher Zahlen, geignet für kleine Wertebereiche.
Folge von Bits oder boolean[], wobei jede Position i einen Wert x repräntiert, wobei
x genau dann in der Menge enthalten ist, wenn das i-te Bit gesetzt ist.
Komplexität der Operationen:
- contains: O(1)
- add: O(1)
- remove: O(1)
Streusspeicherung (Hashing):
Ähnlich wie Bitfelder nur für beliebige Basistypen. Mittels einer Hashfunktion werden die Daten auf einen definierten Wertebereich abgebildet, welcher den Index im Feld angibt: h(x) = i => x = A[i]
Vorteil: Alle Operationen in O(1)
Hashfunktion
h: T -> [0..M-1] für ein Feld der Größe M, geignet wählen:
- surjektiv
- gleichmäßig Streuend um Kollisionen zu minimieren.
Kollisionsbehandlung (geschlossene Speicherung):
Sondieren:
- Nach Kollision mit h_i(x) neuer Versuch mit h_i+1(x)
- Z.b. lineares Sondieren (h_i(x) = h_0(x) + ci) mod M
- zufälliges sondieren, etc
- Doppelhashing: zweite Hashfunktion einsetzen
- => Komplexität von O(1) wenn keine Kollision auftritt
Kollisionsbehandlung (offene Speicherung):
- Kollision wird zu gelassen, d.h. jeder Feldeintrag der Hashtabelle kann mehre Elemente beinhalten (Bucket)
- Mengenoperation wird dann als Operation auf dem jeweiligen Bucket B_h(x) ausgeführt
- Bucket kann irgendwie implementiert werden, z.b. Feld oder linked List
- => Komplexität hängt von der Implementierung der Buckets ab, aber immer mit Faktor 1/M !
Priority Queues und Heaps
Definition: Schlange mit Entnahme des jeweils "ranghöchsten Element.
Modell:
type PQ r t = [(r,t)] -- Ord r (r: Priorität, t: Daten)
Invariante:
- In der Regel wird die Priorität als durch eine natürliche Ranzahl dargestellt, wobei kleinste Rangzahl ( 0 oder 1) höchste Priorität bedeutet
- in Haskell: inv q = all(>=0)(fst(unzip q))
Operationen:
empty, append, remove, size
Repräsentationen:
- linear als Geflecht oder Feld ( wie Modell)
- Feld von Schlangen für wenige Ränge (z.b.für Scheduler in Betriebssystemen)
- Heaps, ein spezieller Baum
Heaps
Definition: links(vollständiger, partiell geordneter Binärbaum (d.h. jeder Knotenwert ist kleiner oder gleich sein Nachfolger)
Repräsentation:
- linear als Feld mit Breitensuche-Anordnung der Knoten, die Wurzel hat den Index 1
- Anschaulich: Wurzel, alle knoten der ersten Ebene (von links nach rechts), alle Knoten der zweiten Ebende, usw.
- Identifizierung der Knoten x durch Indexrechnung: index(x) = i ⇔ index(left(x)) = 2i ∧ index(right(x)) = 2i+1
Heap als Priority Queue:
- Entfernen: kleinstes Element ist die Wurzel, es wird mit dem letzten eingefügten Element vertauscht
- Hinzufügen: hinten anhängen (links unten)
- Bei beiden Operationen muss anschließend die Heap-Eigenschaft wieder hergestellt werden: dies erfolgt in zwei Phasen:
Bäume
allgemein
- Bäume bestehen aus (Unter-)Bäumen
- n Knotenanzahl, h Höhe, H(n) maximale Höhe mit n Knoten, B(h) maximale Blätteranzahl bei Höhe h
- n ≥ h+1 (da falls Kette : h = n-1)
- N(h) = 2^(h+1)-1
- B(h) = 2^h
- h = ⌈ |log2 (n+1)|) - 1⌉
- Bäume sind verzweigte Folgen. D.h. Operationen auf Bäume sind Operationen auf Folgen
(freie) Bäume sind spezielle ungerichtete kreisfreie zusammenhängende Graphen G(E,K) mit E = Menge der Knoten, K ⊆ E x E Menge der Kanten
(Wurzel-)Bäume (B,w) bestehen aus freien Baum B und Wurzel w. Die Endknoten werden auch Blätter des Baums genannt. Desweiteren sind die Begriffe Vater- und Kindnoten für durch eine Kante verbundene Knoten geläufig.
Begriffe
- Grad: Anzahl der Kinder eines Knoten (= Anzahl der nichtleeren Teilbäume eines Unterbaums)
- Ebene: Stufe eines Knotens (Weglänge von der Wurzel)
- Höhe : maximale Ebene eines Baumes (Ebenenanzahl - 1)
- vollständiger Baum: alle Ebenen sind komlett besetzt (außer eventuell der untersten)
Varianten
(geordneter) Baum
ist definiert als:
- Folge von geordneten Bäumen
- Multimenge von Bäumen
n-ärer Baum (n-Tupel von n-ären Bäumen)
spezielle n-äre Bäume:
- n=1 Kette/Liste
- n=2: Binärbaum
- n>= 3: Vielwegbaum (multi way tree), ungeordnete Bäume
markierte Bäume (labelled tree)
Bäume die Wert in den Knoten speichern
Bsp: B<T> = { (b,m) | b ist Baum mit Eckenmenge E, m : E → T }
unendliche Bäume
Standardmethoden
- height
- nodes
- leaves
- left,right
- add
Traversierung
Sortierung
- Vorordnung/Präordnung (preorder) - Wurzel, linker Baum, rechter Baum
- Nachordnung/Postordnung (postorder) - linker baum, rechter Baum, Wurzel
- Inordnung (nur Binärbaum) (inorder) - linker Baum, Wurzel, rechter Baum
Varianten
- Tiefendurchlauf (depth-first traversal): Traversierung rekursiv durch Traversierung der Teilbäume
- Implementierung mit Hilfe eines Stacks
- Breitendurchlauf (breadth-first traversal): von der Wurzel aus eine Ebene nach der anderen durchlaufen
- Implementierung mit Hilfe einer Queue
Repräsentation
- lineare Repräsentation
- z.B. als Array in pre-,post- oder inorder
- Geflecht
- lineare Abbildung
- viele Baumarten → viele Respräsentationen
Implementierung:
Java
markierter Binärbaum
class Node<T> { // record type, no operations,
// no data abstraction !
// data Bintree t =
// Null | Node t (Bintree t)(Bintree t)
Node(T val, Node<T> l, Node<T> r) {
root = val; left = l; right = r;
}
final Node<T> left;
final T root;
final Node<T> right;
}
Haskell
markierter Binärbaum
data Bintree t = Empty | Node(Bintree t) t (Bintree t)
Graphen
Graph G(E,K) E = Menge der Ecken, K ⊆ E x E = Menge der Kanten
- gerichtet - Relation K ist nicht symmetrisch
- streng zusammenhängend, falls jedes Eckenpaar durch Weg (auch über ander Knoten) verbunden ist
- ungerichtet - Relation K ist symmetrisch (a,b) ∈ K ↔ (b,a) ∈ K
- zusammenhängend, falls jedes Eckenpaar durch Weg (auch über ander Knoten) verbunden ist
- Multigraph - Eckenpaar kann durch mehrere Kanten verbunden sein
- planar - Graph kann in 2-D so angeordnet werden, dass sich keine Kanten überschneiden
- markiert - den Ecken und/oder Kanten ist ein Wert zugeordnet
Weg (path) ist eine Folge von Ecken(e_o bis e_n) mit Länge n
- einfacher Weg - alle Knoten von einander unterschiedlich (außer eventuell e_0 = e_n)
Zyklus - in gerichtetem Graph, n ≥ 2, e_0 =e _n
Kreis - in ungerichtetem Graph, n ≥ 3, e_0 = 3_n
isolierte Ecke - Knoten ohne Kante
(un-)typische Operationen
- typisch: komplexe Algorithmen auf unveränderliche Graphen
- untypisch: Operationen zum Erweitern, Ändern, Abfragen
typische Algorithmen
- Eckensuch: Breiten- und Tiefensuche
- Wegsuche
- existiert ein Weg von a nach b
- (un)günstigster Weg
- alle Wege von a nach b
- Struktur
- zyklisch?
- zusammenhängend?
- minimaler Spannbaum
Repräsentation
- Adjazenzmatrix
- Ecken durchnummeriert (0,1,..n-1))
→ Kanten als Zahlentupel (i,j)
Varianten:
- mit bool'schen Werten: a_{i,j} = (i,j) ∊ K
- kantenmarkierte Graphen: a_{i,j} = ∞ falls (i,j) ∊ K, ansonsten -∞
- Abstrakationfkt:
- Invariante:
- Adjazenzlisten
- jeder Knoten hat eine eigene Adjazenzliste für die Nachfolger
- Geflechte
- Jeder Knoten hat eine Liste von Nachfolgern. Elemente in der Liste repräsentieren die Kanten von dem Knoten
Traversieren und Suchen
- precondition: von Wutzel w alle Ecken erreichbar
Def.: Expansion X(w) des Graphen G=(E,K) ist
- a) w selbst, wenn w keine Nachfolger hat
- b) mit dem Nachfolgern {v_1, v_2,...} der ungeordnete Vielwegbaum (w,{X(v_1),X(v_2),...})
- Achtung! Vielwegbaum ist unendlich, falls G Zyklen oder Kreise enthält!)
- Breitendurchlauf
- Breitendurchlauf von X(w) mit Ignorierung von Unterbäumen, mit bereits besuchter Wurzel
- typischerweise interner Iterator
- Tiefendurchlauf
- Durchlauf von X(w) in Präordnung mit Ignorieren von Unterbäumen mit bereits besuchter Wurzel
- nur wenn Graph kein Baum ist!
Algorithmen
- Wegsuche
- Weg von a nach b: Tiefensuche (Weg aufzeichnen / revidieren)
- alle Wege von a nach b:
- kürzester Weg von a nach b: Dijsktra
- alle kürzesten Wege von a nach b: Floyd
- längster Weg: topologisches Sortieren
- Rundwege:
- Euler-Weg
- Euler-Kreis
- Hamilton-Kreis
- minimaler Spannbaum: Kruskal
Spannbaum
freier Baum mit Kanten aus einem ungerichteten, gewichteten, zusammenhängenden Graphen und allen Ecken aus diesen Graphen
Ein minimaler Spannbaum ist ein Spannbaum mit minimalen Kosten (d.h. Summe der Kantengewichte)
Geometrische Objekte (nicht Klausurrelevanz laut Micha)
Geometrische Objekte finden ihren Einsatz bei Computergraphik, sowie als Modelle für Anwendungsprobleme (Algorithmische Geometrie)
Segment-Bäume
Ein Segment-Baum über X ist ein Binärbaum minimaler Höhe, dessen Blätter die Intervalle (xi, xi+1) tragen. Ein Nichtblatt trägt das Intervall (y,z), das die Vereinigung der Intervalle seiner beiden Kinder ist („Knotenintervalle“).
Abtastalgorithmen
Streckenschnitt-Problem
Finde aus einer Menge mit horizontalen Strecken und einer Menge mit vertikalen Strecken, alle Streckenpaare die sich schneiden.
Algorithmus: Abtasten der Objekte mit einer vertikalen Testgeraden (sweep line) - und zwar schrittweise, unter Berücksichtigung der wesentlichen Ereignisse (sweep event structure):
- linkes Ende einer horizontalen Strecke,
- rechtes Ende einer horizontalen Strecke,
- vertikale Strecke.
Punkt-Einschluss-Problem
Finde zu gegebenen Mengen von Punkten und Rechtecken alle Paare (Punkt, Rechteck), bei denen der Punkt im Rechteck liegt
Algorithmus: Plane Sweep(zwei-dimensional) mit Buchführung über die aktuellen Intervalle, die die Rechtecke auf der sweep line bilden.
Rechteckschnitt-Problem
Finde in einer Menge von Rechtecken alle Paare von überlappenden Rechtecken!
Algorithmus: Für Rechtecke, deren Kanten sich schneiden, wird das Problem auf das Streckenschnitt-Problem zurückgeführt. Wenn ein beliebig gewählter Punkt innerhalb eines Rechtecks a in einem Rechteck b enthalten ist, dann überlappen a und b. → Punkteinschluss-Problem anwenden
Allgemeine Streckenschnitte
Finde aus einer Menge von Strecken, die Streckenpaare die sich schneiden.
Algorithmus: Lösung mit Abtastverfahren (plane sweep): Buchführung von der Folge S aller aktuellen Strecken, die die Testgerade schneiden, linear geordnet (sweep status) gemäß den Ordinaten dieser Schnittpunkte.
Divide and Conquer
Arbeitsspeicherverwaltung (nicht Klausurrelevant laut Micha)
Verwaltendes System | verwalteter Speicher | enthält
-------------------------------------------------------------------------------------------------
Laufzeitsystem | |
| Adressraum |
| Codebereich | Instruktionen
| Keller | lokale Variable
| Halde (heap) | Objekte
--------------------------------------------------------------------------------------------------
Betriebssystem |
| Arbeitsspeicher | Seiten/Segmente
| Externer Speicher | Blöcke
typisches Layout des Adressraums eines Prozesses:
------------ oder ------------
| code | | code |
------------ -------------
| stack | | heap |
------|----- ------------
| | | |
------------ ------|------
| heap | | stack |
------------ ------------
(Stack schreib in den leeren Raum)
Speicherfreigabe
- explizite - Gefahr : Pointer auf schon befreite Speicherzellen
- unterlassene - Speicherleck
- automatische - superb
- Keller - Freigabe nach Verlassen der Methode
- Halde
- Verweiszähler (reference counts)
- Versagen bei Zyklen
- start: c = 1;
- Kopieren des Verweises c++;
- Überschreiben eines Verweises c--;
- wenn 0 löschen
- Speicherbereinigung (garbage collection)
- alle vom Keller aus nicht erreichbaren Objekte werden gelöscht (nebenläufig oder wenn Halde überläuft)
- 2 Phasen
- mark
- ausgehend vom Keller alle erreichbaren Objekte markieren (= Graph-Traversierung!)
- sweep
- löschen nicht markierter Objekte
- Entferunung der Markierungen an anderen Objekten
- in Java:
- jedes Element Methode finalize() wird aufgerufen nachdem Objekt nicht mehr erreichbar ist & direkt vor Löschung des Objekts
- WeakReferences schütze nicht vor Löschung
- aber nützlich bei Caching
- für Schlüssel schwache Verweise einfügen nicht die regulären
- wenn Objekt nicht gefunden wird aus Datei nachladen
- Achtung! Eintrag kann verschwinden beim Nutzen von equals();
- bei einheitlicher Speichergröße
- Freispeicherliste
- einrichten neuer Speicherzelle durch Entnahme des Kopfes der Freispeicherliste
- wenn Freispeicherliste erschöpft → markierung erreichbarer Zellen; alle anderen in neue Freispeicherliste
- unterschiedliche Speichergröße
- Bitliste
- Blockverkettung
- First Fit
- Best Fit
- Worst Fit
- Buddy System
- Größe der Halde ist 2^n
- Best Fit mit eventuellem Splitten eines zu großen Blocks
- viel Verschnitt, dafür sehr schnell
- Zellenverkettung
Verweise:
Zusammenfassung: http://www.inf.fu-berlin.de/lehre/WS09/alp3/folien/alph3-13.pdf