HashSet en Java

La classe HashSetimplémente l'interface Set, est basée sur une table de hachage et est également soutenue par une instance HashMap. Puisque HashSetles éléments ne sont pas ordonnés, il n’y a aucune garantie qu’ils seront dans le même ordre après un certain temps. Les opérations d'ajout, de suppression et de recherche seront effectuées en temps constant, à condition que la fonction de hachage répartisse correctement les éléments dans des « buckets », dont nous parlerons plus tard. Quelques points importants concernant HashSet:

• Parce que la classe implémente l'interface Set, elle ne peut stocker que des valeurs uniques ;
• Peut stocker des valeurs NULL ;
• L'ordre dans lequel les éléments sont ajoutés est calculé à l'aide d'un code de hachage ;
• HashSetimplémente également le Serializableet Cloneable.

Pour maintenir un temps d'exécution des opérations constant, le temps passé sur les actions avec HashSet, doit être directement proportionnel au nombre d'éléments dans HashSet+ la « capacité » de l'instance intégrée HashMap(le nombre de « paniers »). Par conséquent, pour maintenir les performances, il est important de ne pas définir une capacité initiale trop élevée (ni un facteur de charge trop faible). Capacité initiale – le nombre initial de cellules (« bacs ») dans la table de hachage. Si toutes les cellules sont remplies, leur nombre augmentera automatiquement. Le facteur de charge est une mesure du niveau de remplissage HashSetavant que sa capacité n'augmente automatiquement. Lorsque le nombre d'éléments dans HashSetdevient supérieur au produit de la capacité initiale et du facteur de charge, la table de hachage est re-hachée (les codes de hachage des éléments sont recalculés et la table est reconstruite en fonction des valeurs obtenues) et le nombre Le nombre de cellules qu'il contient est doublé. Facteur de charge = Nombre d'éléments stockés dans la table / taille de la table de hachage. Par exemple, si le nombre initial de cellules dans la table est de 16 et que le facteur de charge est de 0,75, il s'ensuit que lorsque le nombre de cellules remplies atteint 12, le le nombre de cellules augmentera automatiquement. Le facteur de charge et la capacité initiale sont les deux principaux facteurs qui affectent les performances de HashSet. Un facteur de charge de 0,75 offre en moyenne de bonnes performances. Si ce paramètre est augmenté, la charge mémoire sera réduite (car elle réduira le nombre de rehachages et de reconstructions), mais cela affectera les opérations d'ajout et de recherche. Pour minimiser le temps consacré au re-hachage, vous devez choisir le bon paramètre de capacité initiale. Si la capacité initiale est supérieure au nombre maximum d'éléments divisé par le facteur de charge, aucune opération de re-hachage n'aura lieu. Important: HashSetn'est pas une structure de données avec synchronisation intégrée, donc si plusieurs threads travaillent dessus en même temps et qu'au moins l'un d'entre eux essaie d'apporter des modifications, il est nécessaire de fournir un accès synchronisé de l'extérieur. Cela se fait souvent au détriment d'un autre objet synchronisé encapsulant le HashSet. S'il n'existe pas un tel objet, alors le Collections.synchronizedSet(). C'est actuellement le meilleur moyen d'éviter les opérations désynchronisées avec HashSet.

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

Constructeurs HashSet :

1. HashSet h = new HashSet(); - constructeur par défaut. La capacité initiale par défaut est de 16, le facteur de charge est de 0,75.
2. HashSet h = new HashSet(int initialCapacity)– un constructeur avec une capacité initiale donnée. Facteur de charge – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— un constructeur avec une capacité initiale et un facteur de charge donnés.
4. HashSet h = new HashSet(Collection C)– un constructeur qui ajoute des éléments d'une autre collection.

Le code ci-dessous montre quelques méthodesHashSet :

import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Conclusion:

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

Toutes les classes qui implémentent une interface Setsont prises en charge en interne par les implémentations Map. HashSetstocke les éléments en utilisant HashMap. Bien qu'un HashMapélément doive être représenté sous la forme d'une paire clé-valeur pour y ajouter un élément, HashSetseule la valeur est ajoutée. En fait, la valeur à laquelle nous transmettons HashSetest la clé de l'objet HashMapet une constante est utilisée comme valeur HashMap. De cette façon, dans chaque paire clé-valeur, toutes les clés auront la même valeur. Implémentation HashSeten java doc:

private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();

Si vous regardez la méthode add()y HashSet:

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

Vous pouvez remarquer que la méthode add()y HashSetappelle la méthode put()sur l'objet interne HashMap, en lui passant l'élément à ajouter comme clé, et la constante PRESENT comme valeur. La méthode fonctionne de la même manière remove(). Il appelle la méthode remove()objet interneHashMap :

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

HashSetest basé sur une table de hachage et les opérations d'ajout, de suppression ou de recherche se termineront, en moyenne, en un temps constant (O(1)) . Méthodes HashSet:

1. boolean add(E e): ajoute un élément à HashSet, s'il n'y en a pas, mais si un tel élément est déjà présent, la méthode renvoie false .
2. void clear():supprime tous les éléments d'un ensemble.
3. boolean contains(Object o): Renvoie vrai si l'élément donné est présent dans l'ensemble.
4. boolean remove(Object o): Supprime l'élément donné de l'ensemble, s'il est présent.
5. Iterator iterator(): Renvoie un itérateur pour les éléments de l'ensemble.
6. boolean isEmpty(): Renvoie vrai s'il n'y a aucun élément dans l'ensemble.
7. Object clone(): Effectue un clonage de surface HashSet.

Javadoc : https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html