Java HashSet class implementa la interfície Set, recolzada per una taula hash que en realitat és una instància HashMap. No es garanteix l'ordre d'iteració dels conjunts hash, la qual cosa significa que la classe no garanteix l'ordre constant dels elements al llarg del temps. Aquesta classe permet l'element nul. La classe també ofereix un rendiment de temps constant per a les operacions bàsiques com afegir, eliminar, contenir i mida, assumint que la funció hash dispersa els elements correctament entre els cubs, que veurem més endavant a l'article.
Característiques de Java HashSet
A continuació s'esmenten algunes característiques importants de HashSet:
- Implements Estableix la interfície .
- L'estructura de dades subjacent per a HashSet és Taula hash .
- Com que implementa la interfície Set, no es permeten valors duplicats.
- No es garanteix que els objectes que inseriu a HashSet s'insereixin en el mateix ordre. Els objectes s'insereixen en funció del seu codi hash.
- Els elements NULL estan permesos a HashSet.
- HashSet també implementa Serialitzable i Clonable interfícies.
Declaració de HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
on I és el tipus d'elements emmagatzemats en un HashSet.
Exemple de Java HashSet
Java
// 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());> >}> }> |
retornant una matriu java
>
>Sortida:
1>
Abans d'emmagatzemar un objecte, HashSet comprova si hi ha una entrada existent mitjançant els mètodes hashCode() i equals(). En l'exemple anterior, dues llistes es consideren iguals si tenen els mateixos elements en el mateix ordre. Quan invoqueu el hashCode() mètode a les dues llistes, tots dos donarien el mateix hash ja que són iguals.
Nota: HashSet ho fa no emmagatzemar articles duplicats , si doneu dos Objectes que són iguals, només emmagatzema el primer, aquí és list1.
La jerarquia de HashSet és la següent:
Funcionament intern d'un HashSet
Totes les classes de la interfície Set tenen una còpia de seguretat interna de Map. HashSet utilitza HashMap per emmagatzemar el seu objecte internament. Us heu de preguntar que per introduir un valor a HashMap necessitem un parell clau-valor, però a HashSet només estem passant un valor.
Emmagatzematge a HashMap: De fet, el valor que inserim a HashSet actua com a clau per a l'objecte del mapa i per al seu valor, java utilitza una variable constant. Per tant, a la parella clau-valor, tots els valors seran iguals.
Implementació de HashSet a Java 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();> Si mirem el afegir() mètode de la classe HashSet:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Podem notar que el mètode add() de la classe HashSet crida internament al posar() mètode de suport de l'objecte HashMap passant l'element que heu especificat com a clau i la constant PRESENT com a valor. eliminar () El mètode també funciona de la mateixa manera. Crida internament al mètode remove de la interfície Map.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet no només emmagatzema objectes únics, sinó també una col·lecció única d'objectes M'agrada ArrayList , LinkedList , Vector ,...etc.
Constructors de la classe HashSet
Per crear un HashSet, hem de crear un objecte de la classe HashSet. La classe HashSet consta de diversos constructors que permeten la possible creació del HashSet. A continuació es mostren els constructors disponibles en aquesta classe.
1. HashSet()
Aquest constructor s'utilitza per construir un objecte HashSet buit en el qual la capacitat inicial predeterminada és 16 i el factor de càrrega predeterminat és 0,75. Si volem crear un HashSet buit amb el nom hs, es pot crear com:
HashSet hs = new HashSet();>
2. HashSet(int initialCapacity)
Aquest constructor s'utilitza per construir un objecte HashSet buit en el qual s'especifica la capacitat inicial en el moment de la creació de l'objecte. Aquí, el loadFactor per defecte segueix sent 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet(int initialCapacity, float loadFactor)
Aquest constructor s'utilitza per construir un objecte HashSet buit en el qual s'especifiquen inicialCapacity i loadFactor en el moment de la creació de l'objecte.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet (Col·lecció)
Aquest constructor s'utilitza per construir un objecte HashSet que conté tots els elements de la col·lecció donada. En resum, aquest constructor s'utilitza quan es necessita qualsevol conversió des de qualsevol objecte Collection a l'objecte HashSet. Si volem crear un HashSet amb el nom hs, es pot crear com:
HashSet hs = new HashSet(Collection C);>
A continuació es mostra la implementació dels temes anteriors:
Java
// 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());> >}> }> |
>
>Sortida:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Mètodes a HashSet
| MÈTODE | DESCRIPCIÓ |
|---|---|
| afegir (I i) | S'utilitza per afegir l'element especificat si no està present, si està present, retorna false. |
| clar () | S'utilitza per eliminar tots els elements del conjunt. |
| conté (Objecte o) | S'utilitza per retornar true si un element està present en un conjunt. |
| eliminar (Objecte o) | S'utilitza per eliminar l'element si està present al conjunt. |
| iterador() | S'utilitza per retornar un iterador sobre l'element del conjunt. |
| està buit() | S'utilitza per comprovar si el conjunt està buit o no. Retorna true per buit i fals per a una condició no buida per a conjunt. |
| mida () | S'utilitza per retornar la mida del conjunt. |
| clonar () | S'utilitza per crear una còpia poc profunda del conjunt. |
Realització de diverses operacions en HashSet
Vegem com realitzar algunes operacions d'ús freqüent al HashSet.
1. Afegir elements a HashSet
Per afegir un element al HashSet, podem utilitzar el mètode add() . Tanmateix, l'ordre d'inserció no es conserva al HashSet. Hem de tenir una nota que els elements duplicats no es permeten i tots els elements duplicats s'ignoren.
Exemple
Java
// 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);> >}> }> |
>
>Sortida:
HashSet elements : [Geek, For, Geeks]>
2. Eliminació d'elements a HashSet
Els valors es poden eliminar del HashSet mitjançant el mètode remove().
Exemple
Java
// 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'>));> >}> }> |
>
>Sortida:
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Iterant a través del HashSet
Itereu pels elements de HashSet utilitzant el mètode iterator(). A més, el més famós és utilitzar el millorat per bucle.
Exemple
Bloc de codi
SortidaA, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Complexitat temporal de les operacions de HashSet: L'estructura de dades subjacent per a HashSet és hashtable. Per tant, amortitzeu (mitjana o cas habitual) la complexitat del temps per afegir, eliminar i cercar (conté el mètode) l'operació de HashSet. O(1) temps.
Rendiment de HashSet
HashSet amplia la classe Abstract Set i els implementa Conjunt , Clonable i Serialitzable interfícies on E és el tipus d'elements mantinguts per aquest conjunt. La subclasse coneguda directament de HashSet és LinkedHashSet .
Ara, per mantenir un rendiment de temps constant, la iteració sobre HashSet requereix un temps proporcional a la suma de la mida de la instància HashSet (el nombre d'elements) més la capacitat de la instància HashMap de suport (el nombre de cubs). Per tant, és molt important no establir la capacitat inicial massa alta (o el factor de càrrega massa baix) si el rendiment de la iteració és important.
- Capacitat inicial: La capacitat inicial significa el nombre de cubs quan es crea la taula hash (HashSet utilitza internament l'estructura de dades de la taula hash). El nombre de galledes augmentarà automàticament si la mida actual s'omple.
- Factor de càrrega: El factor de càrrega és una mesura de fins a quin punt es permet que el HashSet arribi abans que la seva capacitat s'augmenti automàticament. Quan el nombre d'entrades a la taula hash supera el producte del factor de càrrega i la capacitat actual, la taula hash es torna a repetir (és a dir, es reconstrueixen les estructures de dades internes) de manera que la taula hash tingui aproximadament el doble de cubs.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
Exemple: Si la capacitat interna és de 16 i el factor de càrrega és de 0,75, el nombre de galledes augmentarà automàticament quan la taula tingui 12 elements.
Efecte sobre el rendiment:
El factor de càrrega i la capacitat inicial són dos factors principals que afecten el rendiment de les operacions HashSet. Un factor de càrrega de 0,75 proporciona un rendiment molt efectiu pel que fa a la complexitat temporal i espacial. Si augmentem el valor del factor de càrrega més que això, la sobrecàrrega de memòria es reduirà (perquè disminuirà l'operació de reconstrucció interna), però afectarà l'operació d'addició i cerca a la taula hash. Per reduir l'operació de repetició, hauríem de triar la capacitat inicial amb prudència. Si la capacitat inicial és superior al nombre màxim d'entrades dividit pel factor de càrrega, mai es produirà cap operació de repetició.
Nota: La implementació en un HashSet no està sincronitzada, en el sentit que si diversos fils accedeixen a un conjunt hash simultàniament, i almenys un dels fils modifica el conjunt, s'ha de sincronitzar externament. Això s'aconsegueix normalment sincronitzant-se en algun objecte que encapsula el conjunt de manera natural. Si no existeix aquest objecte, el conjunt s'ha d'embolicar mitjançant el mètode Collections.synchronizedSet. Això es fa millor en el moment de la creació, per evitar l'accés accidental no sincronitzat al conjunt, tal com es mostra a continuació:
Set s = Collections.synchronizedSet(new HashSet(…));
tipus de bucle for
Mètodes utilitzats amb HashSet
1. Mètodes heretats de la classe java.util.AbstractSet
| Mètode | Descripció |
|---|---|
| és igual() | S'utilitza per verificar la igualtat d'un objecte amb un HashSet i comparar-los. La llista només retorna true si tots dos HashSet contenen els mateixos elements, independentment de l'ordre. |
| codi hash() | Retorna el valor del codi hash per a aquest conjunt. |
| removeAll (col·lecció) | Aquest mètode s'utilitza per eliminar tots els elements de la col·lecció que estan presents al conjunt. Aquest mètode retorna true si aquest conjunt canvia com a resultat de la trucada. |
2. Mètodes heretats de la classe java.util.AbstractCollection
| MÈTODE | DESCRIPCIÓ |
|---|---|
| addAll (col·lecció) | Aquest mètode s'utilitza per afegir tots els elements de la col·lecció esmentada al conjunt existent. Els elements s'afegeixen aleatòriament sense seguir cap ordre específic. |
| conté tot (col·lecció) | Aquest mètode s'utilitza per comprovar si el conjunt conté tots els elements presents a la col·lecció donada o no. Aquest mètode retorna true si el conjunt conté tots els elements i retorna false si falta algun dels elements. |
| retainAll (col·lecció) | Aquest mètode s'utilitza per retenir tots els elements del conjunt que s'esmenten a la col·lecció donada. Aquest mètode retorna true si aquest conjunt ha canviat com a resultat de la trucada. |
| toArray() | Aquest mètode s'utilitza per formar una matriu dels mateixos elements que el del conjunt. |
| toString() | El mètode toString() de Java HashSet s'utilitza per retornar una representació de cadena dels elements de la col·lecció HashSet. |
3. Mètodes declarats a la interfície java.util.Collection
| MÈTODE | DESCRIPCIÓ |
|---|---|
| parallelStream() | Retorna un flux possiblement paral·lel amb aquesta col·lecció com a font. |
| removeIf? (filtre de predicats) | Elimina tots els elements d'aquesta col·lecció que compleixen el predicat donat. |
| corrent() | Retorna un flux seqüencial amb aquesta col·lecció com a font. |
| toArray? (generador d'IntFunction) | Retorna una matriu que conté tots els elements d'aquesta col·lecció, utilitzant la funció generadora proporcionada per assignar la matriu retornada. |
4. Mètodes declarats a la interfície java.lang.Iterable
| MÈTODE | DESCRIPCIÓ |
|---|---|
| per a cadascú? (acció del consumidor) | Realitza l'acció donada per a cada element de l'iterable fins que s'han processat tots els elements o l'acció genera una excepció. |
5. Mètodes declarats a la interfície java.util.Set
| MÈTODE | DESCRIPCIÓ |
|---|---|
| afegirAll? (Col·lecció c) | Afegeix tots els elements de la col·lecció especificada a aquest conjunt si encara no estan presents (operació opcional). |
| conté tot? (Col·lecció c) | Retorna true si aquest conjunt conté tots els elements de la col·lecció especificada. |
| és igual? (Objecte o) | Compara l'objecte especificat amb aquest conjunt per a la igualtat. |
| hashCode() | Retorna el valor del codi hash per a aquest conjunt. |
| removeAll? (Col·lecció c) | Elimina d'aquest conjunt tots els seus elements que estan continguts a la col·lecció especificada (operació opcional). |
| retainAll? (Col·lecció c) | Reté només els elements d'aquest conjunt que estan continguts a la col·lecció especificada (operació opcional). |
| toArray() | Retorna una matriu que conté tots els elements d'aquest conjunt. |
| toArray? (T[] a) | Retorna una matriu que conté tots els elements d'aquest conjunt; el tipus d'execució de la matriu retornada és el de la matriu especificada. |
Preguntes freqüents a HashSet a Java
Q1. Què és HashSet a Java?
Resposta:
HashSet és un tipus de classe, que amplia AbstractSet i implementa interfícies Set.
P2. Per què s'utilitza HashSet?
Resposta:
HashSet s'utilitza per evitar dades duplicades i per trobar valor amb el mètode ràpid.
P3. Diferències entre HashSet i HashMap.
Resposta:
| Base | HashSet | HashMap |
|---|---|---|
| Implementació | HashSet implementa una interfície Set. | HashMap implementa una interfície storesMap. |
| Duplicats | HashSet no permet valors duplicats. | HashMap emmagatzema els parells clau i valor i no permet claus duplicades. Si la clau està duplicada, la clau antiga es substitueix pel nou valor. |
| Nombre d'objectes durant l'emmagatzematge d'objectes | HashSet només requereix un objecte add(Object o). | HashMap requereix posar dos objectes (clau K, valor V) per afegir un element a l'objecte HashMap. |
| Valor fictici | HashSet utilitza internament HashMap per afegir elements. A HashSet, l'argument passat al mètode add(Object) serveix com a clau K. Java associa internament un valor fictici per a cada valor passat al mètode add(Object). | HashMap no té cap concepte de valor fictici. |
| Emmagatzemar o afegir un mecanisme | HashSet utilitza internament l'objecte HashMap per emmagatzemar o afegir els objectes. | HashMap utilitza internament hashing per emmagatzemar o afegir objectes |
| Més ràpid | HashSet és més lent que HashMap. | HashMap és més ràpid que HashSet. |
| Inserció | HashSet utilitza el mètode add() per afegir o emmagatzemar dades. | HashMap utilitza el mètode put() per emmagatzemar dades. |
| Exemple | HashSet és un conjunt, p. {1, 2, 3, 4, 5, 6, 7}. | HashMap és un mapa clau -> parell de valors (clau a valor), p. {a -> 1, b -> 2, c -> 2, d -> 1}. |
P4. Diferències entre HashSet i TreeSet a Java.
Resposta:
| Base | HashSet | Conjunt d'arbres |
|---|---|---|
| Velocitat i implementació interna de l'acció de llançament | Per a operacions com cercar, inserir i suprimir. Aquestes operacions requereixen un temps constant de mitjana. HashSet és més ràpid que TreeSet. HashSet s'implementa mitjançant una taula hash. | TreeSet pren O (Log n) per cercar, inserir i suprimir, que és superior a HashSet. Però TreeSet manté les dades ordenades. A més, admet operacions com higher() (Retorna l'element més alt), floor(), ceiling(), etc. Aquestes operacions també són O(Log n) a TreeSet i no s'admeten a HashSet. TreeSet s'implementa mitjançant un arbre de cerca binari d'autoequilibri (arbre vermell-negre). TreeSet està recolzat per TreeMap a Java. |
| Encàrrec | Els elements de HashSet no estan ordenats. | TreeSet manté els objectes en ordre ordenat definit pel mètode Comparable o Comparator a Java. Els elements del TreeSet s'ordenen per defecte en ordre ascendent. Ofereix diversos mètodes per tractar el conjunt ordenat com ara first(), last(), headSet(), tailSet(), etc. |
| Objecte nul | HashSet permet l'objecte nul. | TreeSet no permet objectes nuls i llança NullPointerException, perquè, perquè TreeSet utilitza el mètode compareTo() per comparar claus, i compareTo() llançarà java.lang.NullPointerException. |
| Comparació | HashSet utilitza el mètode equals() per comparar dos objectes del conjunt i per detectar duplicats. | TreeSet utilitza el mètode compareTo() amb el mateix propòsit. Si equals() i compareTo() no són coherents, és a dir, per a dos objectes iguals equals hauria de tornar cert mentre compareTo() hauria de tornar zero, aleshores trencarà el contracte de la interfície Set i permetrà duplicats en implementacions de Set com TreeSet |