Vorlesung Informatik 2 - Teil B: Theorie
3.5 Assoziative Listen
Bisher haben wir mit indizierten Listen gearbeitet: Arrray, LinkedList. Dabei wird über einen Index (meist von 0 bis n-1) auf die Daten zugegriffen.
Im Gegensatz dazu erlaubt eine assoziative Liste (Map) den Zugriff über einen Schlüssel, d.h. jeder Eintrag in der Liste besteht aus einem Wert (Value) und einem Schlüssel (Key).
Beispiele;
Key Value
Postleitzahl Stadt
Matrikel-Nummer Student
Name Telefonnummer
Eine Assoziative Liste hat zwei Methoden:
put(key, value): speichert value unter dem Schlüssel Key
get(key) : sucht den Wert zum Schlüssel Key.
In Java gibt es das Interface java.util.map<K,V>:
put(key: K, value:V):V Speichert oder ersetzt value unter dem Schlüssel key,
get(key: K): V Liefert den Wert zu key oder null,
remove(key:K):boolean löscht den Aintrag zu key,
replace(key:K, value:V): boolean ersetzt den Wert zu key.
Zum Map Interface gehören noch weitere Methoden die hier nicht aufgeführt sind.
Es gibt zwei Implementierungen, die wir uns genauer ansehen werden:
- HashMap: basiert auf einer Hashtabelle, wird im nächsten Kapitel behandelt. Kann im besten Fall O(1) liefern.
- TreeMap: nutzt einen Suchbaum, den wir später kennenlernen. Garantiert O(log N).