Prächtige Karawanen ziehen durch die weite Wüste Vaubekiens - Datenstrukturen in .NET 2.0

Jeder Entwickler muss irgendwann Mengen von Objekten verwalten. Das Array oder die alte VB-Collection sind dabei die Klassiker doch das .Net Framework bietet viele Klassen, die die Aufgabe besser erledigen. Diese Klassen implementieren gemeinsame Interfaces, die in .Net eine große Rolle spielen.

Auf dieser Seite

	Die Traditionen der Vaubesiks
	Moderne Zeiten
	Zugriff über Index und Key
	Interfaces für die Oasenwärter
	Eigene Collection Klassen und Generics
	Zusammenfassung
	Ressourcen
	Über den Autor

Die Traditionen der Vaubesiks

Die Array Methode

Viele Vaubesiks sind früher mit ihren Karawanen reich geworden. Sie transportieren kostbare Daten vom Volk der Eskuells zu den Völkern der Daus, die in den Steppen rund um Vaubekien leben. Dabei haben sich die Vaubesiks viele Gedanken um die Organisation ihrer Karawanen gemacht.

In der frühen Zeit des Handels wurde das Array-System verwendet. Im Voraus wurde festgelegt, wie viele Kamele an der Karawane teilnehmen, die dann mit Daten beladen werden. Das ist eine einfache und schnelle Variante.

Aber dabei kam es immer wieder zu Problemen, wenn nach der Planung weitere Händler mit Ihren Kamelen an der Karawane teilnehmen wollten. Über die Redim Preserve-Direktive konnte die Karawane zwar vergrößert werden, aber das bedeutete immer eine komplette Reorganisation der gesamten Karawane. Es wurde ein neuer Stellplatz im Speicherhof gesucht und dann wanderten alle Kamele zum neuen Stellplatz und wurden neu aufgereiht. Das verzögerte die Abreise der Karawane erheblich. Vor allem wenn Kamele mit verderblichen Daten dabei waren, wurden die Händler bei dieser Vorgehensweise sehr ungeduldig.

Die alte Vaubekische Collection

Diese Probleme sah auch ein beliebter Wissenschaftler des Vaubesikschen Volksstammes namens Apfelmann, der mit seiner Arbeit immer wieder half, das Leben der Vaubesiks zu verbessern. Er erzählte von der Collection-Methode. Hierbei können einer Karawane mit den Add- und Remove-Kommandos Kamele hinzugefügt oder entfernt werden. Es müssen also nicht mehr alle Kamele in einen neuen Speicherhof laufen, wenn die Anzahl verändert wird.

Außerdem wurden die Kamele nicht nur mit einer fortlaufenden Nummer namens Index verwaltet, sondern bekamen auch einen Namen, der Key genannt wurde, mit dem die Kamele aufgerufen werden konnten.

Leider war die Methode noch nicht ganz ausgereift. So konnte nicht geprüft werden, ob ein Kamel mit einem bestimmten Key teil der Karawane war. Und wenn ein Kamel mit einem bestimmten Key gesucht wurde, so musste der Lademeister vom Anfang der Karawane bis zum Ende durchlaufen, bis er das betreffende Kamel fand oder auch nicht. Und bei hunderten Kamelen konnte das schon ganz schön lange dauern. Wenn er Pech hatte, musste er alle Kamele prüfen, ob sie den gesuchten Namen hatten.

Zum Seitenanfang

Moderne Zeiten

Mit der .Net Reform brachen neue Zeiten für Vaubekien an. Alte vaubesikschen Traditionen wurden in Frage gestellt und die Karawanen mussten immer schneller zusammengestellt werden. Also wurde ein Team von Wissenschaftlern berufen, das neue Wege und Methoden entwickeln sollte. Dabei entstand das heilige Buch des .Net Frameworks. Darin wurden völlig neue Verfahren für das Zusammenstellen von Karawanen vorgeschlagen.

Alle Verfahren sind im .Net Framework in Namespaces aufgeteilt, damit sie leichter zu finden sind. Die meisten der nun folgenden Klassen sind unter System.Collections zu finden. Für die etwas ausgefalleneren gibt es noch System.Collections.Generic und System.Collections.Specialized.

ArrayList

Das Array war an für sich eine schnelle und effektive Datenstruktur, nur bei Veränderungen der Größe gab es Probleme. Nach dem neuen ArrayList-Verfahren müssen nun aber nicht mehr alle Kamele zu einem neuen Stellplatz im Speicherhof wechseln, wenn ein neues Kamel dazu kommt. Die Redim-Direktive ist nicht mehr länger nötig, über Add und Remove können neue Kamele einfach zur Karawane hinzugefügt werden.

Dim Karawane As New System.Collections.ArrayList(500)
Dim k1 As New Kamel("Bananen")
Dim k2 As New Kamel("Bier")
Karawane.Add(k1)
Karawane.Add(k2)
Dim Bier-Kamel As Kamel
Bier-Kamel = Karawane(1)

Wird eine neue ArrayList-Karawane angelegt, so ist standardmäßig erst einmal kein Platz reserviert. Im Constructor-Verfahren könnten gleich 500 Stellplätze reserviert werden, die aber nicht gleich belegt werden müssen. Wird die Anzahl der Stellplätze durch die Add-Methode überschritten, werden automatisch neue Stellplätze reserviert. Wie viele Stellplätze belegt sind, kann ganz normal über die Count-Eigenschaft und die Anzahl der verfügbaren Stellplätze kann über Capacity erfragt werden. Sind zu viele da und werden keine weiteren Kamele mehr erwartet, so kann mit TrimToSize die Menge der teuren Stellplätze der Anzahl der Kamele angepasst werden.

Debug.Print("Anzahl Kamele: " & Karawane.Count)
Debug.Print("Anzahl Stellplätze: " & Karawane.Capacity)
Karawane.TrimToSize()

Zugriff nur über den Index

Dieses Verfahren ist sehr flexibel und sehr schnell. Allerdings können den Kamelen keine Schlüssel bzw. Namen zugeordnet werden. Nur über ihre Position innerhalb der Karawane, den Index, kann auf ein Kamel zugegriffen werden. Dabei beginnt die Zählung immer bei 0! Das geht dann aber sehr schnell, da ja die Position des Kamels im Speicherhof bekannt ist, kann der Karawanenwärter direkt zu einem Kamel gehen, ohne suchen zu müssen.

Alternativ dazu kann die ArrayList mit For Each durchlaufen werden, genauso, wie ein klassisches Array.

HashTable

Nun reicht der Zugriff über die Position in der Karawane nicht für alle Zwecke aus. Das Hauptanliegen der modernen Vaubeken ist der Handel. Auf den langen Handelswegen machen die Karawanen in vielen Oasen Stopp und dort fragen immer wieder Kunden nach bestimmten Waren. Die einen wollen Bier, andere Whisky und wieder andere stehen auf den Klassiker Cola-Korn. Darüber hinaus gibt es noch viele weitere Handelswaren.

Nehmen wir einmal an, dass es in der Karawane für jede Ware genau ein Kamel gibt. Die Vaubesiks wissen zwar die Position eines jeden Kamels innerhalb der Karawane, aber nicht, was das Kamel geladen hat.

Wenn sie das Bier-Kamel suchen, dann haben sie keine Ahnung wo sie anfangen sollen. Sie müssen ganz vorn beginnen und jedes einzelne Kamel abfragen. Bei kleineren Karawanen ist das kein Problem, aber bei den großen, die viele Kunden an entfernten Orten treffen, ist das eine Frage der Zeit. Deshalb haben sie die HashTable-Methode entwickelt.

Zugriff nur über einen Schlüssel

In der alten Vaubesikschen Collection konnte auch schon jedem Kamel ein Schlüssel zugeordnet werden. Wenn aber das Bier-Kamel gesucht wurde, dann mussten im schlimmsten Fall alle Kamele bis zum letzten durchsucht werden und wenn der Kunde durstig und ungeduldig war, konnte das durchaus ein Problem werden.

Deshalb haben sich die Wissenschaftler vom Berechnungstheorie-Team den Hashcode ausgedacht: Wenn eine bestimmte Ware in der Kamel-Karawane gesucht wird, dann sollte man die Position des Kamels in der Karawane über den Schlüssel der Ware finden können, so dass nicht mehr alle abgesucht werden müssen. Mit Hilfe des Key wird ein Hashcode berechnet und mit diesem Hashcode kann dann die Position des Kamels in der Karawane sehr schnell gefunden werden. Im Idealfall kann die exakte Position sogar berechnet werden.

Dim BierKey As String = "Bier"
Dim DattelKey As String = "Datteln"

Dim hashKarawane As New Hashtable()

hashKarawane.Add(BierKey, New Kamel("Bierfass"))
hashKarawane.Add(DattelKey, New Kamel("Dattelbox"))

Dim k As Kamel
k = hashKarawane(BierKey)

Der Schlüssel in einer HashTable kann im Gegensatz zur alten Collection aus einem beliebigen Objekt bestehen, kann also ein Text, eine Zahl oder etwas anderes sein. Wenn wir den Namen einer jeden Ware als Schlüssel annehmen, dann kann ein ganz einfacher so genannter Hashcode aus dem Anfangsbuchstaben der Schlüssels bestehen.

Angenommen wir haben eine Karawane von 100 Kamelen. Und jedes dieser Kamele hat eine Ware geladen. Diese 100 Kamele werden dann nach dem Anfangsbuchstaben ihrer Ware gruppiert.

Wenn ein Kunde Wodka kaufen möchte, dann muss der Karawanenhändler nicht alle Kamele durchsuchen, sondern nur die Kamele der W-Gruppe, die Waren mit dem Anfangsbuchstaben „W“ geladen haben. Das geht dann unter Umständen ganz schnell, wenn an W-Waren nur Whisky und Wodka geladen sind, dann müssen im schlimmsten Fall nur die zwei Kamele, der W-Gruppe, statt der 100 geprüft werden. Ein riesiger Zeitgewinn.

Wenn es aber sehr viele W-Waren gibt, dann ist diese Art des Hashcodes nicht ausreichend und es muss über einen anderen Hashcode nachgedacht werden, mit dem die Kamele in kleine Gruppen eingeteilt werden. Denn das Ideal ist, dass jeder Hashcode genau nur ein Kamel bezeichnet; ist das nicht der Fall, spricht man von „Kollisionen“. Das wussten auch die Wissenschaftler, die das HashTable-Verfahren entwickelten und sie schufen einen guten Standard-Hashcode, der für die meisten Zwecke völlig ausreicht. Nur in Ausnahmefällen wird der Entwickler dort eingreifen müssen.

Kein Zugriff auf die HashTable über einen Index ?

Über einen Index kann leider nicht auf die Hashtable zugegriffen werden. For Each ist der einzige Weg alle Elemente einer HashTable zu durchlaufen. Die Ergebnisse sind dabei oft unerwartet. Angenommen als erstes wird das Whisky-Kamel in die Karawane aufgenommen, dann das Bier-Kamel. Von der Position her ist aber das Bier-Kamel vor dem Whisky-Kamel, weil der angenommene alphabetische Hashcode die Position der Kamele bestimmt und nicht die Reihenfolge des Einfügens in die Karawane, wie bei der ArrayList. Deshalb ist die Reihenfolge der Kamele beim For Each-Zugriff meist anders, als beim Hinzufügen. Dafür ist die Suche nach einem bestimmten Schlüssel sehr viel effizienter, als bei der alten Collection.

In einem Dictionary, wie der Hashtable, werden intern zwei Listen gepflegt. Eine Liste mit den Schlüsseln und eine mit den Werten. Deshalb besteht eine Hashtable aus DictionaryEntry-Elementen und jedes DictionaryEntry-Element verfügt über eine Key- und eine Value-Property.

For Each de As DictionaryEntry In hashKarawane
    Debug.Print("Key:{0}, Value:{1}", de.Key, de.Value)
Next

Wollen Sie hingegen direkt über die Liste der Kamele oder die Liste der Schlüssel iterieren, dann können Sie die Values- und die Keys-Collections verwenden.

For Each k As Kamel In hashKarawane.Values
    Debug.Print(k.Ware)
Next

Aber Achtung bei dieser Variante! Die Elemente der Values-Collection sind vom Typ Object und da könnten sich also über die Add-Methode, die ebenfalls beliebige Objekte akzeptiert, auch Esel oder gar Wüstenhunde in die Karawane reinmogeln, die dann aber gar keine Waren geladen haben. Deshalb wird der Compiler auch einen Fehler melden, wenn Sie die Option Stric On-Direktive verwenden - und das sollten Sie ja immer tun!

Für diesen Fall empfiehlt es sich, eine eigene HashTable oder ArrayList zu definieren, die nur Kamele als Elemente akzeptiert. Dass Vaubeken das oft tun, hat der Bericht über die Generics als Basis für allerlei Container schon beschrieben. Kamelkarawanen und Kleiderständer haben also mehr gemein, als Sie vielleicht bisher angenommen hatten.

Zum Seitenanfang

Zugriff über Index und Key

Als alter Vaubesik ist man es gewohnt, das die Collection einen Zugriff über Index und Schlüssel erlaubt. Um den modernen Vaubeken bei der Reform zu helfen gibt es daher auch nach wie vor die gute alte Vaubesik Collection im .Net Framework, wenn auch etwas versteckt im Microsoft.VisualBasic Namespace.

Dim colGoodOldTime As New Microsoft.VisualBasic.Collection

Die neue/alte Collection bietet die bekannten Funktionen, damit alte Programme leicht in die neue Welt portiert werden können. Und diese alte traditionelle Methode ist von der Performance her gar nicht mal schlecht, wenn ein Zugriff sowohl über Index, als auch über einen Schlüssel, erforderlich ist. Aber sie ist schlechter, als die Hashtable und die ArrayList und sie bietet wenig Komfort. Die ArrayList ist die effizienteste Datenstruktur zum dynamischen verwalten von Objektreferenzen.

Werden sowohl Index als auch Schlüssel benötigt, dann lohnt auch ein Blick auf die SortedList, die beides bietet. Sie ist eine Mischung aus ArrayList und HashTable, aber langsamer als die beiden. Das Einfügen eines Elementes dauert länger, das es an die richtige Stelle der sortierten Liste eingefügt werden muß. Doch die Karawane muss schon viele Kamele haben, damit ein Unterschied zu spüren ist. Dafür bietet sie viele Möglichkeiten auf Elemente zuzugreifen.

Weitere Karawanen-Arten

Neben den etablierten Karawanen gibt es noch etliche exotische. Dazu zählen Queue und Stack, so wie BitArray, StringCollection und andere. Eine Übersicht ist in Tabelle 1 zufinden.

Tabelle 1: Übersicht über die Collection Klassen im .Net Framework

Zum Seitenanfang

Interfaces für die Oasenwärter

Auf ihren Reisen halten die Karawanen in vielen Oasen an, um zu handeln oder einfach nur, um den Tieren eine Ruhepause zu gönnen. In jeder Oase muss sich eine Karawane beim Oasenwärter anmelden. Diese Oasenwärter sind bequeme Menschen, die nicht jeden Tag ein neues Karawanen-System lernen wollen. Deshalb haben sie Standards definiert, die jede Karawane einhalten muss. Diese Standards werden Interfaces genannt und bauen aufeinander auf. Eine Übersicht ist in Abbildung 1 zu finden.

IEnumerable und ICollection

So möchte der Oasenwärter jedes Kamel einer Karawane kurz inspizieren können, deshalb muss jede Karawane das IEnumerable-Interface unterstützen, welches For Each ermöglicht. Außerdem möchte der Wärter erfahren, wieviele Kamele an der Karawane teilnehmen. Deshalb müssen gute Karawanen auch noch das ICollection-Interface implementieren und damit eine Count-Eigenschaft zur Verfügung stellen.

Dim iEnum As IEnumerable
Dim iColl As ICollection

' Erste Karawane: ArrayList
iEnum = arlKarawane
iColl = arlKarawane
Debug.Print("Anzahl Kamele: {0}", iColl.Count)
For Each k As Kamel In iEnum
    Debug.Print(k.Ware)
Next

' Zweite Karawane: HashTable
iEnum = hashKarawane.Values 'sonst werden DictionaryEntrys geliefert!
iColl = hashKarawane
Debug.Print("Anzahl Kamele: {0}", iColl.Count)
For Each k As Kamel In iEnum
    Debug.Print(k.Ware)
Next

In diesem Beispiel werden Variabeln vom Typ IEnumerable und ICollection verwendet um mit For Each oder mit Count auf die Elemente zuzugreifen. So kann der Oasenwärter immer auf die gleiche Art und Weise mit Karawanen umgehen.

Diese beiden Basis-Interfaces implementieren fast alle Collection-Klassen und noch viele weitere Klassen des Frameworks. So kann eine Queue oder ein Stack auch mit For Each durchlaufen werden. Es lohnt sich also, einfach mal einen Blick auf die Basistypen einer Klasse im ObjectBrowser zu werfen. Dann wissen Sie schnell, was eine Klasse kann und was nicht.

Abbildung 1: Die Interfaces der Collection Klassen

IList und IDictionary

An den Interfaces IList und IDictionary scheiden sich die Geister. IList implementieren alle Klassen, die einen Zugriff über einen Index erlauben und IDictionary erlaubt den Zugriff über einen Schlüssel. Werden beide Interfaces implementiert, so wird beides unterstützt und es ist mit Kompromissen bei der Performance zu rechnen, die allerdings bei 1000 Elementen in der Collection noch nicht ins Gewicht fallen.

Beide Interfaces erfordern eine Add-Methode, einmal mit einem Schlüssel und einmal ohne Schlüssel. Darüber hinaus müssen Clear, Remove, Contains und andere Methoden von den Klassen unterstützt werden.

Zum Seitenanfang

Eigene Collection Klassen und Generics

Typisierte Collections

In den Oasen trafen sich Karawanen, die die verschiedensten Waren geladen hatten. Die Wärter konnten auf den ersten Blick nur schwer einschätzen, was ein Kamel geladen hatte, ob es ein Bier- oder ein Sushi-Kamel war. Deshalb kamen typisierte Karawanen in Mode, die immer nur ein Produkt transportieren. Wollte dann ein Händler einem Bier-Kamel Sushi aufladen gab es eine klare Invalid-Cast-Exception, weil die typisierte Karawane die Annahme verweigerte.

Kluge Händler arbeiten nach dem Option Strict-Prinzip, das sie vor dem Beladen warnt, dass das Kamel die Sushi-Rollen nicht transportieren kann. Die Vaubeken haben das von anderen Völner gelernt, aber leider haben sich die Vorteile der frühen Typprüfung noch nicht überall herumgesprochen. Viele versuchen weiterhin einem Bier-Kamel Sushi oder Müsli aufzuladen und bekommen dann während des Marsches zu den Kunden riesige Probleme.

In der Vergangenheit waren zwar viele Programmierer immer wieder einmal mit der Fleißarbeit beschäftigt, eigene typisierte Collection-Klassen zu schreiben – aber die Mühe wurde auch oft gescheut.

Bei einer normalen ArrayList sind alle Elemente vom Typ Object. Der Oasenwärter oder der Händler könnten gar nicht unterscheiden, was die Kamele der Karawane transportieren können. So kam es immer wieder vor, das sich in eine Bier-Karawane auch ein Müsli-Kamel einreihte und keiner hat es gemerkt. Erst als die Karawane dann in der Zielstadt ankam und die Kamele auf die Kneipen aufgeteilt wurden, beschwerten sich einzelne Wirte, das sie statt Bier Müsli bekommen hätten.

Eigene Typisierte Collection Klassen

Im alten Framework, das im Jahr 2003 erschien, war die Erstellung eigener typisierter Collection-Klassen noch recht mühselig:

Imports System.Collections
Public Class BierKarawanenList
    Inherits CollectionBase
    Public Sub Add(ByVal bk As BierKamel)
        Me.InnerList.Add(bk)
    End Sub
    Public ReadOnly Property Item(ByVal x As Integer) As BierKamel
        Get
            Return CType(InnerList(x), BierKamel)
        End Get
    End Property
End Class

Hier wird eine ArrayList definiert, die nur Bier-Kamele aufnimmt. Das ist zwar durch Vererbung schon einfacher als vor der .Net Reform geworden, aber in Zukunft wird es noch leichter gehen.

Generische Collection Klassen

Mit dem neuen .Net Framework 2.0 werden so genannte Generics eingeführt, die an die von C++ seit langem gekannten Templates erinnern. Jetzt wird es wirklich sehr einfach, eigene Collection-Klassen zu implementieren. Das hat nämlich schon jemand generisch getan, denn der Code für eigene Collection-Klassen war doch immer irgendwie gleich. Also haben die Schöpfer des neuen Frameworks generische Collection Klassen geschaffen und nun reicht eine Zeile Code, um sich eine Collection für Bier-Kamele zu definieren, die keine Esel oder gar Müsli-Kamele mehr akzeptiert:

Option Strict On

Dim arlKamel As New System.Collections.Generic.List(Of BierKamel)

arlKamel.Add("Hallo") 'CompileError: Add-Methode verlangt BierKamele!
arlKamel.Add(New BierKamel("Berliner Weiße"))
arlKamel(0).Name = "Hans"

Die generischen Collection-Klassen sind im Namespace System.Collections.Generic zu finden. Dort gibt es für die meisten Collections auch einen generischen Typ. List entspricht dabei der ArrayList und Dictionary der Hashtable.

Bei der Deklaration der generischen Klasse wird das Of-Schlüsselwort zum festlegen des zu unterstützenden Types verwendet. Auch für viele Interfaces existieren generische Partner.

Der große Vorteil ist nicht nur, das bei den Collection-Klassen während der Kompilierung die Typen geprüft werden können und Intellisense auch die Mitglieder der Typen anzeigt, was bei Object-Elementen nicht geht. Bei Collection-Klassen, die keine Objektreferenzen, sondern Wert-Typen wie Integer enthalten entfällt darüber hinaus auch das Boxing in Referenztypen – und damit sind generische Collection-Klassen performanter als ihre untypisierten Vorgänger.

Zum Seitenanfang

Zusammenfassung

Im Bereich des Karawanenwesens hat sich viel gegenüber den alten Vaubesik-Zeiten verändert und es ist endlich ganz einfach eigene typsichere Karawanen zusammen zu stellen. Dabei gibt es verschiedene Möglichkeiten eine Karawane aufzubauen, je nach Anforderung des Kunden.

Wer allerdings das Bier nicht immer in Karawanen umladen, sondern die Waren so weitertransportieren möchte, wie er sie vom Volk der Eskuells erhält, der sollte auch einmal einen Blick auf das mächtige DataSet werfen.

Es bietet viele Möglichkeiten und verhindert den Medienbruch zwischen Resultset der Datenbank und einem Objektmodell.

Zum Seitenanfang

Ressourcen

MSDN Library, Generic Collection Types:
http://msdn.microsoft.com/library/en-us/cpguide/html/cpconwhatiscollection.asp

Marcel Gnoth, Neue Datenstrukturen in .Net,
http://www.gnoth.net/Job/Publikationen.htm

Zum Seitenanfang

Über den Autor

Marcel Gnoth liest leidenschaftlich gern Reisegeschichten und schreibt auch über seine eigenen Reisen. Wenn er in Deutschland ist, dann verdient er sich sein Geld für die Reisen mit der .net Entwicklung bei der Berliner NTeam GmbH. Weitere Informationen finden Sie unter http://www.gnoth.net/ .

Zum Seitenanfang