Implementacje interfejsów Set i Queue

„Jak tam twój procesor?”

„W porządku. Siedziałem w ciekłym azocie przez godzinę, więc teraz jestem jak nowy!”

"Świetnie. Więc kontynuujmy."

„Ustaw kolekcje”.

Z matematycznego punktu widzenia zbiór to grupa unikalnych elementów. Zatem w programowaniu Set jest zbiorem unikalnych elementów, czyli zbiorem, który nie pozwala na przechowywanie identycznych elementów.

„Nie wiem, czy Ellie pokazała ci hierarchię dziedziczenia Seta. Jeśli nie, oto ona:”

„A HashSet to kolekcja, która przechowuje elementy wewnętrznie przy użyciu wartości skrótu zwracanych przez metodę hashCode ()”.

„Dla uproszczenia HashSet<E> przechowuje obiekt HashMap<E, Object>, który przechowuje wartości HashSet jako klucze”.

"Wow!"

„Korzystanie z kodów skrótu pozwala szybko wyszukiwać, dodawać i usuwać elementy z zestawu”.

„Pamiętaj jednak, że twoja klasa musi poprawnie zaimplementować metody hashCode & equals , aby dodać obiekty twoich klas do zestawu i poprawnie je tam znaleźć”.

„Obie metody są często używane w HashSet/HashMap ” .

„Jeśli zapomnisz zaimplementować metodę hashCode (), ryzykujesz, że nie będziesz w stanie znaleźć swojego obiektu w zestawie, nawet jeśli jest obecny”.

- Tak, pamiętam, pamiętam. Mówiłeś mi o tym wcześniej. Słyszałem o tym wszystko.

„OK. Oto kilka bardziej przydatnych informacji dla ciebie”.

„Załóżmy, że poprawnie zaimplementowałeś hashCode i equals  w swojej klasie i szczęśliwie przechowujesz swoje obiekty w zestawie”.

„Ale potem idziesz i zmieniasz jeden z obiektów, a tym samym zmieniasz wewnętrzne dane używane do obliczania jego skrótu . Tak więc zmienia się skrót obiektu”.

„A to oznacza, że ​​kiedy będziesz go szukać w Zestawie, prawdopodobnie go nie znajdziesz”.

Jak to działa?

„Jest to dobrze znana pułapka podczas pracy z haszami. Zasadniczo wyszukiwanie HashSet (i HashMap) gwarantuje prawidłowe działanie tylko wtedy, gdy obiekty są niezmienne ”.

"Wow! I co, nikt nic z tym nie robi?"

„Wszyscy udają, że problem nie istnieje. Ale to często pojawia się w wywiadach, więc może warto o tym pamiętać…”

„ LinkedHashSet to zestaw HashSet, którego elementy są również przechowywane na połączonej liście. Normalne zestawy HashSet nie obsługują kolejności elementów. Po pierwsze, po prostu nie jest to oficjalna operacja. Po drugie, nawet kolejność wewnętrzna może się znacznie zmienić, gdy pojedynczy element jest dodany”.

Ale możesz uzyskać iterator z LinkedHashSet i użyć go do przejrzenia wszystkich elementów w kolejności, w jakiej zostały dodane do LinkedHashSet . Nie zdarza się to często, ale czasami jest to bardzo potrzebne”.

„Rozumiem. Uwielbiam, gdy istnieją klasy dla tych scenariuszy „na wszelki wypadek”. Takie przypadki nie są wcale takie rzadkie”.

" TreeSet to zbiór, który przechowuje elementy w postaci drzewa uporządkowanego według wartości. TreeSet <E> zawiera TreeMap <E, Object>, który przechowuje wszystkie te wartości. A ten TreeMap używa zrównoważonego czerwono -czarnego drzewa do przechowywania elementy . W rezultacie obsługuje bardzo szybkie dodawanie, usuwanie i zawiera operacje. ”

„Tak, pamiętam. Niedawno o tym rozmawialiśmy. Myślałem też o tym, gdzie to jest używane”.

„Okazuje się, że używają go niektóre z najpopularniejszych kolekcji Javy”.

Tak, nawiasem mówiąc, ankieterzy często pytają o TreeSet . Zwykle próbują cię oszukać. Powiedzą: „Jeśli TreeSet używa drzewa binarnego, to wszystkie elementy mogą tworzyć jedną długą gałąź, więc wyszukiwanie zajmie długi czas. «To jest właśnie czas, aby postawić bezczelnego faceta na swoim miejscu, stwierdzając: „Nawet dziecko wie, że TreeSet i TreeMap używają zrównoważonych czerwono -czarnych drzew, więc taka sytuacja jest właściwie niemożliwa”.

– Ach. Bardzo chciałbym zobaczyć twarz osoby, która zadała to pytanie. Może nawet zapamiętam to zdanie…

„Ale w praktyce Set okazał się nie tak prosty, jak początkowo myślałem”.

„Z drugiej strony sytuacja z kolejką jest znacznie prostsza:”

" Kolejka implementuje kolejkę. Elementy są dodawane na końcu kolejki i pobierane z przodu."

„ PriorytetQueue jest w rzeczywistości jedyną klasyczną implementacją interfejsu Queue , nie licząc LinkedList , który technicznie jest również kolejką”.

„Dobra, zaczynam się męczyć. To wszystko na dzisiaj. Do następnego razu”.