Grijjy, Inc. Consulting stellt auf GitHub verschiedene Bibliotheken, Komponenten und Quellcode von Klassen, die in ihrer Anwendungsentwicklung zum Einsatz kommen, zur Verfügung. Ein Teil davon bezieht sich auf generische Sets, die in dem folgenden Beitrag beschrieben werden:
„Willkommen zu diesem ersten Beitrag aus einer Reihe über angepasste Sammlungen in Delphi. Diese sind Teil unserer Grijjy-Foundation-Bibliothek von Klassen und Hilfsmitteln, die in unserer Codebasis benutzt werden. Andere Grijjy Repositories sind oft auf diese Bibliothek angewiesen.
Einführung des TgoSet
Haben Sie jemals zwischen der Verwendung einer TList<T> oder eines TDictionary<T> für die Ablage einer Sammlung von Items abgewägt? Sie wollen schnell prüfen, ob die Sammlung ein bestimmtes Item enthält, also würde ein Dictionary sinnvoll erscheinen. Andererseits wollen Sie keine Key/Value-Paare ablegen, sondern nur Items, also wäre eine gewöhnliche List angemessener.
Vielleicht haben Sie dieses Problem durch das Erstellen eines Dictionaries mit einem Dummy-Wertetyp (Wie TDictionary<String, Integer>) und dem Hinzufügen von 0-Werten mit allen Strings „gelöst“. Obwohl dies funktioniert, fühlt es sich irgendwie wie ein Hack an und verschwendet Arbeitsspeicher und Leistung.
Deswegen haben wir ein generisches Set namens TgoSet<T> erstellt. Sie können es in der Grijjy.Collections-Unit finden.
Ein Set ist, wie ein Dictionary, eine Sammlung von unsortierten Items, das Hashing für das schnelle Finden von Items nutzt. Und wie eine Liste speichert es einfach Items ohne Key/Value-Paaren. Anders als in einer Liste ist die Reihenfolge der Items in der Sammlung nicht definiert und auf die Items ist kein Zugriff per Index möglich. Sie können alle Items mit einer for..in-Schleife oder der ToArray-Methode aufreihen.
Simple API
Das Anwenden eines TgoSets ist recht einfach. Das API ist dem eines Dictionaries ähnlich:
|
var Keywords: TgoSet;
|
Die Ausgabe dieses Codes ist:
|
"if" is a Delphi keyword |
Wie Sie sehen ist die Reihenfolge der Items aus der Sammlung undefiniert. Sie entspricht (normalerweise) nicht der Reihenfolge in der die Items hinzugefügt wurden oder einer alphabetischen Sortierung. Wie in einem Dictionary wird die Reihenfolge der Items durch ihre Hash-Codes bestimmt.
Beachten Sie, dass, wie in einem Dictionary, die Add-Methode eine Exception auslöst, wenn das entsprechende Item bereits in dem Set vorhanden ist. Benutzen Sie stattdessen AddOrSet, um das zu vermeiden (Obwohl es ein wenig langsamer ist).
Außerdem können Sie Ihren eigenen Comparer an den Konstruktor übergeben wie bei einem Dictionary, wenn Sie nicht den Standard-Comparer verwenden wollen. Beispielsweise wollen sie das vielleicht tun, wenn Sie Strings prüfen wollen ohne dabei Groß- und Kleinschreibung zu berücksichtigen. Oder wenn Sie eine schnellere Hash-Funktion als die von Delphi bereitgestellte verwenden wollen.
Andere Set-Typen
Wenn Sie sich den Sourcecode des TgoSet<T> ansehen, werden Sie feststellen, dass es von TgoReadOnlySet<T> abgeleitet ist. Das bedeutet, dass Sie eine schreibgeschützte Ansicht des Sets als Eigenschaft oder Parameter Anzeigen können, sodass andere das Set nicht versehentlich ändern können.
Wie mit anderen Sammlungen in Delphi gibt es auch hier eine Version in der nur Objekte abgelegt werden können und die automatisch den Besitz über diese Objekte übernimmt. Diese Version, TgoObjectSet<T>, zerstört seine Objekte, wenn das Set zerstört oder gecleart wird oder Objekte aus dem Set entfernt werden. Um ein Objekt zu entfernen ohne es zu zerstören, kann das Extract API verwendet werden.
Wie ein Set funktioniert
Ein Set ähnelt am ehesten einem Dictionary ohne Values. Wir können also damit beginnen, TDictionary<TKey, TValue> anzuschauen und allen Value-bezogenen Code zu entfernen. Delphis Dictionary wird mit Hashtabellen und linearer Sondierung zur Auflösung von Kollisionen implementiert. Wir benutzen das gleiche Modell in unserem Set.
Unsere Hashtabelle ist lediglich ein dynamisches Array von TItem-Records:
| type TgoReadOnlySet = class(TEnumerable) private type TItem = record HashCode: Integer; Item: T; end; private FItems: TArray; ... end; |
Ein TItem speichert seinen Wert und Hashcode. Die Länge der Hashtabelle (FITems) ist immer eine Zweierpotenz.
Das Hinzufügen eines Items besteht aus folgenden Schritten:
- Berechne den Hashcode für das Item (Mit IEqualityComparer<T>.GetHashCode).
- Wandle den Hashcode in einen Index der Hashtabelle um. Da die Länge der Hashtabelle immer eine Potenz von Zwei ist, können wir den Hashcode mit einem logischen and mit der Länge der Hashtabelle minus 1 verbinden.
- Finde das entsprechende Item in der Hashtabelle. Wenn es leer ist können wir unser Item dort ablegen. Ansonsten wird der Index immer weiter erhöht, bis ein leeres Item gefunden wird (Das ist der lineare Sondierungsteil).
Als Code sieht das so aus:
|
procedure TgoSet.Add(const AItem: T);
|
Als erstes prüfen wir, ob die Hashtabelle erweitert werden muss. Das tun wir, sobald die Hashtabelle zu 75% voll ist. Zu diesem Zeitpunkt ist die Chance für Hashkollisionen groß genug, um eine Erweiterung zu erfordern.
Beachten Sie außerdem, dass wir den Hashcode per and mit $7FFFFFFF verbinden. Das befreit im Grunde den Vorzeichenbit, was den Code nichtnegativ macht. Dies ist nötig, da der Hashcode -1 (EMPTY_Hash) für das Angeben eines leeren Hashtabelleneintrags reserviert ist.
Die while-Schleife führt das lineare Sondieren durch, um leere Einträge in der Hashtabelle zu finden. Falls in der Hashtabelle bereits ein Eintrag mit dem gleichen Hashcode existiert, benutzen wir IEqualityComparer<T>.Equals um das Item mit dem zu vergleichen, das wir hinzufügen wollen. Sollten beide gleich sein, wird eine Exception ausgelöst, da doppelte Items in einem Set nicht erlaubt sind.
Dies sind die Grundlagen für die Implementierung einer Hashtabelle in einer Sammlung. Natürlich muss auch, falls nötig, für die Erweiterung des Sets und das Entfernen von Items gesorgt werden. Sollten Sie Interesse an den hier verwendeten Algorithmen haben, schauen Sie doch in den Quellcode. Er sollte nicht schwierig zu folgen sein, wo Sie jetzt wissen, wie die Hashtabelle aufgebaut ist.“
Nach dem Originalpost „Expand your Collections collection – Part 1: a generic Set“, von Erik van Bilsen auf http://www.grijjy.com/, 05.01.2017. Übersetzung von Nils Eilers.
