Jeu de hachage Java La classe implémente l'interface Set, soutenue par une table de hachage qui est en fait une instance de HashMap. Aucune garantie n'est faite quant à l'ordre d'itération des jeux de hachage, ce qui signifie que la classe ne garantit pas l'ordre constant des éléments dans le temps. Cette classe autorise l'élément null. La classe offre également des performances en temps constant pour les opérations de base telles que l'ajout, la suppression, le contenu et la taille en supposant que la fonction de hachage disperse correctement les éléments entre les compartiments, ce que nous verrons plus loin dans l'article.

Fonctionnalités Java HashSet

Quelques fonctionnalités importantes de HashSet sont mentionnées ci-dessous :

• Met en oeuvre Définir l'interface .
• La structure de données sous-jacente pour HashSet est Table de hachage .
• Comme il implémente l'interface Set, les valeurs en double ne sont pas autorisées.
• Il n'est pas garanti que les objets que vous insérez dans HashSet soient insérés dans le même ordre. Les objets sont insérés en fonction de leur code de hachage.
• Les éléments NULL sont autorisés dans HashSet.
• HashSet implémente également Sérialisable et Clonable interfaces.

Déclaration de HashSet

public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>

où ET est le type d'éléments stockés dans un HashSet.

Exemple Java de HashSet

Java

chaîne java en json

>

>

1>

Avant de stocker un objet, HashSet vérifie s'il existe une entrée existante à l'aide des méthodes hashCode() et equals(). Dans l’exemple ci-dessus, deux listes sont considérées comme égales si elles contiennent les mêmes éléments dans le même ordre. Lorsque vous invoquez le code de hachage() méthode sur les deux listes, elles donneraient toutes les deux le même hachage puisqu’elles sont égales.

Note: HashSet fait ne pas stocker les éléments en double , si vous donnez deux objets égaux, il ne stocke que le premier, ici list1.

La hiérarchie de HashSet est la suivante :

Fonctionnement interne d'un HashSet

Toutes les classes de l'interface Set sont sauvegardées en interne par Map. HashSet utilise HashMap pour stocker son objet en interne. Vous devez vous demander que pour saisir une valeur dans HashMap, nous avons besoin d'une paire clé-valeur, mais dans HashSet, nous ne transmettons qu'une seule valeur.

Stockage dans HashMap : En fait, la valeur que nous insérons dans HashSet agit comme une clé de l'objet map et pour sa valeur, Java utilise une variable constante. Ainsi, dans la paire clé-valeur, toutes les valeurs seront les mêmes.

Implémentation de HashSet dans la documentation 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();>

Si nous regardons le ajouter() méthode de la classe HashSet :

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

On peut remarquer que la méthode add() de la classe HashSet appelle en interne le mettre() méthode de sauvegarde de l'objet HashMap en passant l'élément que vous avez spécifié comme clé et la constante PRESENT comme valeur. retirer() la méthode fonctionne également de la même manière. Il appelle en interne la méthode Remove de l’interface Map.

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

HashSet stocke non seulement des objets uniques, mais également une collection unique d'objets comme Liste des tableaux , Liste liée , Vecteur,..etc.

Constructeurs de la classe HashSet

Pour créer un HashSet, nous devons créer un objet de la classe HashSet. La classe HashSet se compose de différents constructeurs qui permettent la création éventuelle du HashSet. Voici les constructeurs disponibles dans cette classe.

1. HashSet()

Ce constructeur est utilisé pour créer un objet HashSet vide dans lequel la capacité initiale par défaut est de 16 et le facteur de charge par défaut est de 0,75. Si nous souhaitons créer un HashSet vide avec le nom hs, alors il peut être créé comme :

HashSet hs = new HashSet();>

2. HashSet (int initialCapacity)

Ce constructeur est utilisé pour construire un objet HashSet vide dans lequel initialCapacity est spécifié au moment de la création de l'objet. Ici, le loadFactor par défaut reste 0,75.

HashSet hs = new HashSet(int initialCapacity);>

3. HashSet (int initialCapacity, float loadFactor)

Ce constructeur est utilisé pour créer un objet HashSet vide dans lequel initialCapacity et loadFactor sont spécifiés au moment de la création de l'objet.

HashSet hs = new HashSet(int initialCapacity, float loadFactor);>

4. HashSet (Collection)

Ce constructeur est utilisé pour construire un objet HashSet contenant tous les éléments de la collection donnée. En bref, ce constructeur est utilisé lorsqu'une conversion est nécessaire d'un objet Collection vers l'objet HashSet. Si nous souhaitons créer un HashSet avec le nom hs, il peut être créé comme :

HashSet hs = new HashSet(Collection C);>

Vous trouverez ci-dessous la mise en œuvre des sujets ci-dessus :

Java

>

>

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

Méthodes dans HashSet

Effectuer diverses opérations sur HashSet

Voyons comment effectuer quelques opérations fréquemment utilisées sur le HashSet.

1. Ajout d'éléments dans HashSet

Pour ajouter un élément au HashSet, nous pouvons utiliser la méthode add() . Cependant, l'ordre d'insertion n'est pas conservé dans le HashSet. Nous devons noter que les éléments en double ne sont pas autorisés et que tous les éléments en double sont ignorés.

Exemple

Java

>

>

HashSet elements : [Geek, For, Geeks]>

2. Suppression d'éléments dans HashSet

Les valeurs peuvent être supprimées du HashSet à l'aide de la méthode remove().

Exemple

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. Itérer dans le HashSet

Parcourez les éléments de HashSet à l’aide de la méthode iterator(). Aussi, la plus connue consiste à utiliser le amélioré pour la boucle.

Exemple

Bloc de code

A, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>

Complexité temporelle des opérations HashSet : La structure de données sous-jacente de HashSet est une table de hachage. Donc, amortissez (moyenne ou cas habituel) la complexité temporelle nécessaire à l'ajout, à la suppression et à la recherche (méthode contient) de HashSet. O(1) temps.

Performances de HashSet

HashSet étend la classe Abstract Set et implémente Ensemble , Clonable , et Sérialisable interfaces où E est le type d’éléments maintenus par cet ensemble. La sous-classe directement connue de HashSet est LinkedHashSet .

Désormais, pour maintenir des performances en temps constant, l'itération sur HashSet nécessite un temps proportionnel à la somme de la taille de l'instance HashSet (le nombre d'éléments) plus la capacité de l'instance HashMap de sauvegarde (le nombre de compartiments). Il est donc très important de ne pas définir une capacité initiale trop élevée (ou un facteur de charge trop faible) si les performances itératives sont importantes.

• Capacité initiale : La capacité initiale signifie le nombre de compartiments lorsque la table de hachage (HashSet utilise en interne la structure de données de la table de hachage) est créée. Le nombre de compartiments sera automatiquement augmenté si la taille actuelle est pleine.
  
• Facteur de charge: Le facteur de charge est une mesure du niveau de remplissage autorisé du HashSet avant que sa capacité ne soit automatiquement augmentée. Lorsque le nombre d'entrées dans la table de hachage dépasse le produit du facteur de charge et de la capacité actuelle, la table de hachage est rehachée (c'est-à-dire que les structures de données internes sont reconstruites) de sorte que la table de hachage contienne environ deux fois le nombre de compartiments.
  

 Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>

Exemple: Si la capacité interne est de 16 et le facteur de charge est de 0,75, le nombre de compartiments sera automatiquement augmenté lorsque la table contient 12 éléments.

Effet sur les performances :

Le facteur de charge et la capacité initiale sont deux facteurs principaux qui affectent les performances des opérations HashSet. Un facteur de charge de 0,75 offre des performances très efficaces en termes de complexité temporelle et spatiale. Si nous augmentons la valeur du facteur de charge plus que cela, la surcharge de mémoire sera réduite (car cela diminuera l'opération de reconstruction interne), mais cela affectera l'opération d'ajout et de recherche dans la table de hachage. Pour réduire l'opération de remaniement, nous devons choisir judicieusement la capacité initiale. Si la capacité initiale est supérieure au nombre maximum d'entrées divisé par le facteur de charge, aucune opération de répétition n'aura lieu.

Note: L'implémentation dans un HashSet n'est pas synchronisée, dans le sens où si plusieurs threads accèdent simultanément à un ensemble de hachage et qu'au moins un des threads modifie l'ensemble, il doit être synchronisé en externe. Ceci est généralement accompli en synchronisant sur un objet qui encapsule naturellement l'ensemble. Si aucun objet de ce type n’existe, l’ensemble doit être encapsulé à l’aide de la méthode Collections.synchronizedSet. Il est préférable de le faire au moment de la création, pour éviter tout accès accidentel non synchronisé à l'ensemble, comme indiqué ci-dessous :

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

Méthodes utilisées avec HashSet

1. Méthodes héritées de la classe java.util.AbstractSet

2. Méthodes héritées de la classe java.util.AbstractCollection

3. Méthodes déclarées dans l'interface java.util.Collection

4. Méthodes déclarées dans l'interface java.lang.Iterable

5. Méthodes déclarées dans l'interface java.util.Set

FAQ sur HashSet en Java

T1. Qu’est-ce que HashSet en Java ?

Répondre:

HashSet est un type de classe qui étend AbstractSet et implémente les interfaces Set.

Q2. Pourquoi HashSet est-il utilisé ?

Répondre:

HashSet est utilisé pour éviter les données en double et pour trouver de la valeur avec la méthode rapide.

Q3. Différences entre HashSet et HashMap.

Répondre:

Q4. Différences entre HashSet et TreeSet en Java.

Répondre: