HashSet w Javie: unikalne wartości, przynależność i działania na zbiorach

Zbiór przechowuje unikalne wartości

HashSet (z java.util) to kolekcja, która przechowuje każdą wartość najwyżej raz. Nie ma tu kluczy i wartości połączonych w pary jak w HashMap: to po prostu worek różnych elementów. Jego całe zadanie to szybka odpowiedź na jedno pytanie: „czy to tu jest?”

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("java");   // duplikat: ignorowany

        System.out.println(tags.contains("java"));     // true
        System.out.println(tags.contains("frontend")); // false
        System.out.println(tags.size());               // 2
    }
}

Jest jeden parametr typu, <ElementType>. Podobnie jak przy ArrayList i HashMap zmienną zwykle deklaruje się jako interfejs Set, a tworzy HashSet.

add zwraca informację, czy wartość była nowa

add nie tylko zapisuje wartość, ale też zwraca boolean, który mówi, czy zbiór faktycznie się zmienił. Dodanie wartości, która już jest w zbiorze, zwraca false i niczego nie zmienia.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();

        System.out.println(seen.add(7));  // true: 7 było nowe
        System.out.println(seen.add(7));  // false: już było
        System.out.println(seen);
    }
}

Ta zwracana wartość jest naprawdę przydatna: if (!seen.add(x)) { /* x is a repeat */ } pozwala wykrywać duplikaty w jednym wierszu na bieżąco.

Usuwanie duplikatów z listy

Zbiór odrzuca powtórzenia, więc najszybszy sposób na usunięcie duplikatów z kolekcji to przerzucenie jej do zbioru. Konstruktor HashSet przyjmuje dowolną inną kolekcję:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ada", "Boris", "Ada", "Chen", "Boris"));

        Set<String> unique = new HashSet<>(names);
        System.out.println(unique);          // każde imię raz
        System.out.println(unique.size());   // 3

        // potrzebujesz z powrotem List?
        List<String> deduped = new ArrayList<>(unique);
        System.out.println(deduped.size());  // 3
    }
}

To najczęstszy powód, dla którego początkujący sięgają po zbiór. Pamiętaj tylko, że po drodze tracisz pierwotną kolejność; jeśli kolejność ma znaczenie, użyj LinkedHashSet (omówiony niżej).

contains, remove i size

Codzienne operacje wyglądają tak samo jak w innych kolekcjach:

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("api");

        System.out.println(tags.contains("api"));  // true
        System.out.println(tags.size());           // 3

        tags.remove("backend");
        System.out.println(tags.contains("backend")); // false

        tags.clear();
        System.out.println(tags.isEmpty());         // true
    }
}

Wielka przewaga nad ArrayList to contains. Lista musi przejść po każdym elemencie, żeby odpowiedzieć (O(n)), a HashSet trafia niemal od razu do odpowiedzi (mniej więcej O(1)). Gdy łapiesz się na wywoływaniu list.contains(...) wewnątrz pętli, to zwykle sygnał, że pora przejść na zbiór.

Działania na zbiorach: suma, iloczyn, różnica

Zbiory błyszczą, gdy je łączysz. Gdy wiesz, która metoda co robi, czyta się je jak zwykły tekst:

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);            // wszystko, co jest w którymkolwiek zbiorze
        System.out.println(union);  // 1 2 3 4 5 6

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // tylko to, co jest w obu
        System.out.println(intersection); // 3 4

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);    // w a, ale nie w b
        System.out.println(difference);   // 1 2
    }
}

Najważniejsza pułapka: addAll, retainAll i removeAll zmieniają zbiór, na którym je wywołano. Dlatego każdy przykład najpierw kopiuje a do nowego HashSet, inaczej zniszczyłbyś oryginał. Dla każdego wyniku buduj nowy zbiór.

HashSet nie zachowuje kolejności

Podobnie jak HashMap, HashSet nie gwarantuje kolejności iteracji, a ta może się różnić między uruchomieniami. Jeśli potrzebujesz przewidywalności:

• LinkedHashSet zachowuje kolejność wstawiania, czyli kolejność dodawania elementów.
• TreeSet utrzymuje elementy posortowane według porządku naturalnego (albo podanego przez ciebie Comparator).

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("gamma");
        insertion.add("alpha");
        insertion.add("beta");
        System.out.println(insertion);  // [gamma, alpha, beta]

        Set<String> sorted = new TreeSet<>(insertion);
        System.out.println(sorted);      // [alpha, beta, gamma]
    }
}

Wszystkie trzy implementują interfejs Set, więc zamiana jednego na drugi to zmiana jednego wiersza z konstruktorem.

Elementy muszą być haszowalne

Pod spodem HashSet opiera się na HashMap, więc obowiązuje ta sama zasada: odnajduje elementy przez haszowanie, co oznacza, że hashCode() i equals() elementu muszą być ze sobą zgodne. Typy wbudowane, takie jak String i Integer, robią to poprawnie, i dlatego powtórzone napisy "java" powyżej poprawnie się scalają. Jeśli przechowujesz instancje własnej klasy, nadpisz zarówno equals, jak i hashCode. Inaczej dwa obiekty „równe” znaczeniowo zostaną uznane za różne, a contains i usuwanie duplikatów po cichu przestaną działać.

Dalej: iterowanie po kolekcjach

Znasz już trzy najważniejsze kolekcje: ArrayList, HashMap i HashSet. Po każdej przechodzi się trochę inaczej i czyhają przy tym subtelne pułapki (na przykład modyfikowanie kolekcji w trakcie pętli). Dalej zbierzemy to wszystko razem i omówimy czyste iterowanie po kolekcjach za pomocą pętli for-each, iteratorów i forEach.