HashSet w Javie

Klasa HashSetimplementuje interfejs Set, opiera się na tablicy mieszającej i jest również wspierana przez instancję HashMap. Ponieważ HashSetelementy nie są uporządkowane, nie ma gwarancji, że po pewnym czasie elementy będą w tej samej kolejności. Operacje dodawania, usuwania i wyszukiwania będą wykonywane w czasie stałym, pod warunkiem, że funkcja haszująca prawidłowo rozdzieli elementy na „zasobniki”, o czym później. Kilka ważnych punktów na temat HashSet:

• Ponieważ klasa implementuje interfejs Set, może przechowywać tylko unikalne wartości;
• Może przechowywać wartości NULL;
• Kolejność dodawania elementów jest obliczana przy użyciu kodu skrótu;
• HashSetimplementuje również Serializablei Cloneable.

Aby zachować stały czas wykonania operacji, czas spędzony na akcjach z HashSet, musi być wprost proporcjonalny do liczby elementów w HashSet+ „pojemności” wbudowanej instancji HashMap(liczby „koszyków”). Dlatego, aby utrzymać wydajność, ważne jest, aby nie ustawiać zbyt dużej pojemności początkowej (ani zbyt niskiego współczynnika obciążenia). Pojemność początkowa – początkowa liczba komórek („pojemników”) w tabeli mieszającej. Jeżeli wszystkie komórki zostaną wypełnione, ich liczba automatycznie się zwiększy. Współczynnik obciążenia to miara tego, jak bardzo może być zapełniony, HashSetzanim jego pojemność automatycznie wzrośnie. Gdy liczba elementów w HashSetstanie się większa od iloczynu pojemności początkowej i współczynnika obciążenia, następuje ponowne hashowanie tablicy skrótów (kody skrótów elementów są przeliczane i tabela jest odbudowywana zgodnie z uzyskanymi wartościami) i liczba liczba komórek w nim ulega podwojeniu. Współczynnik obciążenia = liczba elementów przechowywanych w tabeli / rozmiar tabeli mieszającej. Na przykład, jeśli początkowa liczba komórek w tabeli wynosi 16, a współczynnik obciążenia wynosi 0,75, to wynika z tego, że gdy liczba wypełnionych komórek osiągnie 12, liczba komórek automatycznie wzrośnie. Współczynnik obciążenia i pojemność początkowa to dwa główne czynniki wpływające na wydajność HashSet. Współczynnik obciążenia wynoszący 0,75 zapewnia średnio dobrą wydajność. Jeśli ten parametr zostanie zwiększony, wówczas obciążenie pamięci zostanie zmniejszone (ponieważ zmniejszy to liczbę ponownych skrótów i przebudów), ale będzie to miało wpływ na operacje dołączania i wyszukiwania. Aby zminimalizować czas spędzony na ponownym hashowaniu, należy wybrać odpowiedni parametr pojemności początkowej. Jeśli początkowa pojemność jest większa niż maksymalna liczba elementów podzielona przez współczynnik obciążenia, wówczas w ogóle nie nastąpi operacja ponownego mieszania. Ważny: HashSetnie jest strukturą danych z wbudowaną synchronizacją, więc jeśli pracuje nad nią wiele wątków jednocześnie i przynajmniej jeden z nich próbuje dokonać zmian, konieczne jest zapewnienie zsynchronizowanego dostępu z zewnątrz. Często odbywa się to kosztem innego zsynchronizowanego obiektu zawierającego plik HashSet. Jeśli nie ma takiego obiektu, to Collections.synchronizedSet(). Jest to obecnie najlepszy sposób zapobiegania niezsynchronizowanym operacjom z plikami HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

Konstruktorzy HashSet:

1. HashSet h = new HashSet(); - domyślny konstruktor. Domyślna pojemność początkowa wynosi 16, współczynnik obciążenia wynosi 0,75.
2. HashSet h = new HashSet(int initialCapacity)– konstruktor o zadanej pojemności początkowej. Współczynnik obciążenia – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— konstruktora o zadanej nośności początkowej i współczynniku obciążenia.
4. HashSet h = new HashSet(Collection C)– konstruktor dodający elementy z innej kolekcji.

Poniższy kod demonstruje niektóre metody HashSet:

import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Dodaj elementy do zestawu HashSet za pomocą metody add().
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// spróbuj dodać kolejny taki sam element

        // Wydrukuj elementy zestawu HashSet na konsoli
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Usuń elementy ze zbioru za pomocą metody remove().
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Przejrzyj elementy zestawu HashSet za pomocą iteratora:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Wniosek:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

Wszystkie klasy implementujące interfejs Setsą wewnętrznie obsługiwane przez implementacje Map. HashSetprzechowuje elementy za pomocą HashMap. Chociaż HashMapelement musi być reprezentowany jako para klucz-wartość, do której można dodać element, HashSetdodawana jest tylko wartość. W rzeczywistości wartość, którą przekazujemy, HashSetjest kluczem do obiektu HashMap, a jako wartość używana jest stała HashMap. W ten sposób w każdej parze klucz-wartość wszystkie klucze będą miały tę samą wartość. Realizacja HashSetw java doc:

private transient HashMap map;

// Konstruktor - 1
// Wszystkie konstruktory niejawnie tworzą obiekt HashMap.
public HashSet()
{
    // Utwórz niejawny obiekt HashMap
    map = new HashMap();
}

// Konstruktor- 2
public HashSet(int initialCapacity)
{
    // Utwórz niejawny obiekt HashMap
    map = new HashMap(initialCapacity);
}

// Obiekt klasy Object, za każdym razem działający jako wartość w HashMap
private static final Object PRESENT = new Object();

Jeśli spojrzysz na metodę add()y HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

Można zauważyć, że metoda add()y HashSetwywołuje metodę put()na obiekcie wewnętrznym HashMap, przekazując mu jako klucz element, który ma zostać dodany, a jako wartość stałą PRESENT. Metoda działa w podobny sposób remove(). Wywołuje metodę remove()obiektu wewnętrznego HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSetopiera się na tabeli mieszającej, a operacje dodawania, usuwania lub wyszukiwania będą wykonywane średnio w stałym (O(1)) czasie . Metody HashSet:

1. boolean add(E e): dodaje element do HashSet, jeśli go nie ma, ale jeśli taki element już istnieje, metoda zwraca false .
2. void clear():usuwa wszystkie elementy ze zbioru.
3. boolean contains(Object o): Zwraca wartość true , jeśli dany element występuje w zestawie.
4. boolean remove(Object o): Usuwa dany element ze zbioru, jeśli jest obecny.
5. Iterator iterator(): Zwraca iterator dla elementów zestawu.
6. boolean isEmpty(): Zwraca wartość true , jeśli w zestawie nie ma żadnych elementów.
7. Object clone(): Wykonuje klonowanie powierzchniowe HashSet.

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html