Implementierungen der Set- und Queue-Schnittstellen

„Na, wie geht es deinem Prozessor?“

„Es ist in Ordnung. Ich habe eine Stunde lang in flüssigem Stickstoff gesessen, also bin ich jetzt so gut wie neu!“

„Großartig. Dann lass uns weitermachen.“

„Sammlungen festlegen.“

Mathematisch gesehen ist eine Menge eine Gruppe einzigartiger Elemente. In der Programmierung ist ein Set also eine Sammlung einzigartiger Elemente, also eine Sammlung, die es nicht zulässt, identische Elemente zu speichern.

„Ich weiß nicht, ob Ellie dir Sets Vererbungshierarchie gezeigt hat. Wenn nicht, hier ist sie:“

„Ein HashSet ist eine Sammlung, die Elemente intern unter Verwendung der von der hashCode ()-Methode zurückgegebenen Hash-Werte speichert.“

„Der Einfachheit halber speichert HashSet<E> ein HashMap<E, Object>-Objekt, das die Werte des HashSets als Schlüssel speichert.“

„Wow!“

„Durch die Verwendung von Hash-Codes können Sie schnell nach Elementen suchen, Elemente hinzufügen und daraus entfernen.“

„Bedenken Sie jedoch, dass Ihre Klasse die Methoden hashCode & equal richtig implementieren muss , um Objekte Ihrer Klassen zu einem Set hinzuzufügen und sie dort korrekt zu finden.“

„Beide Methoden werden häufig in HashSet/HashMap verwendet. “

„Wenn Sie vergessen, die Methode hashCode () zu implementieren , besteht die Gefahr, dass Sie Ihr Objekt nicht im Set finden, selbst wenn es vorhanden ist.“

„Ja, ich erinnere mich, ich erinnere mich. Du hast mir vorhin davon erzählt. Ich habe alles darüber gehört.“

„Okay. Dann sind hier noch einige weitere nützliche Informationen für Sie.“

„Angenommen, Sie haben hashCode und equal  in Ihrer Klasse korrekt implementiert und speichern Ihre Objekte gerne in einem Set.“

„Aber dann ändern Sie eines der Objekte und ändern dadurch die internen Daten, die zur Berechnung seines Hashs verwendet werden . Der Hash des Objekts ändert sich also.“

„Und das bedeutet, dass Sie es wahrscheinlich nicht finden werden, wenn Sie im Set danach suchen.“

„Wow! Wie funktioniert das?“

„Dies ist eine bekannte Falle bei der Arbeit mit Hashes. Im Wesentlichen funktioniert die Suche nach HashSet (und HashMap) nur dann garantiert ordnungsgemäß, wenn die Objekte unveränderlich sind .“

„Whoa! Und was, niemand unternimmt etwas dagegen?“

„Jeder tut so, als gäbe es das Problem nicht. Aber das kommt in Interviews häufig zur Sprache, daher lohnt es sich vielleicht, daran zu denken …“

„Ein LinkedHashSet ist ein HashSet, dessen Elemente auch in einer verknüpften Liste gespeichert sind. Normale HashSets unterstützen keine Reihenfolge der Elemente. Erstens handelt es sich einfach nicht um eine offizielle Operation. Zweitens kann sich sogar die interne Reihenfolge erheblich ändern, wenn ein einzelner Element wird hinzugefügt.“

Sie können jedoch einen Iterator aus einem LinkedHashSet abrufen und damit alle Elemente in der Reihenfolge durchgehen, in der sie dem LinkedHashSet hinzugefügt wurden . Das passiert nicht oft, aber manchmal ist es sehr nötig.“

„Ich verstehe. Ich liebe es, wenn es Kurse für diese „nur für den Fall“-Szenarien gibt. Solche Fälle sind gar nicht so selten.“

„ TreeSet ist eine Sammlung, die Elemente in Form eines nach Werten geordneten Baums speichert. Ein TreeSet <E> enthält eine TreeMap <E, Object>, die alle diese Werte speichert. Und diese TreeMap verwendet einen ausgeglichenen rot -schwarzen Baum zum Speichern Elemente . Daher unterstützt es sehr schnelle Operationen zum Hinzufügen, Entfernen und Enthalten.

„Ja, ich erinnere mich. Das haben wir erst kürzlich besprochen. Und ich habe auch darüber nachgedacht, wo das verwendet wird.“

„Und es stellt sich heraus, dass einige der beliebtesten Java-Sammlungen es verwenden.“

„Ja. Übrigens fragen Interviewer oft nach TreeSet . Sie versuchen normalerweise, Sie auszutricksen. Sie sagen: „Wenn ein TreeSet einen Binärbaum verwendet, können alle Elemente einen langen Zweig bilden, sodass die Suche eine Weile dauern wird.“ lange her. «Dies ist genau der richtige Zeitpunkt, um den unverschämten Kerl in die Schranken zu weisen und zu sagen: „Sogar ein Kind weiß, dass TreeSet und TreeMap ausgewogene Rot -Schwarz- Bäume verwenden , sodass diese Situation eigentlich unmöglich ist.““

„Ah. Ich würde gerne das Gesicht der Person sehen, die diese Frage gestellt hat. Vielleicht kann ich mir diesen Satz sogar merken. …“

„Aber in der Praxis stellte sich heraus, dass Set nicht so einfach war, wie ich zunächst dachte.“

„Andererseits ist die Situation mit Queue viel einfacher:“

„ Queue implementiert eine Warteschlange. Elemente werden am Ende der Warteschlange hinzugefügt und von vorne übernommen.“

„ PriorityQueue ist tatsächlich die einzige klassische Implementierung der Queue- Schnittstelle, abgesehen von LinkedList , das technisch gesehen ebenfalls eine Warteschlange ist.“

„Okay, ich werde langsam müde. Das ist alles für heute. Bis zum nächsten Mal.“