Dans cet article, nous verrons comment fonctionne HashSet en interne en Java, ce qui est également une question d’interview des collections favouriteJava, mais avant d’entrer dans l’implémentation interne de HashSet en Java, il est important de connaître deux points sur HashSet.
- HashSet en Java ne stocke que des valeurs uniques, c’est-à-dire qu’aucun doublon n’est autorisé.
- HashSet fonctionne sur le concept de hachage tout comme HashMap en Java, mais son fonctionnement diffère du HashMap de la manière suivante –
- Dans HashMap, une paire (Clé, Valeur) est ajoutée et la fonction de hachage est calculée à l’aide de key.
- Où, comme dans la fonction de hachage HashSet, est calculée en utilisant la valeur elle-même. Notez que dans HashSet, nous avons la méthode add(E e) qui ne prend que l’élément à ajouter en paramètre.
Vous l’avez peut-être déjà deviné, car la fonction de hachage est calculée en utilisant la valeur, c’est pourquoi seules les valeurs uniquevalues sont stockées dans le HashSet. Si vous essayez de stocker à nouveau le même élément, la fonction de hachage calculée serait la même, donc l’élément sera écrasé.
HashSet utilise en interne HashMap
Maintenant, revenons à l’implémentation interne de HashSet en Java le point le plus important est l’implémentation de la classe HashSet utilise en interne HashMap pour stocker ses éléments.
Dans le HashSet, il existe de nombreux constructeurs, un sans paramètre et plusieurs autres avec une capacité initiale ou un facteur de charge, mais chacun de ces constructeurs crée un HashMap.Étant donné que HashSet utilise HashMap en interne, savoir comment HashMap fonctionne en interne en Java vous aidera à comprendre comment HashSet fonctionne en interne en Java.
Extraits de constructeur HashSet
Dans la classe HashSet en Java, vous pouvez voir que les constructeurs de la classe créent un HashMap.
/*** Constructs a new, empty set; the backing <tt>HashMap</tt> instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() { map = new HashMap<>();}
public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor);}
Et la carte, qui est utilisée pour stocker des valeurs, est définie comme
private transient HashMap<E,Object> map;
Dans le constructeur, si vous l’avez remarqué, il existe des paramètres nommés capacité initiale et facteur de charge.Pour HashSet, la capacité initiale par défaut est de 16, c’est-à-dire qu’un tableau (ou un compartiment) de longueur 16 serait créé et le facteur de charge par défaut est de 0,75. Où le facteur de charge est une mesure du degré de remplissage de la table de hachage avant que sa capacité ne soit automatiquement augmentée.
Comment les éléments sont ajoutés – Implémentation interne de HashSet
J’ai indiqué au point 2 ci-dessus que HashSet calcule la fonction de hachage en utilisant la valeur elle-même et qu’il n’y a pas de paire (Clé, Valeur) dans HashSet, puis est venue l’instruction que HashSet utilise en interne HashMap pour stocker des objets.Ces deux instructions peuvent sembler contradictoires car les magasins HashMap (clé, valeur) s’apparient, voyons donc comment ces deux instructions contradictoires sont vraies.
En fait, à partir de la méthode add de la classe HashSet, la méthode put() de HashMap est appelée où la valeur, qui doit être ajoutée dans l’ensemble, devient Clé et un objet constant « PRÉSENT » est utilisé comme valeur.
C’est ainsi que PRESENT est défini dans l’implémentation de HashSet-
// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();
Et c’est ainsi que la méthode add est implémentée dans la classe HashSet –
public boolean add(E e) { return map.put(e, PRESENT)==null;}
Ainsi, vous pouvez voir avec dans l’implémentation interne du HashSet que c’est une paire (clé, valeur) qui obtient réellement added.It c’est juste que la valeur réelle (qui est ajoutée au HashSet) devient la clé et qu’une valeur factice « PRÉSENTE » est ajoutée comme valeur lors de sa sauvegarde dans le HashMap de sauvegarde.
Par exemple une instruction pour ajouter un élément à HashSet-set.add(« Mumbai »); traduit en interne en map.put (« Mumbai », PRÉSENT); et ensuite ajouté à l’instance HashMap de sauvegarde.
Une chose à noter ici est que dans HashMap, la valeur peut être dupliquée mais la clé doit être unique. C’est ainsi que Hashset s’assure que seules des valeurs uniques y sont stockées, car la valeur qui doit être stockée dans le HashSetdevient la clé tout en la stockant dans HashMap.
Comment l’élément est supprimé – Implémentation interne du HashSet
Lorsque nous devons supprimer un élément du HashSet, supprimez à nouveau en interne la méthode de HashSetcalls remove (clé d’objet) méthode du HashMap.
C’est ainsi qu’il est implémenté dans la classe HashSet.
public boolean remove(Object o) { return map.remove(o)==PRESENT;}
Notez ici que la méthode remove (clé d’objet) du HashMap renvoie la valeur associée à la clé.Alors que la méthode remove (Object o) du HashSet renvoie une valeur booléenne. Nous savons également que pour chaque valueadded dans HashSet, en interne lorsqu’elle est ajoutée à la HashMap associée, value devient Key et la valeur est toujours unobject appelé PRESENT. Par conséquent, la valeur renvoyée par la méthode remove (clé d’objet) du HashMap est toujours présente donc la carte de condition.supprimer (o) == PRÉSENT.
Comment les éléments sont récupérés de HashSet en Java
Dans HashSet, il n’y a pas de méthode get comme indiqué dans Map ou List. Dans HashSet, l’itérateur est là pour parcourir les valeurs de l’ensemble. En interne, il appellera le jeu de clés du HashMap, car les valeurs sont stockées en tant que clés dans le HashMap, donc ce que nous obtiendrons, ce sont les valeurs stockées dans le HashSet.
C’est ainsi que l’itérateur est implémenté en interne dans le HashSet en Java.
/*** Returns an iterator over the elements in this set. The elements* are returned in no particular order.** @return an Iterator over the elements in this set* @see ConcurrentModificationException*/public Iterator<E> iterator() { return map.keySet().iterator();}
Pointe vers la note
- Contrairement à HashMap où la fonction de hachage est calculée à l’aide de la clé HashSet utilise la valeur elle-même pour calculer la fonction de hachage.
- Étant donné que la fonction de hachage est calculée à l’aide de la valeur, seules les valeurs uniques sont stockées dans le jeu de hachages.
- HashSet utilise en interne HashMap pour stocker ses éléments.
- Lorsque l’élément est ajouté à HashSet à l’aide de la méthode add(E e), HashSet appelle en interne la méthode put() de la HashMap où la valeur transmise dans la méthode add devient clé dans la méthode put(). Une valeur factice « PRESENT » est transmise comme valeur dansla méthode put().
Recommandations pour l’apprentissage (cours Udemy)
- Cours de Masterclass de programmation Java
- Java en profondeur: Devenez un Ingénieur Java Complet!
- Cours de Master Class Spring Framework
- Cours de formation Python complet
- Python pour la Science des données et l’apprentissage automatique
C’est tout pour ce sujet Comment Fonctionne HashSet en interne en Java. Si vous avez des doutes ou des suggestions à faire, veuillez laisser un commentaire. Merci!
Sujets connexes
- Comment ArrayList Fonctionne en interne en Java
- Comment HashMap Fonctionne en interne en Java
- Comment La classe LinkedList Fonctionne en interne en Java
- LinkedHashSet en Java Avec des Exemples
- TreeSet en Java Avec des exemples
Vous pourriez aussi aimer –