Hash und Tree Implementierungen

Ich gehe mal davon aus, dass der Leser die Collection Interfaces List, Set und Map kennt. Reden wir doch mal ein bisschen über Sets:

Set fruit = new HashSet(); fruit.add("Apple"); fruit.add("Orange"); fruit.add("Banana"); fruit.add("Cherry"); System.out.println(fruit); 

[Apple, Orange, Banana, Cherry]

Soweit, so gut. Was aber, wenn wir die Früchte alphabetisch sotiert haben wollen? Das erreichen wir ganz einfach, indem wir statt einem HashSet ein TreeSet benutzen:

Set fruit = new TreeSet(); 

[Apple, Banana, Cherry, Orange]

Warum funktioniert das? Weil im zweiten Fall die Implementierung den Inhalt des Sets in einer Baumstruktur speichert, und damit garantiert, dass Einträge in log(n) gefunden werden können. Beim HashSet hingegen kann die Performanz an die Bedürfnisse gut angepaßt werden, indem beim Instantiieren die Anzahl der “Buckets” der Anwendung entsprechend gesetzt wird.

Im allgemeinen sind die Hash-Funktionen schneller, aber ein sortiertes Set zu haben, kann unbezahlbar sein. Ein paar Dinge sind zu beachten: Elemente im TreeSet müssen Comparable implementieren, sonst wird eine Exception geworfen. Außerdem kann ein HashSet null enthalten, TreeSet nicht.

Initialisierung

In dem Beispiel weiter oben wollen wir vier Früchte in unserem Set haben. leider können wir diese nicht dem Konstruktor mitgeben. Aber mit einem Trick wir können eine Klasse ableiten, die diese Werte in das Set einträgt:

Set fruit = new TreeSet() {{ add("Apple"); add("Orange"); add("Banana"); add("Cherry"); }}; 

Collections Klasse

die Collections Klasse wird oft übersehen, enthält aber einen Haufen unglaublich pratischer statischer Methoden. Diese fallen in die folgenden Kategorien:

Such- und Sortierfunktionen: Kleinstes und größtes Element, oder gleich die ganze Liste sortieren, und mit bestimmten Suchalgorithmen ein Element finden. Es können auch gezielt nur bestimmte Teile einer Liste durchsucht werden.

Kopieren, ersetzen, verdrehen: Collections können per Zufall vermischt werden, Kopien erstellt werden, oder mit einem bestimmten Objekt viele Male gefüllt werden.

Wrapping: Eine unmodifizierbare oder synchronisierte Version einer Collection können erzeugt werden. Besonders das Wrapping ist extrem nützlich. Wenn eine Funktion ein Set zurückgibt, das nicht verändert werden darf, kann das entweder dokumentiert werden (kann ignoriert werden), oder ein neues Set kann erzeugt werden:

return new TreeSet(fruit); 

Oder, die beste Lösung, wir geben ein nicht modifizierbares Set zurück:

return Collections.unmodifiableSet(fruit); 

Anfragen an das zurückgegebene Set werden an das interne Set weitergegeben – aber jeder Versuch, das Set zu ändern, wirft eine UnsupportedOperationException. Das war’s für heute! Zum Abschluß möchte ich noch herzlich den Collections Framework Overview empfehlen, der noch weiter auf die Philosophie der Architektur eingeht. Viel Spaß beim Lesen!