Unsere Datenschutzrichtlinie wird in Kürze aktualisiert. Bitte sehen Sie sich die Vorschau an.

Grundlagen der Programmierung: Datenstrukturen

Sets

Testen Sie unsere 2016 Kurse

10 Tage kostenlos!

Jetzt testen Alle Abonnements anzeigen
Ein Set ist eine unsortierte Sammlung von Objekten. Es gibt in einem Set keine Duplikate und es eignet sich insbesondere, um die Mitgliedschaft eines Objekts in einer Sammlung zu kontrollieren.

Transkript

Machen Sie sich bewusst, dass manche Datenstrukturen in Ihrer Sprache nicht enthalten sind. Oder zumindest nicht als Teil der Standardbibliothek. Sie müssen sich möglicherweise mit einem anderen Framework verlinken, normalerweise mit dem von Drittanbietern. Oder Sie können sie eventuell sogar selbst schreiben. Aber nun zu einer Datenstruktur, die fast sicher in Ihrer Sprache existiert. Die Idee eines Sets. Sets sind sehr einfach anzuwendende Datenstrukturen. Möglicherweise die einfachste verwendbare Datenstruktur überhaupt. Aber um zu verstehen, wie sie funktionieren, hilft es, dass wir bereits Strukturen wie verlinkte Listen und Hash-Tabellen kennengelernt haben. Ein Set ist eine ungeordnete Sammlung von Objekten. Was heißt das? Denken Sie einfach an einen großen Behälter, in den Sie einen Haufen Objekte geben können. Das ist ein Set. Mit unsortiert meine ich, dass es keinen Index gibt wie bei einem Array. Es gibt keine spezielle Reihenfolge wie in einer verlinkten Liste, einem Stack oder einer Queue. Es gibt keinen Schlüssel wie bei einer Hash-Tabelle. Es ist nur ein Haufen Objekte ohne bestimmte Reihenfolge. Sie denken sich vielleicht, dass das sehr einschränkend klingt. Da haben Sie völlig recht. Es ist absichtlich sehr einschränkend. Wozu das gut sein soll? Der erste Grund: Im Gegensatz zu einem Array oder zu einem assoziativen Array oder einer verlinkten Liste gibt es in Sets keine Duplikate. Sie können nicht dasselbe Objekt ein zweites Mal zum Set hinzufügen. Und nun der zweite Grund. Sets wurden designt, um sehr schnell nachschauen zu können, um sehr schnell sehen zu können, ob es ein bestimmtes Objekt in der Sammlung bereits gibt oder nicht. Dies wird oft Kontrolle der Mitgliedschaft in einer Sammlung genannt. Wenn wir also ein Objekt haben egal ob einen String oder einen Dateinamen oder ein Mitarbeiterobjekt, und wenn wir wissen wollen, ob wir dieses Objekt in einer bestimmten Sammlung haben, dann ist es sehr schnell, in einem Set danach zu suchen. Allerdings unter der Oberfläche verwendet ein Set meistens eine Hash-Tabelle. Aber anstatt ein Schlüsselobjekt zu hashen, um ein separates Wertobjekt zu speichern, verwenden Sie ein Set und das ist das Schlüsselobjekt. Und das ist das Wertobjekt in einem. Ich nehme also das Objekt, so wie es ist, lasse es durch die Hash-Funktion laufen, lege es dann in der Tabelle ab und ich lege das Objekt selbst in dieser Tabelle ab. Ich kann diesen Vorgang auch jederzeit wiederholen. Dann kommt ein anderer Hash-Wert heraus und ich lege es wieder in der Tabelle ab. Wenn ich also die Mitgliedschaft kontrollieren möchte, um herauszufinden, ob wir etwas über dieses eine spezielle Objekt wissen, dann wiederholen wir diesen Prozess einfach. Üblicherweise wäre das etwas wie eine Contains-Methode, die wir mit dem Set aufrufen können. Wenn also mein Set-Objekt eins beinhaltet, dann lassen wir's wieder durch die Hash-Funktion laufen, nehmen den Index und schauen an diesem Ort nach, ob das Objekt dort bereits existiert. Es ist also eine sehr einfache Art des Nachschauens, ob ein spezielles Objekt in einer Sammlung existiert. Aber es ist auch sehr leicht, davon eine falsche Vorstellung zu bekommen. Sets unterstützen ein schnelles Nachschauen, aber wir würden ein Set nie zum direkten Indexieren eines speziellen Objekts verwenden. Und dieses dann wiederbekommen. Weil das gar keinen Sinn machen würde. Um nämlich direkt zu einem bestimmten Objekt in einem Set zu gelangen, müssen Sie das Objekt ja schon haben. Denn das ist die einzige Möglichkeit, an den Index heranzukommen. Die einzige Art, das zu tun, ist also, nach der Mitgliedschaft zu fragen, um die Existenz in der Sammlung zu klären. Habe ich dieses Objekt bereits? Habe ich dieses Produkt in der Liste der Produkte? Habe ich diese Person in der Liste meiner Angestellten? Aber es ist nicht dazu da, einen Wert wiederzubekommen. Wie auch immer. Wenn Sie wieder alles aus dem Set herausbekommen wollen, dann ist das völlig in Ordnung. Und es ist vor allem eine andere Geschichte. Ebenso können Sie durch alle Elemente eines Sets iterieren, das ist ausgesprochen annehmbar. Sie können nur mit keiner garantierten Reihenfolge arbeiten. Ein Set ist also eine ungeordnete Sammlung an Objekten. Es hat keinen Index, es hat keine Reihenfolge oder auch keinen Schlüssel. Und der Vorteil: Es unterstützt keine Duplikate. Aber es unterstützt 'das schnelle Nachschauen, ob ein spezielles Objekt existiert. Wir kontrollieren eine Mitgliedschaft in der Sammlung. Und wir können alles aus dem Set wieder herausbekommen. Wir wollen es nur nicht dazu verwenden, um zu einem bestimmten Element in dem Set zu gelangen. Und wenn Sie irgendein anderes Verhalten als dieses brauchen, dann ist es einfach nicht die beste Datenstruktur für diese Aufgabe. Nun ... Sets sind eine von den unterschiedlichen Programmiersprachen sehr gut unterstützte Datenstruktur. Es ist viel einfacher, Sets zu verwenden, als viele andere Strukturen. Ruby hat Sets. Python unterstützt Sets und Frozen Sets. Das ist sogar noch effizienter. Wenn Sie Ihr Set einfrieren können, was, so wie's klingt, einen Weg darstellt, das Set nach der Erzeugung unveränderbar zu machen. Mit einer vergleichbaren Idee haben wir in Objective C NSSet, welches eingefroren ist, und NSMutableSet, zu dem man noch Elemente hinzufügen kann, nachdem es angelegt wurde. In Java: set ist ein Interface, wie list und queues. Und die einfachste Set-Klasse ist das HashSet, welches, wie Sie sich vorstellen können, anzeigt, dass es eine Hash-Tabelle verwendet, um ein Set anzulegen. Ebenso hat C# ein HashSet. Und in C++ gibt's einen Set-Container in der Standardvorlagenbibliothek. Obwohl interessanterweise in C++ Sets nicht mit Hash-Tabellen implementiert werden, aber das ist eine andere Geschichte.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!