Kolekcje implementujące interfejs Set posiadają cechę wyróżniającą ją od innych poznanych wcześniej kolekcji – elementy nie mogą się powtarzać. Dodatkowo użytkownik nie ma wpływu na pozycję przy dodawaniu elementów, jednak konkretna implementacja może porządkować zbiory. Dozwolona jest wartość null, jednakże tylko raz.

W stosunku do sekwencyjnego przeszukiwania listy wykorzystanie interfejsu Set może okazać się bardziej wydajne. Artykuł jest częścią wpisów o kolekcjach w Javie.

Interfejs Set

Najważniejsze klasy, które implementują ten interfejs.

• TreeSet – zestaw, który mimo braku indeksów jest uporządkowany, a za szybkość wyszukiwania zapewniają drzewa czerwono-czarne.
• HashSet – zestaw, implementacja nieposortowana, która przechowuje elementy w tablicy z hashowaniem.
• AbstractSet – zawiera definicje metod interfejsu Set – przydatne w przypadku własnej implementacji, gdyż zwalnia z programisty obowiązek definiowania wszystkich metod.

AbstractSet

Jest to klasa, która implementuje podstawowe metody takie jak dodawanie, usuwanie, wyszukiwanie elementów z listy. Jest wygodna w przypadku, gdy programista zdecyduje się opracować własną implementację interfejsu Set. Jeżeli potrzebna jest inna implementacja konkretnej metody, to można ją przesłonić.

Konstruktor

protected AbstractSet() – pusty konstruktor.

HashSet

Klasa wykorzystująca do swojego działania tzw. tablicę mieszającą (ang. hash table). Każdy obiekt jest reprezentowany przez obliczoną wartość zwaną kodem mieszającym (ang. hash code). Aby było możliwe obliczenie tej wartości potrzebna jest metoda hashCode() (która zwraca kod typu całkowitego int). Takie reprezentowanie danych pozwala na szybki dostęp do elementów. Czas wykonywania podstawowych operacji jest stały (dodawanie, usuwanie, dostęp).

Początkowa pojemność

Podobnie jak w przypadku innych konstruktorów tak i w kolekcji HashSet podczas tworzenia można zadeklarować początkową liczbę przechowywanych elementów (ang. initial capacity), a co za tym idzie ustalić pojemność wewnętrznej tablicy z hashowaniem. Należy uważać, aby nie przesadzić z jej wielkością, szczególnie gdy możemy się spodziewać przybliżoną liczbę elementów kolekcji. W przypadku, gdy podamy za małą liczbę potrzebne będzie utworzenie nowej – większej tablicy (potęgi liczby 2) i skopiowaniu elementów ze starej tablicy.

Współczynnik zapełnienia

Kolejnym parametrem, który można wpisać samemu jest współczynnik zapełnienia tablicy (ang. load factor). Jest to wartość zmiennoprzecinkowa typu float. Wartość ta decyduje jaka część tablicy musi zostać zapełniona, aby została wykonana automatyczna przebudowa wewnętrznej tablicy. Standardowa wartość wynosi 0.75 wywołując konstruktor bez wpisywania tego argumentu.

Czemu jednak nie ustawić go na 1.0, aby jak najrzadziej trzeba było powiększać tablicę? Zapełnienie całej tablicy źle wpłynie na czasy wykonywania operacji odczytu, czy też dodawania elementów. Zwykle lepiej zachować standardową wartość i tylko w przypadku konkretnej optymalizacji próbować ją modyfikować.

Konstruktory

HashSet() – konstruktor bezparametrowy tworzy pusty obiekt z tablicą o pojemności 16 oraz współczynnikiem zapełnienia 0.75.

HashSet(Collection<? extends E> collection) – tworzy kolekcję oraz wstawia do niej elementy kolekcji collection.

HashSet(int initialCapacity) – konstruuje kolekcję z wewnętrzną tablicą o pojemności podanej w parametrze + dopełnienie do najbliższej potęgi liczby 2 (np. przy podaniu 45 utworzy tablicę o pojemności 64), a współczynnik zapełnienia ustawia na 0.75.

HashSet(int pojemnosc, float wspZap) – tworzy tablicę o rozmiarze jak wyżej, a drugi to współczynnik, który decyduje jaką część tablicy należy zapełnić, aby trzeba było ją powiększyć.

Metody

boolean add(E element) – sprawdza czy dodawany element już istnieje – jeżeli nie, to dodaje go do kolekcji i zwraca true.

boolean remove(Object object) – usuwa element podany w parametrze – jeśli się uda (element istnieje) to zwraca true.

void clear() – usuwa wszystkie elementy z kolekcji.

boolean contains(Object object) – sprawdza czy kolekcja zawiera element podany w parametrze – jeśli tak, to zwraca true.

int size() – zwraca rozmiar kolekcji (liczbę elementów, a nie rozmiar tablicy).

Iterator<E> iterator() – zwraca iterator.

Przykład użycia

Wynik będzie następujący.

[null, Młotek, Miarka, Śrubokręt]

Jak pokazuje powyższy przykład nie można duplikować elementów, ale można przechowywać wartość null. Również kolejność wyświetlania nie jest zależna od nas, gdyż zbiór nie jest uporządkowany.

TreeSet

Klasa TreeSet w porównaniu jest kolekcją uporządkowaną, jednakże nie zapewnia swobodnego dostępu po indeksie i nie zapamiętuje kolejności dodawania elementów. Elementy są porządkowane naturalnie (ang. natural ordering) lub na podstawie porównań przez metodę copmareTo() przez własny komparator. W przypadku jego braku elementy umieszczane w kolekcji muszą implementować interfejs Comparable.

W celu zapewnienia wysokiej wydajności wyszukiwania elementów kolekcja przechowywana jest w drzewach czerwono-czarnych, których złożoność można oszacować jako O(log(n)).

Konstruktory

TreeSet() – tworzy pustą kolekcję.

TreeSet(Collection<? extends E> collection) – tworzy kolekcję zawierającą tę przekazaną w parametrze. Elementy muszą implementować interfejs comparable, żeby móc porządkować zbiór naturalnie.

TreeSet(SortedSet<E> s) – tworzy kolekcję zawierającą tę przekazaną w parametrze. Elementy porządkowane są tak samo jak w te przekazywane.

TreeSet(Comparator<? super E> comparator) – Tworzy kolekcję, która będzie porządkowana przez przekazany komparator.

Metody

Kolekcja TreeSet oferuje te same metody, co HashSet. W związku z tym opiszemy tylko te, które są dostępne jedynie w strukturze drzewiastej.

E first() – zwraca najmniejszy element zbioru.

E last() – zwraca największy element zbioru.

addAll(Collection<? extends E> collection) – dodawane są wszystkie elementy z podanej kolekcji.

SortedSet<E> subSet(E from, E to) – zwraca wszystkie elementy znajdujące się pomiędzy pierwszym a drugim parametrem (łącznie z nimi).

NavigableSet<E> subSet(E from, boolean fInc, E to, boolean toInc) – zwraca wszystkie elementy znajdujące się pomiędzy pierwszym a drugim parametrem.

Przykłady użycia

Spróbujmy wykonać kod taki sam jak w przypadku HashSet. Przypominamy o możliwości wykorzystania zmiennych interfejsowych, dzięki czemu wystarczy tylko w jednym miejscu zmienić rodzaj kolekcji na TreeSet.

Efekt uruchomienia programu jest następujący.

Pierwsze na co możemy zwrócić uwagę jest kolejność – jest alfabetyczna. Drzewa są kolekcją uporządkowaną, a klasa String zapewnia sortowanie leksykograficzne. Porównywane są kolejne znaki łańcucha na podstawie ich wartości w systemie kodowania Unicode.

Kolejnym ciekawym miejscem jest wyrzucenie wyjątku NullPointerException przy próbie dodania wartości null do zbioru. Taka operacja nie jest możliwa ze względu na brak możliwości porównania obiektu z wartością null. Mówiąc inaczej nastąpiła próba wykonania metody compareTo(), która w przypadku pustej wartości rzuca tym właśnie wyjątkiem.

HashSet vs TreeSet

Kolekcja HashSet jest szybsza, gdy nie jest potrzebne żadne sortowanie elementów. Dodatkowo w przypadku drzew czerwono-czarnych ze względu na ich algorytmy zachowania poziomów drzewa może wystąpić dużo rotacji, co może spowolnić działanie przy samym dodawaniu elementów kolekcji.

Jednakże gdy potrzebujemy dostać zbiór z określonego przedziału lub najmniejszy element zbioru, to klasa TreeSet może okazać się lepszym rozwiązaniem.