Zestaw skrótów Java class implementuje interfejs Set, oparty na tablicy mieszającej, która w rzeczywistości jest instancją HashMap. Nie ma żadnej gwarancji co do kolejności iteracji zestawów skrótów, co oznacza, że klasa nie gwarantuje stałej kolejności elementów w czasie. Ta klasa dopuszcza element null. Klasa oferuje również stałą wydajność w czasie dla podstawowych operacji, takich jak dodawanie, usuwanie, zawiera i rozmiar, zakładając, że funkcja mieszająca prawidłowo rozdziela elementy pomiędzy segmentami, co zobaczymy w dalszej części artykułu.
Funkcje Java HashSet
Poniżej wymieniono kilka ważnych funkcji HashSet:
- Przybory Ustaw interfejs .
- Podstawowa struktura danych dla HashSet to Hashtable .
- Ponieważ implementuje interfejs zestawu, duplikaty wartości są niedozwolone.
- Nie ma gwarancji, że obiekty wstawiane w HashSet zostaną wstawione w tej samej kolejności. Obiekty wstawiane są na podstawie ich kodu skrótu.
- Elementy NULL są dozwolone w HashSet.
- HashSet również implementuje Możliwość serializacji I Możliwość klonowania interfejsy.
Deklaracja HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
Gdzie I to typ elementów przechowywanych w zestawie HashSet.
Przykład Java HashSet
Jawa
// Java program to illustrate the concept> // of Collection objects storage in a HashSet> import> java.io.*;> import> java.util.*;> > class> CollectionObjectStorage {> > >public> static> void> main(String[] args)> >{> >// Instantiate an object of HashSet> >HashSet set =>new> HashSet();> > >// create ArrayList list1> >ArrayList list1 =>new> ArrayList();> > >// create ArrayList list2> >ArrayList list2 =>new> ArrayList();> > >// Add elements using add method> >list1.add(>1>);> >list1.add(>2>);> >list2.add(>1>);> >list2.add(>2>);> >set.add(list1);> >set.add(list2);> > >// print the set size to understand the> >// internal storage of ArrayList in Set> >System.out.println(set.size());> >}> }> |
rodzaje pętli for
>
>Wyjście:
1>
Przed zapisaniem obiektu HashSet sprawdza, czy istnieje wpis, używając metod hashCode() i równości(). W powyższym przykładzie dwie listy są uważane za równe, jeśli zawierają te same elementy w tej samej kolejności. Kiedy wywołujesz hashCode() na dwóch listach, obie dałyby ten sam skrót, ponieważ są równe.
Notatka: HashSet tak nie przechowywać zduplikowanych elementów , jeśli podasz dwa równe obiekty, wówczas przechowuje tylko pierwszy, tutaj jest to lista1.
Hierarchia HashSet jest następująca:
Wewnętrzne działanie zestawu HashSet
Wszystkie klasy interfejsu Set są wewnętrznie wspierane przez Map. HashSet używa HashMap do wewnętrznego przechowywania swojego obiektu. Pewnie zastanawiasz się, że do wprowadzenia wartości w HashMap potrzebujemy pary klucz-wartość, ale w HashSet przekazujemy tylko jedną wartość.
Przechowywanie w HashMap: Właściwie wartość, którą wstawiamy do HashSet, działa jak klucz do obiektu mapy, a Java używa stałej zmiennej dla jej wartości. Zatem w parze klucz-wartość wszystkie wartości będą takie same.
Implementacja HashSet w dokumencie Java
private transient HashMap map; // Constructor - 1 // All the constructors are internally creating HashMap Object. public HashSet() { // Creating internally backing HashMap object map = new HashMap(); } // Constructor - 2 public HashSet(int initialCapacity) { // Creating internally backing HashMap object map = new HashMap(initialCapacity); } // Dummy value to associate with an Object in Map private static final Object PRESENT = new Object();> Jeśli spojrzymy na dodać() metoda klasy HashSet:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Możemy zauważyć, że metoda add() klasy HashSet wewnętrznie wywołuje metodę umieścić() metoda tworzenia kopii zapasowej obiektu HashMap poprzez przekazanie określonego elementu jako klucza i stałej PRESENT jako jego wartości. usunąć() metoda działa również w ten sam sposób. Wewnętrznie wywołuje metodę usuwania interfejsu Map.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet nie tylko przechowuje unikalne obiekty, ale także unikalną kolekcję obiektów tak jak Lista tablic , Połączona lista , wektor,..etc.
Konstruktory klasy HashSet
Aby utworzyć HashSet, musimy utworzyć obiekt klasy HashSet. Klasa HashSet składa się z różnych konstruktorów, które umożliwiają ewentualne utworzenie HashSet. Poniżej przedstawiono konstruktory dostępne w tej klasie.
1. HashSet()
Ten konstruktor służy do budowania pustego obiektu HashSet, w którym domyślna pojemność początkowa wynosi 16, a domyślny współczynnik obciążenia wynosi 0,75. Jeśli chcemy utworzyć pusty zestaw HashSet o nazwie hs, można go utworzyć jako:
HashSet hs = new HashSet();>
2. HashSet(int początkowa pojemność)
Konstruktor ten służy do budowania pustego obiektu HashSet, w którym w momencie tworzenia obiektu określono wartość inicjującą. Tutaj domyślny współczynnik obciążenia pozostaje 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet(int początkowyCapacity, float LoadFactor)
Konstruktor ten służy do budowania pustego obiektu HashSet, w którym w momencie tworzenia obiektu określone są wartości początkoweCapacity i LoadFactor.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet (kolekcja)
Konstruktor ten służy do zbudowania obiektu HashSet zawierającego wszystkie elementy z danej kolekcji. Krótko mówiąc, tego konstruktora używa się, gdy wymagana jest jakakolwiek konwersja dowolnego obiektu Collection na obiekt HashSet. Jeśli chcemy utworzyć HashSet o nazwie hs, można go utworzyć jako:
HashSet hs = new HashSet(Collection C);>
Poniżej realizacja powyższych tematów:
Jawa
// Java program to Demonstrate Working> // of HashSet Class> > // Importing required classes> import> java.util.*;> > // Main class> // HashSetDemo> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> > >// Creating an empty HashSet> >HashSet h =>new> HashSet();> > >// Adding elements into HashSet> >// using add() method> >h.add(>'India'>);> >h.add(>'Australia'>);> >h.add(>'South Africa'>);> > >// Adding duplicate elements> >h.add(>'India'>);> > >// Displaying the HashSet> >System.out.println(h);> >System.out.println(>'List contains India or not:'> >+ h.contains(>'India'>));> > >// Removing items from HashSet> >// using remove() method> >h.remove(>'Australia'>);> >System.out.println(>'List after removing Australia:'> >+ h);> > >// Display message> >System.out.println(>'Iterating over list:'>);> > >// Iterating over hashSet items> >Iterator i = h.iterator();> > >// Holds true till there is single element remaining> >while> (i.hasNext())> > >// Iterating over elements> >// using next() method> >System.out.println(i.next());> >}> }> |
>
>Wyjście:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Metody w HashSet
| METODA | OPIS |
|---|---|
| dodaj (i i) | Służy do dodania określonego elementu, jeśli nie jest obecny. Jeśli jest obecny, zwraca wartość false. |
| jasne() | Służy do usuwania wszystkich elementów zestawu. |
| zawiera (obiekt o) | Służy do zwracania prawdy, jeśli element występuje w zestawie. |
| usuń(obiekt o) | Służy do usuwania elementu, jeśli jest obecny w zestawie. |
| iterator() | Służy do zwracania iteratora nad elementem w zestawie. |
| jest pusty() | Służy do sprawdzania, czy zestaw jest pusty, czy nie. Zwraca wartość true w przypadku pustego zestawu i false w przypadku niepustego warunku. |
| rozmiar() | Służy do zwracania rozmiaru zestawu. |
| klon() | Służy do tworzenia płytkiej kopii zestawu. |
Wykonywanie różnych operacji na HashSet
Zobaczmy, jak wykonać kilka często używanych operacji na zestawie HashSet.
1. Dodawanie elementów w HashSet
Aby dodać element do HashSet, możemy użyć metody add(). Jednak kolejność wstawiania nie jest zachowywana w zestawie HashSet. Musimy pamiętać, że zduplikowane elementy są niedozwolone, a wszystkie zduplikowane elementy są ignorowane.
Przykład
Jawa
// Java program to Adding Elements to HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // AddingElementsToHashSet> class> GFG {> > >// Method 1> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty HashSet of string entities> >HashSet hs =>new> HashSet();> > >// Adding elements using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> > >// Printing all string el=ntries inside the Set> >System.out.println(>'HashSet elements : '> + hs);> >}> }> |
>
>Wyjście:
HashSet elements : [Geek, For, Geeks]>
2. Usuwanie elementów w HashSet
Wartości można usunąć z HashSet za pomocą metody Remove().
Przykład
Jawa
// Java program Illustrating Removal Of Elements of HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // RemoveElementsOfHashSet> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an> >HashSet hs =>new> HashSet();> > >// Adding elements to above Set> >// using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> >hs.add(>'A'>);> >hs.add(>'B'>);> >hs.add(>'Z'>);> > >// Printing the elements of HashSet elements> >System.out.println(>'Initial HashSet '> + hs);> > >// Removing the element B> >hs.remove(>'B'>);> > >// Printing the updated HashSet elements> >System.out.println(>'After removing element '> + hs);> > >// Returns false if the element is not present> >System.out.println(>'Element AC exists in the Set : '> >+ hs.remove(>'AC'>));> >}> }> |
>
>Wyjście:
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Iteracja po zestawie HashSet
Iteruj po elementach HashSet za pomocą metody iterator(). Najbardziej znanym jest również użycie udoskonalona pętla for.
Przykład
Blok kodu
WyjścieA, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Złożoność czasowa operacji HashSet: Podstawowa struktura danych dla HashSet jest hashtable. Zatem amortyzuj (średni lub zwykły przypadek) złożoność czasową operacji dodawania, usuwania i wyszukiwania (zawiera metodę) operacji HashSet O(1) czas.
Wydajność HashSet
HashSet rozszerza klasę Abstract Set i implementuje Ustawić , Możliwość klonowania i Możliwość serializacji interfejsy, gdzie E jest typem elementów obsługiwanych przez ten zbiór. Bezpośrednio znaną podklasą HashSet jest LinkedHashSet .
Teraz, aby utrzymać stałą wydajność w czasie, iteracja po HashSet wymaga czasu proporcjonalnego do sumy rozmiaru instancji HashSet (liczba elementów) plus pojemność instancji bazowej HashMap (liczba segmentów). Dlatego bardzo ważne jest, aby nie ustawiać zbyt dużej pojemności początkowej (lub współczynnika obciążenia zbyt niskiego), jeśli ważna jest wydajność iteracji.
- Pojemność początkowa: Początkowa pojemność oznacza liczbę segmentów, kiedy tworzona jest tablica mieszająca (HashSet wewnętrznie używa struktury danych tablicy mieszającej). Liczba wiader zostanie automatycznie zwiększona, jeśli bieżący rozmiar zostanie zapełniony.
- Współczynnik obciążenia: Współczynnik obciążenia jest miarą tego, jak pełny może być HashSet, zanim jego pojemność zostanie automatycznie zwiększona. Kiedy liczba wpisów w tablicy mieszającej przekracza iloczyn współczynnika obciążenia i aktualnej pojemności, tablica mieszająca jest poddawana ponownemu haszowaniu (tzn. przebudowie wewnętrznych struktur danych), tak aby tabela mieszająca zawierała w przybliżeniu dwukrotnie większą liczbę segmentów.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
Przykład: Jeśli pojemność wewnętrzna wynosi 16, a współczynnik obciążenia wynosi 0,75, liczba segmentów zostanie automatycznie zwiększona, gdy tabela będzie zawierać 12 elementów.
Wpływ na wydajność:
Współczynnik obciążenia i pojemność początkowa to dwa główne czynniki wpływające na wydajność operacji HashSet. Współczynnik obciążenia 0,75 zapewnia bardzo efektywną wydajność pod względem złożoności czasowej i przestrzennej. Jeśli zwiększymy wartość współczynnika obciążenia bardziej, wówczas obciążenie pamięci zostanie zmniejszone (ponieważ zmniejszy to operację wewnętrznego przebudowy), ale będzie to miało wpływ na operację dodawania i wyszukiwania w tablicy mieszającej. Aby ograniczyć operację ponownego mieszania, powinniśmy mądrze wybrać początkową pojemność. Jeśli początkowa pojemność jest większa niż maksymalna liczba wpisów podzielona przez współczynnik obciążenia, operacja ponownego mieszania nigdy nie zostanie wykonana.
Notatka: Implementacja w zestawie HashSet nie jest zsynchronizowana w tym sensie, że jeśli wiele wątków jednocześnie uzyskuje dostęp do zestawu skrótów i co najmniej jeden z wątków modyfikuje zestaw, należy go zsynchronizować zewnętrznie. Zwykle osiąga się to poprzez synchronizację jakiegoś obiektu, który w naturalny sposób otacza zestaw. Jeżeli taki obiekt nie istnieje, zestaw należy opakować metodą Collections.synchronizedSet. Najlepiej zrobić to w momencie tworzenia, aby zapobiec przypadkowemu niezsynchronizowanemu dostępowi do zestawu, jak pokazano poniżej:
Set s = Collections.synchronizedSet(new HashSet(…));
Metody używane z HashSet
1. Metody dziedziczone z klasy java.util.AbstractSet
| metoda | Opis |
|---|---|
| równa się() | Służy do sprawdzania równości obiektu z zestawem HashSet i porównywania ich. Lista zwraca wartość true tylko wtedy, gdy oba HashSet zawierają te same elementy, niezależnie od kolejności. |
| kod skrótu() | Zwraca wartość kodu skrótu dla tego zestawu. |
| usuń wszystko (kolekcja) | Metoda ta służy do usunięcia z kolekcji wszystkich elementów znajdujących się w zbiorze. Ta metoda zwraca wartość true, jeśli ten zestaw ulegnie zmianie w wyniku wywołania. |
2. Metody dziedziczone z klasy java.util.AbstractCollection
| METODA | OPIS |
|---|---|
| dodaj wszystko (kolekcja) | Metoda ta służy do dołączenia wszystkich elementów wspomnianej kolekcji do istniejącego zbioru. Elementy dodawane są losowo, bez zachowania określonej kolejności. |
| zawieraWszystko(kolekcja) | Metoda ta służy do sprawdzenia, czy zbiór zawiera wszystkie elementy występujące w danej kolekcji, czy też nie. Ta metoda zwraca wartość true, jeśli zestaw zawiera wszystkie elementy, i zwraca wartość false, jeśli brakuje któregokolwiek z elementów. |
| zachowaj wszystko (kolekcja) | Metoda ta służy do zachowania wszystkich elementów ze zbioru, które są wymienione w danej kolekcji. Ta metoda zwraca wartość true, jeśli ten zestaw uległ zmianie w wyniku wywołania. |
| do tablicy() | Ta metoda służy do tworzenia tablicy zawierającej te same elementy, co tablica Set. |
| doString() | Metoda toString() Java HashSet służy do zwracania ciągu reprezentującego elementy kolekcji HashSet. |
3. Metody zadeklarowane w interfejsie java.util.Collection
| METODA | OPIS |
|---|---|
| strumień równoległy() | Zwraca prawdopodobnie równoległy Stream z tą kolekcją jako źródłem. |
| usunąćIf?(Filtr predykatów) | Usuwa wszystkie elementy tej kolekcji, które spełniają podany predykat. |
| strumień() | Zwraca sekwencyjny Stream z tą kolekcją jako źródłem. |
| toArray? (Generator funkcji Int) | Zwraca tablicę zawierającą wszystkie elementy w tej kolekcji, korzystając z dostarczonej funkcji generatora w celu alokacji zwróconej tablicy. |
4. Metody zadeklarowane w interfejsie java.lang.Iterable
| METODA | OPIS |
|---|---|
| forEach? (Działanie konsumenckie) | Wykonuje daną akcję dla każdego elementu Iterable, dopóki wszystkie elementy nie zostaną przetworzone lub akcja nie zgłosi wyjątku. |
5. Metody zadeklarowane w interfejsie java.util.Set
| METODA | OPIS |
|---|---|
| dodaćWszystko?(Kolekcja c) | Dodaje do tego zestawu wszystkie elementy z określonej kolekcji, jeśli jeszcze ich nie ma (operacja opcjonalna). |
| zawieraWszystko? (Kolekcja c) | Zwraca wartość true, jeśli ten zestaw zawiera wszystkie elementy określonej kolekcji. |
| równa się? (Obiekt o) | Porównuje określony obiekt z tym zestawem pod kątem równości. |
| hashCode() | Zwraca wartość kodu skrótu dla tego zestawu. |
| usunąćWszystko?(Kolekcja c) | Usuwa z tego zestawu wszystkie jego elementy zawarte w określonej kolekcji (operacja opcjonalna). |
| zachować wszystko? (Kolekcja c) | Zachowuje tylko elementy tego zestawu, które znajdują się w określonej kolekcji (operacja opcjonalna). |
| do tablicy() | Zwraca tablicę zawierającą wszystkie elementy tego zestawu. |
| do tablicy?(T[]a) | Zwraca tablicę zawierającą wszystkie elementy tego zestawu; typem środowiska wykonawczego zwróconej tablicy jest typ określonej tablicy. |
Często zadawane pytania w HashSet w Javie
Pytanie 1. Co to jest HashSet w Javie?
Odpowiedź:
HashSet to typ klasy, który rozszerza AbstractSet i implementuje interfejsy Set.
Pytanie 2. Dlaczego używany jest HashSet?
Odpowiedź:
HashSet służy do unikania duplikatów danych i znajdowania wartości szybką metodą.
Pytanie 3. Różnice między HashSet i HashMap.
Odpowiedź:
| Podstawa | Zestaw skrótów | HashMapa |
|---|---|---|
| Realizacja | HashSet implementuje interfejs Set. | HashMap implementuje interfejs storeMap. |
| Duplikaty | HashSet nie pozwala na powielanie wartości. | HashMap przechowuje pary kluczy i wartości i nie pozwala na duplikowanie kluczy. Jeżeli klucz jest zduplikowany, stary klucz zostaje zastąpiony nową wartością. |
| Liczba obiektów podczas przechowywania obiektów | HashSet wymaga tylko jednego dodania obiektu (Obiekt o). | HashMap wymaga umieszczenia dwóch obiektów (klawisz K, wartość V), aby dodać element do obiektu HashMap. |
| Wartość fikcyjna | HashSet wewnętrznie używa HashMap do dodawania elementów. W HashSet argument przekazany w metodzie add(Object) służy jako klucz K. Java wewnętrznie kojarzy fikcyjną wartość z każdą wartością przekazaną w metodzie add(Object). | HashMap nie ma żadnej koncepcji wartości fikcyjnej. |
| Przechowywanie lub dodawanie mechanizmu | HashSet wewnętrznie używa obiektu HashMap do przechowywania lub dodawania obiektów. | HashMap wewnętrznie używa hashowania do przechowywania lub dodawania obiektów |
| Szybciej | HashSet jest wolniejszy niż HashMap. | HashMap jest szybszy niż HashSet. |
| Wprowadzenie | HashSet używa metody add() do dodawania lub przechowywania danych. | HashMap używa metody put() do przechowywania danych. |
| Przykład | HashSet to zbiór m.in. {1, 2, 3, 4, 5, 6, 7}. | HashMap to mapa pary klucz -> wartość (klucz do wartości), np. {a -> 1, b -> 2, c -> 2, d -> 1}. |
Pytanie 4. Różnice między HashSet i TreeSet w Javie.
Odpowiedź:
| Podstawa | Zestaw skrótów | Zestaw drzew usuwanie ostatniego zatwierdzenia gi |
|---|---|---|
| Szybkość i wewnętrzna realizacja akcji rzutu | Do operacji takich jak wyszukiwanie, wstawianie i usuwanie. Operacje te zajmują średnio stały czas. HashSet jest szybszy niż TreeSet. HashSet jest zaimplementowany przy użyciu tabeli mieszającej. | TreeSet pobiera O(Log n) do wyszukiwania, wstawiania i usuwania, który jest wyższy niż HashSet. Ale TreeSet przechowuje posortowane dane. Obsługuje również operacje takie jak wyżej() (zwraca element o najmniejszym wyższym poziomie), podłoga(), sufit() itp. Te operacje są również O(Log n) w TreeSet i nie są obsługiwane w HashSet. TreeSet jest zaimplementowany przy użyciu samobalansującego drzewa wyszukiwania binarnego (drzewo czerwono-czarne). TreeSet jest wspierany przez TreeMap w Javie. |
| Zamawianie | Elementy w HashSet nie są uporządkowane. | TreeSet utrzymuje obiekty w kolejności sortowania określonej metodą Comparable lub Comparator w Javie. Elementy TreeSet są domyślnie sortowane w kolejności rosnącej. Oferuje kilka metod radzenia sobie z uporządkowanym zestawem, takich jak First(), Last(), headSet(), tailSet() itp. |
| Obiekt zerowy | HashSet zezwala na obiekt zerowy. | TreeSet nie zezwala na obiekt o wartości null i zgłasza wyjątek NullPointerException. Dlaczego, TreeSet używa metody CompareTo() do porównywania kluczy, a CompareTo() zgłasza wyjątek java.lang.NullPointerException. |
| Porównanie | HashSet używa metody równości() do porównywania dwóch obiektów w zestawie i do wykrywania duplikatów. | TreeSet używa metody CompareTo() w tym samym celu. Jeśli metodyquals() i CompareTo() nie są spójne, tj. dla dwóch równych obiektów równanie powinno zwrócić wartość true, a CompareTo() powinno zwrócić zero, wówczas zerwie to umowę interfejsu Set i umożliwi duplikaty w implementacjach Set, takich jak TreeSet |