Struktury danych – zbiór

Artykuł ten opisuje przykładową implementację zbioru. Zbiór jest abstrakcyjnym typem danych, który występuje w wielu językach programowania. Zasada pracy ze zbiorami są niezależnie od języka programowania.

Przykładową implementację przygotowałem w Javie. Żeby wynieść jak najwięcej z tego artykułu potrzebna jest wiedza na temat hashCode i equals. Niezbędna jest też znajomość kontraktu pomiędzy metodami equals i hashCode.

Do zrozumienia przykładowej implementacji niezbędna będzie też wiedza o typach generycznych.

Może przydać się też wiedza na temat szacowania złożoności obliczeniowej.

Struktura danych a abstrakcyjny typ danych

W poprzednich artykułach z serii opisujących listę wiązaną czy tablicę asocjacyjną pominąłem kwestie definicji. Używałem określenia struktura danych i abstrakcyjny typ danych zamiennie. Tym razem chciałbym zwrócić Twoją uwagę na drobną różnicę pomiędzy tymi określeniami.

Abstrakcyjny typ danych definiuje zachowanie danego typu. Określa zestaw operacji, które można na tym typie wykonać. Opis abstrakcyjnego typu danych zawiera także cechy charakterystyczne dla danego typu.

Na przykład zbiór jest abstrakcyjnym typem danych (niżej opiszę jego własności), a TreeSet czy HashSet są implementacjami tego abstrakcyjnego typu danych. Te implementacje używają rożnych struktur danych. Innym przykładem może być abstrakcyjny typ danych tablica asocjacyjna, której implementacja może używać tablicy i listy wiązanej.

Czym jest zbiór

Zbiór jest abstrakcyjnym typem danych, który ma następujące własności:

• pozwala na przechowywanie wielu elementów,
• kolejność elementów w zbiorze nie ma znaczenia¹,
• pozwala na przechowywanie co najwyżej jednej kopii elementu (duplikaty nie są dozwolone).

Podstawowymi operacjami, które można przeprowadzić na zbiorze jest dodanie elementu, usunięcie elementu i sprawdzenie czy dany element jest częścią zbioru.

Zbiór jest także jednym z podstawowych pojęć matematycznych.

Algebra zbiorów

Tematem tego artykułu nie jest zbiór w kontekście matematycznym. Chciałbym jednak zwrócić Twoją uwagę na podstawowe operacje, które można przeprowadzać na zbiorach. Ta podstawowa wiedza może także przydać się w kontekście programowania.

Poza operacjami przyda się też wiedza o tak zwanym zbiorze pustym. Zbiór pusty jak sama nazwa wskazuje jest pusty, nie ma żadnego elementu.

Iloczyn

Nazywany także przecięciem dwóch zbiorów. Przecięcie to nic innego jak część wspólna dwóch zbiorów. Przecięcie dwóch zbiorów może prowadzić do uzyskania:

• mniejszego podzbioru, który jest częścią wspólną obu zbiorów,
• zbioru równemu obu zbiorom, jeśli oba zbiory zawierają dokładnie takie same elementy,
• pustego zbioru, jeśli oba zbiory nie mają wspólnych elementów.

Iloczyn dowolnego zbioru ze zbiorem pustym zawsze jest zbiorem pustym.

Suma

Suma dwóch zbiorów to zbiór, który zawiera wszystkie elementy z obu sumowanych zbiorów.

Różnica

Różnica zbioru A i zbioru B to zbiór zawierający wszystkie elementy, które są w zbiorze A i nie ma ich w zbiorze B.

Pobierz opracowania zadań z rozmów kwalifikacyjnych

Przygotowałem rozwiązania kilku zadań algorytmicznych z rozmów kwalifikacyjnych. Rozkładam je na czynniki pierwsze i pokazuję różne sposoby ich rozwiązania. Dołącz do grupy ponad 6147 Samouków, którzy jako pierwsi dowiadują się o nowych treściach na blogu, a prześlę je na Twój e-mail.

Jak działa zbiór?

W ramach tego artykułu skupię się na przykładowej implementacji, która oparta jest o funkcję skrótu (w języku Java jest to hashCode). Przedstawiona tu implementacja będzie uproszczoną wersją klasy HashSet, znajdującej się w bibliotece standardowej.

hashCode i equals

Podobnie jak w przypadku tablicy asocjacyjnej opartej o funkcję skrótu tak i tutaj hashCode i equals pełnią kluczową rolę.

Także tutaj na podstawie wartości funkcji hashCode obliczone zostanie „wiaderko”, do którego wpadnie dany element. Następnie elementy wewnątrz tego samego wiaderka porównywane będą przy pomocy metody equals. Takie podejście pozwala na uzyskanie bardzo dobrej złożoności obliczeniowej.

Podobnie jak w przypadku tablicy asocjacyjnej kluczowe jest zachowanie kontraktu pomiędzy tymi metodami.

Podstawowe operacje

Jak wspomniałem wyżej zbiór oferuje kilka podstawowych operacji. Na potrzeby tego artykułu ograniczę je do takiego interfejsu:

public interface SimpleSet<E> {
    int size();
    boolean add(E element);
    boolean remove(E element);
    boolean contains(E element);
}

• int size() – metoda zwraca liczbę elementów zbioru,
• boolean add(E element) – metoda dodaje element to zbioru, zwraca true jeśli element został dodany,
• boolean remove(E element) – metoda usuwa element ze zbioru, zwraca true jeśli element został usunięty,
• boolean contains(E element) – metoda zwraca flagę informującą czy element istnieje w zbiorze.

Przykładowa implementacja

Podobieństwa pomiędzy HashSet i HashMap

Zacznę od krótkiego przypomnienia czym jest tablica asocjacyjna. Ta struktura pozwala na przechowywanie kluczy i odpowiadających im wartości. Implementacja HashMap zakłada, że tablica asocjacyjna zawiera unikalny zestaw kluczy. Innymi słowy nie może w niej być dwóch takich samych kluczy.

Tablica asocjacyjna, podobnie jak zbiór, nie zwraca uwagi na porządek kluczy². Zbiór nie zawiera duplikatów, mapa nie przechowuje zduplikowanych kluczy.

Czy widzisz tu pewne podobieństwo pomiędzy zbiorem a tak zdefiniowaną tablicą asocjacyjną? Powiem więcej, bardzo często implementacje zbioru pod spodem używają tablicy asocjacyjnej.

Są też języki programowania, w których w bibliotece standardowej nie ma zbiorów a jedynie tablice asocjacyjne. Jednym z takich języków jest Go.

Kod źródłowy

Jak wspomniałem wcześniej zbiór jest bardzo podobny do tablicy asocjacyjnej. To podobieństwo jest widoczne także w przykładowej implementacji:

public class SimpleHashSet<T> implements SimpleSet<T> {
    private static final Object PRESENT = new Object();

    private final SimpleMap<T, Object> map = new SimpleHashMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean add(T item) {
        return map.put(item, PRESENT) == null;
    }

    @Override
    public boolean remove(T item) {
        return map.remove(item) == PRESENT;
    }

    @Override
    public boolean contains(T item) {
        return map.containsKey(item);
    }
}

Zauważ, że cały mechanizm związany z funkcją skrótu, kubełkami, dynamicznym rozszerzaniem pojemności zbioru jest ukryty w implementacji tablicy asocjacyjnej. Sam zbiór korzysta jedynie z publicznych metod. Jeśli nie znasz któregokolwiek z tych mechanizmów koniecznie przeczytaj artykuł o tablicy asocjacyjnej.

Interesującym zabiegiem jest tu użycie instancji PRESENT. Dzięki takiemu podejściu minimalizowana jest wielkość zbioru, istnieje tylko jeden obiekt wartości współdzielony pomiędzy wszystkimi kluczami.

Implementacja zbioru opartego o funkcje skrótu jest na tyle prosta, że zestaw testów jednostkowych ma dużo więcej linijek kodu ;).

Złożoność obliczeniowa

Złożoność obliczeniowa poszczególnych operacji odpowiada złożoności obliczeniowej tablicy asocjacyjnej. Wynika to z faktu, że każda operacja wywołuje odpowiednią metodę zaimplementowaną w tablicy asocjacyjnej.

Ma to dokładnie takie same konsekwencje jak w przypadku mapy opartej o funkcję skrótu. Jeśli funkcja skrótu jest „dobra” wówczas złożoność operacji wynosi Ο(1). Jeśli jest zła, złożoność obliczeniowa spada do Ο(n).

Dla przypomnienia możesz rzucić okiem na złożoność obliczeniową mapy.

Najczęściej zadawane pytania

Czy zbiór jest serializowalny/wielowątkowo bezpieczny/posortowany

Jak wspomniałem na początku artykułu zbiór tak na prawdę nie jest strukturą danych. Zbiór to abstrakcyjny typ danych, który może mieć wiele implementacji. Jedną z nich przedstawiłem w tym artykule. Sam zbiór nie może być serializowalny/wielowątkowo bezpieczny/posortowany, ale jego konkretna implementacja już tak. Na przykład implementacja zbioru oparta o drzewo jest posortowana, a ta oparta o funkcję skrótu już nie musi taka być.

Czym zbiór różni się od listy

Zbiór z definicji jest nieuporządkowanym zbiorem elementów, które nie mogą się powtarzać. Lista to elementy, które mogą się powtarzać. Dodatkowo lista ma swój określony porządek.

Czym zbiór różni się od tablicy asocjacyjnej

Tablica asocjacyjna zawiera unikalny zbiór kluczy, Każdy z kluczy ma przyporządkowaną wartość. Zbiór kluczy w mapie nie zawiera duplikatów. Można powiedzieć, że zbiór jest częścią mapy – zbiór nie zawiera mapowania. To podobieństwo widać w przykładowej implementacji.

Dodatkowe materiały do nauki

W artykule tylko musnąłem zagadnienia związane z matematyką. Jeśli chcesz możesz dowiedzieć się czegoś więcej o algebrze zbiorów.

Polecam lekturę dokumentacji klasy HashSet i przejrzenie implementacji HashSet w OpenJDK. Możesz też rzucić okiem na implementację zbioru opartą o drzewa.

Jak zwykle zachęcam Cię też do przejrzenia kodu źródłowego użytego w artykule.

Podsumowanie

Teraz wiesz czym jest zbiór. Znasz złożoność obliczeniową poszczególnych operacji. Znasz podstawowe operacje, które można przeprowadzać na zbiorach. Masz też pod ręką zestaw dodatkowych materiałów, które pozwolą Ci poszerzyć zdobytą wiedzę. Możesz śmiało powiedzieć, że udało Ci się poznać kolejny abstrakcyjny typ danych :).

Jeśli znasz kogoś komu materiał zebrany w tym artykule może się przydać będę wdzięczny za podzielenie się linkiem. Zależy mi na dotarciu do nowych Czytelników, a Ty możesz mi w ten sposób pomóc – z góry dziękuję!

Jeśli nie chcesz pominąć kolejnych artykułów na blogu dopisz się do samouczkowego newslettera. Możesz też polubić profil Samouczka na Facebook’u. To tyle na dzisiaj, trzymaj się i do następnego razu!

1. Niektóre implementacje porządkują elementy zbioru. ↩

2. To zależy od implementacji, na przykład TreeMap sortuje klucze a TreeSet przechowuje posortowane wartości. ↩

Pobierz opracowania zadań z rozmów kwalifikacyjnych

Przygotowałem rozwiązania kilku zadań algorytmicznych z rozmów kwalifikacyjnych. Rozkładam je na czynniki pierwsze i pokazuję różne sposoby ich rozwiązania. Dołącz do grupy ponad 6147 Samouków, którzy jako pierwsi dowiadują się o nowych treściach na blogu, a prześlę je na Twój e-mail.