Kolekcje Javy – Interfejs Set
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 interfejsuSet
– 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.HashSet; import java.util.Set; public class Test { public static void main(String[]args) { Set<String> narzedzia = new HashSet<>(); // Dodawanie elementów narzedzia.add("Młotek"); narzedzia.add("Śrubokręt"); narzedzia.add("Miarka"); narzedzia.add("Taśma"); // Wyświetlenie kolekcji HashSet System.out.println(narzedzia); System.out.println("Czy skrzynka zawiera młotek? - " + narzedzia.contains("Młotek")); // Duplikowanie elementów System.out.println("Próba dodania ponownie tego samego elementu - " + narzedzia.add("Miarka")); //Usunięcie elementu narzedzia.remove("Taśma"); System.out.println(narzedzia); //Dodanie elementu null narzedzia.add(null); System.out.println(narzedzia); } } |
Wynik będzie następujący.
1 2 3 4 |
[Młotek, Taśma, Miarka, Śrubokręt] Czy skrzynka zawiera młotek? - true Próba dodania ponownie tego samego elementu - false [Młotek, Miarka, Śrubokręt] |
[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
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.TreeSet; import java.util.Set; public class TestTreeSet { public static void main(String[]args) { Set<String> narzedzia = new TreeSet<>(); // Dodawanie elementów narzedzia.add("Młotek"); narzedzia.add("Śrubokręt"); narzedzia.add("Miarka"); narzedzia.add("Taśma"); // Wyświetlenie kolekcji HashSet System.out.println(narzedzia); System.out.println("Czy skrzynka zawiera młotek? - " + narzedzia.contains("Młotek")); // Duplikowanie elementów System.out.println("Próba dodania ponownie tego samego elementu - " + narzedzia.add("Miarka")); //Usunięcie elementu narzedzia.remove("Taśma"); System.out.println(narzedzia); //Dodanie elementu null narzedzia.add(null); System.out.println(narzedzia); } } |
Efekt uruchomienia programu jest następujący.
1 2 3 4 5 6 7 8 |
[Miarka, Młotek, Taśma, Śrubokręt] Czy skrzynka zawiera młotek? - true Próba dodania ponownie tego samego elementu - false [Miarka, Młotek, Śrubokręt] Exception in thread "main" java.lang.NullPointerException at java.base/java.util.TreeMap.put(TreeMap.java:561) at java.base/java.util.TreeSet.add(TreeSet.java:255) at Test.main(Test.java:28) |
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.