Projektskizze

ACF - Advanced Collection-Framework

01.10.2002 - 30.05.2003

Das gesamte Projekt wurde alleinverantwortlich durchgeführt.

Zur Implementierung von Echtzeitsystemen sind hochgradig effiziente Datenstrukturen erforderlich. Datenstrukturen des JDK genügen diesem Anspruch nicht, so dass zur Vorbereitung zukünftiger Projekte die Implementierung eines eigenen Collection-Frameworks ACF nötig ist:

konsistentes Design
Nicht alle tatsächlichen Collections des JDK besitzen die im Collection-Interface definierten Schnittstellen. Diverse Methoden, die für die jeweilige Datenstruktur nicht realisierbar sind, lösen daher beim Aufruf eine Exception vom Typ "UnsupportedOperation-Exception" aus. Dieser Designansatz ist äußerst fragwürdig.*
Das Design von ACF orientiert sich an den in der Informatik etablierten Definitionen abstrakter Datentypen (ADT). Bei entsprechend modularer Architektur implementiert jede Datenstruktur ausschließlich Schnittstellen, die der jeweilige Algorithmus effizient unterstützt. Dadurch ist eine ungeschickte oder fehlerhafte Benutzung des API ausgeschlossen.
performante Implementierung
Für die JDK-Collections wurde die jeweils einfachste Implementierung gewählt. In den meisten Fällen bedeutet das den Verzicht auf eine performante Implementierung.*
Das ACF stellt effizientere Implementierungen bereit. So wird hier beispielsweise ein dynamisches Hashverfahren unterstützt, das dem derzeitigen Wissensstand der Informatik entspricht.
Bereitstellen aller wichtigen Datenstrukturen
Vielfach wird die geringe Vielseitigkeit der JDK-Collections kritisiert.* Nur wenige der wichtigsten abstrakten Datentypen stehen als JDK-Collection zur Verfügung.
Das ACF beinhaltet eine Reihe komplexerer Datenstrukturen. So unterstützt ein AVL-Tree die effiziente Suche in einer ausgeglichenen Baumstruktur, ein Heap dient als Prioritätswarteschlange und ein Suffix-Trie ermöglicht performantes Verwalten von Strings.

API

Das API des ACF hat folgende Eigenschaften:

Konsistenz der Strukturen
Ein Update-Handling ermöglicht es der jeweiligen Datenstruktur, selbständig auf Änderungen an seinen Elementen zu reagieren und die Struktur konsistent zu halten. Es ist zum Beispiel möglich, ein Objekt in verschiedenen sortierten Listen zu speichern. Das für die Sortierreihenfolge relevante Attribut (Membervariable) des Objekts könnte sich zur Laufzeit ändern. In allen Listen wird in diesem Fall das geänderte Objekt an die neue, der korrekten Sortierreihenfolge entsprechende Position verschoben. Die Datenstrukturen sind damit adjustiert und konsistent.
Persistenz
Die Datenstrukturen implementieren Schnittstellen, welche die Verwendung diverser Persistency-Frameworks ermöglichen. Die konkrete Persistenzlösung agiert dabei im Hintergrund, so dass die Benutzung des API einfach bleibt.
Zugriff durch mehrere Benutzer
Ein Iterator-Konzept wie im JDK erlaubt die Mehrfachbenutzung der selben Datenstruktur. Die Datenstruktur kann von mehreren Iteratoren unabhängig voneinander durchlaufen werden.
Thread-Sicherheit
Das Durchlaufen der Datenstruktur, das Einfügen neuer Elemente und das Löschen von Elementen ist thread-sicher.
Generische Typen
Auf die Elemente der Datenstrukturen wird generisch zugegriffen. Minimaler Mehraufwand beim Implementieren erspart beim Zugriff auf die gespeicherten Elemente das aus dem JDK bekannte Casting. Rückgabewerte von Zugriffsmethoden sind bei solchen Datenstrukturen nicht einfach vom Typ der Basisklasse "Object", sondern entsprechen dem konkreten Typ der eingefügten Objekte. Die Datenstrukturen sind typsicher.

ADT

Das Verhalten der Datenstrukturen wird gemäß der verbreiteten Konvention jeweils als ADT (abstrakter Datentyp, abstract datatyp) spezifiziert. ACF stellt für die folgenden ADTs mehr als eine konkrete Implementierung zur Verfügung.

Search Tree: AVLTree, BinaryTree
Trie: Trie, SuffixTrie
Hash Table: HashTable (Hashing nach dem Divisionsverfahren, dynamische Behandlung von Kollisionen)
Priority Queque: ArrayHeap, LinkedHeap, FibonacciHeap
Queque: ArrayQueque, LinkedQueque
Stack: ArrayStack, LinkedStack
sorted List: ArrayList, LinkedList, BinaryArrayList (binärer Zugriff auf Listenelemente)

Ausblick

Bereits jetzt stehen im ACF alle wichtigen Datenstrukturen bereit, die zur Implementierung fundamentaler Algorithmen aus bekannten Problemklassen benötigt werden. Trotzdem wird ACF fortlaufend um neue Datenstrukturen erweitert.
Die Integration eines Persistency-Frameworks erspart die zweckfremde Verwendung von relationalen Datenbanksystemen zur bloßen Sicherung der Persistenz. Dadurch wird die Software-Entwicklung in diesem Bereich wesentlich effektiver.
Dass verfügbare Collection-Frameworks gewisse Schwächen aufweisen, gilt nicht nur für die Sprache Java. Die Gestaltung des ACF ermöglicht eine einfache Portierung auf die meisten anderen objektorientierten Sprachen. Für .Net wird bald eine Implementierung von ACF in C# bereitstehen.

* Vgl. Guido Krüger, Handbuch der Java-Programmierung, Addison-Wesley, 2002, Kapitel 15