Lernen Sie Ihre Codierungsgrundlagen kennen: die Hauptunterschiede zwischen Sets und Arrays

Eine Frage, die ich von meinen CS-Schülern bei The Forge häufig bekomme, ist, warum ich bei Interviewproblemen häufig Sets anstelle von einfachen alten Arrays verwende.

Um diese Frage zu beantworten, müssen wir die grundlegenden Unterschiede zwischen einer Menge und einem Array verstehen.

Wenn Sie visuell lernen und eine Videoerklärung bevorzugen, finden Sie hier ein 3-minütiges Video, in dem die Antwort erklärt wird (wenn auch in geringerer Tiefe).

Arrays waren eine der ersten Datenstrukturen, deren Verwendung ich gelernt habe.

Sie sind nicht nur eine grundlegende Datenstruktur, die in fast jeder Codierungsanwendung verwendet wird, sondern auch ziemlich einfach zu verstehen.

Erst viel später in meiner Software-Karriere wurde ich mit dem seltsamen, aber magischen Cousin des Arrays bekannt gemacht:

Der Satz.

Sets sind wie Arrays… außer sie sind es nicht.

Erinnern wir uns schnell daran, wie ein Array funktioniert

Arrays:

  • Sind bestellt
  • Indizes beginnen bei 0
  • Kann doppelte Elemente enthalten
  • Haben Sie eine O (n) Suchzeit, wenn Sie nach einem Element suchen

Sets verhalten sich jedoch etwas anders

Sets:

  • Sind ungeordnet (in fast allen Sprachen)
  • Habe Indizes gehasht
  • Darf KEINE doppelten Elemente enthalten
  • Haben Sie eine O (1) Suchzeit, wenn Sie nach einem Element suchen

Schauen wir uns das genauer an.

1. Setzt Insert By Hashing

Die Elemente in einer Menge werden ganz anders gespeichert als die eines Arrays.

Die Art und Weise, wie ein Set seine Elemente speichert, ist durch Hashing.

Angenommen, Sie möchten das Zeichen "A" in einem Satz und einem Array speichern.

Das Array würde einfach den nächsten verfügbaren Index finden, sofern nicht anders angegeben, und das Element in diesen Index einfügen.

Beim Hashing sehen die Dinge jedoch etwas anders aus.

Wie Hashing funktioniert

Beim Hashing wird die Eingabe (x) aufgenommen, mit einer bestimmten Hash-Funktion (h) verzerrt und eine endgültige Ausgabe (y) erhalten.

Grundsätzlich ist h (x) = (y)

Sieht ein bisschen verwirrend aus, oder?

Mach dir keine Sorgen! Dies sollte die Dinge klären.

Ein einfaches Beispiel für eine Hashing-Funktion (h) könnte das Anhängen von "asdf" an das Ende Ihrer Eingabe (x) sein.

Wenn (x) "A" ist und das Anhängen von "asdf" (h) ist, wäre die Ausgabe (y) einfach wie folgt:

"A" + "asdf" → "Aasdf"

"Aasdf" wäre also unser (y).

Wie verwendet ein Set Hashing?

Ein Set verwendet Hashing, um zu entscheiden, wo Ihre Eingabe gespeichert werden soll (x).

Kurz gesagt, eine Menge nimmt Ihre Eingabe, hasht sie und speichert sie im Index, der mit der Hash-Eingabe übereinstimmt, AKA mit der Ausgabe (y).

Dies ist der Grund, warum Sets in den meisten Sprachen ungeordnet sind.

Die Array-Indizierung ist einfach (0 bis n), sodass Sie sich leicht merken können, was als Nächstes kommt.

Bei den komplexen Hashing-Funktionen, die die meisten Compiler verwenden, kann die Reihenfolge, in der die Elemente eingefügt wurden, nur gefunden werden, wenn Sie einen sekundären Indizierungsmechanismus beibehalten.

2. Sets dürfen keine Duplikate enthalten

Korrekt!

Ein Set kann nur eindeutige Elemente enthalten.

Im Gegensatz zu dem, was sich anhört, kann dies in vielen Situationen, einschließlich Google Interview-Fragen, äußerst hilfreich sein.

Warum macht es das, fragst du?

Nun, wegen Hashing!

Da meine Hashing-Funktion (h) während der Ausführung meines Programms konsistent bleibt, erhalten Sie durch Eingabe derselben (x) immer dieselbe (y).

Das heißt, wenn ich versuchen würde, ein zweites "A" einzufügen, würde meine Hashing-Funktion dieselbe Adresse wie das erste "A" ausgeben und sie einfach überschreiben!

Bei einem Array wird einfach das zweite „A“ an den nächsten verfügbaren Index angehängt.

3. Sets haben eine O (1) Suchzeit

Angenommen, Sie haben ein Array von n Elementen, wobei n eine große Zahl ist, und Sie wollten sehen, ob in diesem Array „A“ vorhanden ist.

Nun, im schlimmsten Fall existiert "A" nicht.

Und um das herauszufinden, müssten Sie alle n dieser Elemente durchlaufen !

Dies gibt einem Array eine zeitliche Komplexität von O (n), wenn es darum geht, ein Element nachzuschlagen.

Mit einem Set können wir viel Zeit sparen

Wenn wir herausfinden wollten, ob ein Element in unserer Menge vorhanden ist oder nicht, müssen wir nur dieses Element hashen und den Index überprüfen!

Denken Sie daran: Der Index, in dem ein Element gespeichert ist, ist mit dem Element selbst verbunden.

Wenn wir also sehen wollten, ob "A" in unserem Set vorhanden ist oder nicht, müssten wir es einfach hashen (+ "asdf") und diesen Index überprüfen!

Da dieser Prozess immer eine konstante Anzahl von Operationen erfordert, egal wie groß die Menge ist, hat er eine konstante zeitliche Komplexität.

Das bedeutet, dass eine Menge eine zeitliche Komplexität von O (1) hat, wenn es darum geht, ein Element nachzuschlagen… Was eine enorme Verbesserung darstellt!

Können Sie sich Situationen vorstellen, in denen dies nützlich ist?

Wenn Sie nicht können, lesen Sie diese Google Interview-Frage, in der ein Set den Unterschied ausmacht!

Danke fürs Lesen!

.ein

PS - Weitere Tutorials zu Datenstrukturen und Algorithmen sowie zur Vorbereitung von Interviews finden Sie unter www.TheForge.ca!

Wir helfen Studenten und neuen Absolventen, ihren Traumjob in der Software zu finden!