Java HashSet třída implementuje rozhraní Set, podporované hashovací tabulkou, která je ve skutečnosti instancí HashMap. Není zaručeno pořadí iterací sad hash, což znamená, že třída nezaručuje konstantní pořadí prvků v průběhu času. Tato třída povoluje prvek null. Třída také nabízí konstantní časový výkon pro základní operace, jako je přidat, odebrat, obsahovat a velikost za předpokladu, že hashovací funkce správně rozmístí prvky mezi kbelíky, což uvidíme dále v článku.
Funkce Java HashSet
Níže je uvedeno několik důležitých funkcí HashSet:
- Provádí Nastavit rozhraní .
- Základní datová struktura pro HashSet je Hashtable .
- Protože implementuje rozhraní Set Interface, duplicitní hodnoty nejsou povoleny.
- U objektů, které vložíte do HashSet, není zaručeno, že budou vloženy ve stejném pořadí. Objekty jsou vkládány na základě jejich hash kódu.
- Prvky NULL jsou v HashSet povoleny.
- HashSet také implementuje Serializovatelné a Klonovatelné rozhraní.
Deklarace HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
kde A je typ prvků uložených v HashSet.
Příklad HashSet Java
Jáva
// 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());> >}> }> |
mylivecricket.in
>
>Výstup:
1>
Před uložením objektu HashSet zkontroluje, zda existuje existující záznam pomocí metod hashCode() a equals(). Ve výše uvedeném příkladu jsou dva seznamy považovány za rovnocenné, pokud mají stejné prvky ve stejném pořadí. Když vyvoláte hashCode() metoda na dvou seznamech, oba by daly stejný hash, protože jsou stejné.
Poznámka: HashSet ano neukládat duplicitní položky , pokud dáte dva objekty, které jsou stejné, uloží se pouze první, zde je seznam1.
Hierarchie HashSet je následující:
Interní fungování HashSet
Všechny třídy rozhraní Set jsou interně zálohovány pomocí Map. HashSet používá HashMap pro interní ukládání svého objektu. Určitě vás zajímá, že k zadání hodnoty do HashMap potřebujeme pár klíč-hodnota, ale v HashSet předáváme pouze jednu hodnotu.
Úložiště v HashMap: Ve skutečnosti hodnota, kterou vložíme do HashSet, funguje jako klíč k objektu mapy a pro její hodnotu používá java konstantní proměnnou. Takže v páru klíč–hodnota budou všechny hodnoty stejné.
Implementace HashSet v Javě doc
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();> Pokud se podíváme na přidat() metoda třídy HashSet:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Můžeme si všimnout, že metoda add() třídy HashSet interně volá dát() metoda zálohování objektu HashMap předáním prvku, který jste zadali jako klíč, a konstanty PRESENT jako jeho hodnoty. odstranit() metoda také funguje stejným způsobem. Interně volá metodu remove rozhraní mapy.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet nejen ukládá jedinečné objekty, ale také jedinečnou sbírku objektů jako ArrayList , Spojový seznam , Vektor ,..atd.
Konstruktory třídy HashSet
Abychom vytvořili HashSet, musíme vytvořit objekt třídy HashSet. Třída HashSet se skládá z různých konstruktorů, které umožňují možné vytvoření HashSet. Níže jsou uvedeny konstruktory dostupné v této třídě.
1. HashSet()
Tento konstruktor se používá k vytvoření prázdného objektu HashSet, ve kterém je výchozí počáteční kapacita 16 a výchozí faktor zatížení je 0,75. Pokud chceme vytvořit prázdnou sadu HashSet s názvem hs, lze ji vytvořit jako:
HashSet hs = new HashSet();>
2. HashSet (int initialCapacity)
Tento konstruktor se používá k vytvoření prázdného objektu HashSet, ve kterém je počáteční kapacita specifikována v době vytvoření objektu. Zde zůstává výchozí loadFactor 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet (int initialCapacity, float loadFactor)
Tento konstruktor se používá k sestavení prázdného objektu HashSet, ve kterém jsou v době vytváření objektu zadány počáteční kapacita a loadFactor.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet (kolekce)
Tento konstruktor se používá k sestavení objektu HashSet obsahujícího všechny prvky z dané kolekce. Stručně řečeno, tento konstruktor se používá, když je potřeba jakýkoli převod z jakéhokoli objektu Collection na objekt HashSet. Pokud chceme vytvořit HashSet s názvem hs, může být vytvořen jako:
HashSet hs = new HashSet(Collection C);>
Níže je uvedena implementace výše uvedených témat:
Jáva
// 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());> >}> }> |
>
>Výstup:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Metody v HashSet
| METODA | POPIS |
|---|---|
| přidat (a a) | Používá se k přidání zadaného prvku, pokud není přítomen, pokud je přítomen, vrátí hodnotu false. |
| Průhledná() | Používá se k odstranění všech prvků ze sady. |
| obsahuje (Objekt o) | Používá se k vrácení true, pokud je prvek přítomen v sadě. |
| odstranit (objekt o) | Používá se k odstranění prvku, pokud je přítomen v sadě. |
| iterátor() | Používá se k vrácení iterátoru nad prvkem v sadě. |
| je prázdný() | Slouží ke kontrole, zda je sada prázdná nebo ne. Vrátí true pro prázdnou a false pro neprázdnou podmínku pro sadu. |
| velikost() | Slouží k vrácení velikosti sady. |
| klon() | Používá se k vytvoření mělké kopie sady. |
Provádění různých operací na HashSet
Podívejme se, jak provést několik často používaných operací na HashSet.
1. Přidání prvků do HashSet
K přidání prvku do HashSet můžeme použít metodu add() . Objednávka vložení však není zachována v HashSet. Musíme si uvědomit, že duplicitní prvky nejsou povoleny a všechny duplicitní prvky jsou ignorovány.
Příklad
Jáva
// 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);> >}> }> |
>
>Výstup:
HashSet elements : [Geek, For, Geeks]>
2. Odebrání prvků v HashSet
Hodnoty lze ze sady HashSet odstranit pomocí metody remove().
Příklad
Jáva
// 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'>));> >}> }> |
>
>Výstup:
integer double java
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Iterace přes HashSet
Iterujte prvky HashSet pomocí metody iterator(). Nejznámější z nich je také použití vylepšená smyčka for.
Příklad
Blok kódu
VýstupA, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Časová náročnost operací HashSet: Základní datová struktura pro HashSet je hashtable. Takže amortizujte (průměrný nebo obvyklý případ) časovou složitost pro přidání, odebrání a vyhledání (obsahuje metodu) operace HashSet O(1) čas.
Výkon HashSet
HashSet rozšiřuje třídu Abstract Set a implementuje Soubor , klonovatelné a Serializovatelné rozhraní, kde E je typ prvků udržovaných touto sadou. Přímo známá podtřída HashSet je LinkedHashSet .
Nyní pro udržení konstantního časového výkonu vyžaduje iterace přes HashSet čas úměrný součtu velikosti instance HashSet (počet prvků) plus kapacita záložní instance HashMap (počet bucketů). Je tedy velmi důležité nenastavit počáteční kapacitu příliš vysoko (nebo příliš nízký faktor zatížení), pokud je důležitý výkon iterace.
- Počáteční kapacita: Počáteční kapacita znamená počet bucketů při vytvoření hashtable (HashSet interně používá hashtable datovou strukturu). Počet segmentů se automaticky zvýší, pokud se zaplní aktuální velikost.
- Faktor zatížení: Faktor zatížení je měřítkem toho, jak plné se může HashSet naplnit, než se automaticky zvýší jeho kapacita. Když počet záznamů v hašovací tabulce překročí součin faktoru zatížení a aktuální kapacity, hašovací tabulka je přehashována (tj. vnitřní datové struktury jsou přestavěny), takže hašovací tabulka má přibližně dvojnásobný počet bucketů.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
Příklad: Pokud je vnitřní kapacita 16 a faktor zatížení je 0,75, počet lopat se automaticky zvýší, když stůl obsahuje 12 prvků.
Vliv na výkon:
Faktor zatížení a počáteční kapacita jsou dva hlavní faktory, které ovlivňují výkon operací HashSet. Faktor zatížení 0,75 poskytuje velmi efektivní výkon s ohledem na časovou a prostorovou složitost. Pokud zvýšíme hodnotu zátěžového faktoru více, pak se režie paměti sníží (protože se sníží operace vnitřní přestavby), ale ovlivní to operaci přidání a vyhledávání v hashtable. Abychom omezili operaci přehánění, měli bychom počáteční kapacitu zvolit moudře. Pokud je počáteční kapacita větší než maximální počet položek vydělený faktorem zatížení, nikdy nedojde k žádné opakované operaci.
Poznámka: Implementace v HashSet není synchronizovaná v tom smyslu, že pokud k sadě hash přistupuje více vláken současně a alespoň jedno z vláken sadu upravuje, musí být synchronizována externě. Toho je obvykle dosaženo synchronizací na nějakém objektu, který přirozeně zapouzdřuje sadu. Pokud žádný takový objekt neexistuje, měla by být sada zabalena pomocí metody Collections.synchronizedSet. To se nejlépe provádí při vytváření, aby se zabránilo náhodnému nesynchronizovanému přístupu k sadě, jak je znázorněno níže:
Set s = Collections.synchronizedSet(new HashSet(…));
Metody používané s HashSet
1. Metody zděděné z třídy java.util.AbstractSet
| Metoda | Popis |
|---|---|
| rovná se() | Používá se k ověření rovnosti objektu s HashSet a jejich porovnání. Seznam vrátí hodnotu true pouze v případě, že obě sady HashSet obsahují stejné prvky, bez ohledu na pořadí. |
| hashcode() | Vrátí hodnotu hash kódu pro tuto sadu. |
| odstranit vše (kolekce) | Tato metoda se používá k odstranění všech prvků z kolekce, které jsou přítomny v sadě. Tato metoda vrátí hodnotu true, pokud se tato sada změní v důsledku volání. |
2. Metody zděděné z třídy java.util.AbstractCollection
| METODA | POPIS |
|---|---|
| addAll(kolekce) | Tato metoda se používá k připojení všech prvků ze zmíněné kolekce k existující sadě. Prvky se přidávají náhodně, aniž by se řídily konkrétním pořadím. |
| obsahuje vše (kolekce) | Tato metoda se používá ke kontrole, zda sada obsahuje všechny prvky přítomné v dané kolekci nebo ne. Tato metoda vrátí hodnotu true, pokud sada obsahuje všechny prvky, a vrátí hodnotu false, pokud některý z prvků chybí. |
| zachovat vše (kolekce) | Tato metoda slouží k zachování všech prvků ze sady, které jsou v dané kolekci uvedeny. Tato metoda vrátí hodnotu true, pokud se tato sada v důsledku volání změnila. |
| toArray() | Tato metoda se používá k vytvoření pole stejných prvků jako sada. |
| toString() | Metoda toString() Java HashSet se používá k vrácení řetězcové reprezentace prvků kolekce HashSet. |
3. Metody deklarované v rozhraní java.util.Collection
| METODA | POPIS |
|---|---|
| paralelní proud() | Vrátí možná paralelní proud s touto sbírkou jako zdrojem. |
| removeIf? (Predikátový filtr) | Odebere všechny prvky této kolekce, které splňují daný predikát. |
| proud() | Vrátí sekvenční stream s touto sbírkou jako zdrojem. |
| toArray? (generátor IntFunction) | Vrátí pole obsahující všechny prvky v této kolekci pomocí poskytnuté funkce generátoru k přidělení vráceného pole. |
4. Metody deklarované v rozhraní java.lang.Iterable
| METODA | POPIS |
|---|---|
| pro každého? (spotřebitelská akce) | Provede danou akci pro každý prvek Iterable, dokud nejsou zpracovány všechny prvky nebo akce nevyvolá výjimku. |
5. Metody deklarované v rozhraní java.util.Set
| METODA | POPIS |
|---|---|
| addAll? (Kolekce c) | Přidá do této sady všechny prvky v zadané kolekci, pokud ještě nejsou přítomny (volitelná operace). |
| obsahuje vše? (kolekce c) | Vrátí hodnotu true, pokud tato sada obsahuje všechny prvky zadané kolekce. |
| rovná se? (Objekt o) | Porovná zadaný objekt s touto množinou pro rovnost. |
| hashCode() | Vrátí hodnotu hash kódu pro tuto sadu. |
| odstranit vše? (kolekce c) | Odebere z této sady všechny její prvky, které jsou obsaženy v zadané kolekci (volitelná operace). |
| keepAll? (Kolekce c) | Zachová pouze prvky v této sadě, které jsou obsaženy v zadané kolekci (volitelná operace). |
| toArray() | Vrátí pole obsahující všechny prvky v této sadě. |
| toArray?(T[] a) | Vrátí pole obsahující všechny prvky v této sadě; typ runtime vráceného pole je typ zadaného pole. |
Nejčastější dotazy v HashSet v Javě
Q1. Co je HashSet v Javě?
Odpovědět:
HashSet je typ třídy, který rozšiřuje AbstractSet a implementuje rozhraní Set.
Q2. Proč se používá HashSet?
Odpovědět:
HashSet se používá k zamezení duplicitních dat a k nalezení hodnoty rychlou metodou.
Q3. Rozdíly mezi HashSet a HashMap.
Odpovědět:
| Základ | HashSet | HashMap |
|---|---|---|
| Implementace | HashSet implementuje rozhraní Set. | HashMap implementuje rozhraní storeMap. |
| Duplikáty | HashSet neumožňuje duplicitní hodnoty. | HashMap ukládá páry klíčů a hodnot a neumožňuje duplicitní klíče. Pokud je klíč duplicitní, je starý klíč nahrazen novou hodnotou. |
| Počet objektů při ukládání objektů | HashSet vyžaduje pouze jeden objekt add(Object o). | HashMap vyžaduje dva objekty put (klíč K, hodnota V) k přidání prvku do objektu HashMap. |
| Falešná hodnota | HashSet interně používá HashMap k přidávání prvků. V HashSet slouží argument předaný v metodě add(Object) jako klíč K. Java interně přidružuje fiktivní hodnotu pro každou hodnotu předávanou v metodě add(Object). | HashMap nemá žádný koncept fiktivní hodnoty. |
| Uložení nebo přidání mechanismu | HashSet interně používá objekt HashMap k ukládání nebo přidávání objektů. | HashMap interně používá hash k ukládání nebo přidávání objektů |
| Rychleji | HashSet je pomalejší než HashMap. | HashMap je rychlejší než HashSet. |
| Vložení | HashSet používá metodu add() pro přidávání nebo ukládání dat. | HashMap používá pro ukládání dat metodu put(). |
| Příklad | HashSet je sada, např. {1, 2, 3, 4, 5, 6, 7}. | HashMap je mapa klíč -> pár hodnot (klíč k hodnotě), např. {a -> 1, b -> 2, c -> 2, d -> 1}. |
Q4. Rozdíly mezi HashSet a TreeSet v Javě.
Odpovědět:
| Základ | HashSet | TreeSet |
|---|---|---|
| Rychlost a vnitřní provedení, házení akce | Pro operace, jako je vyhledávání, vkládání a mazání. Tyto operace v průměru zaberou konstantní čas. HashSet je rychlejší než TreeSet. HashSet je implementován pomocí hash tabulky. | TreeSet bere O(Log n) pro vyhledávání, vkládání a mazání, které je vyšší než HashSet. Ale TreeSet uchovává setříděná data. Také podporuje operace jako vyšší() (Vrátí nejméně vyšší prvek), podlaha(), strop() atd. Tyto operace jsou také O(Log n) v TreeSet a nejsou podporovány v HashSet. TreeSet je implementován pomocí samovyvažujícího binárního vyhledávacího stromu (červeno-černý strom). TreeSet je podporován TreeMap v Javě. |
| Objednávání | Prvky v HashSet nejsou seřazeny. | TreeSet udržuje objekty v seřazeném pořadí definovaném buď metodou Comparable nebo Comparator v Javě. Prvky TreeSet jsou standardně seřazeny ve vzestupném pořadí. Nabízí několik metod, jak se vypořádat s uspořádanou sadou, jako je first(), last(), headSet(), tailSet() atd. |
| Objekt Null | HashSet umožňuje nulový objekt. | TreeSet nepovoluje null Object a vyvolá výjimku NullPointerException, Why, protože TreeSet používá k porovnání klíčů metodu CompareTo() a CompareTo() vyvolá výjimku java.lang.NullPointerException. |
| Srovnání | HashSet používá metodu equals() k porovnání dvou objektů v sadě a k detekci duplikátů. | TreeSet používá pro stejný účel metodu CompareTo(). Pokud funkce equals() a CompareTo() nejsou konzistentní, tj. pro dva stejné objekty by funkce equals měla vrátit hodnotu true, zatímco funkce CompareTo() by měla vrátit nulu, poruší to smlouvu rozhraní Set a umožní duplikáty v implementacích sady, jako je TreeSet. |