Blog

Java : Les ensembles : HashSet & TreeSet

HashSet

Cette classe implémente l’interface Set, en utilisant une table hachée. Un HashSet est implanté comme une HashMap, dont les clés sont les éléments du hashSet et les valeurs sont toutes une même valeur PRESENT.
Les opérations get et put sont en temps constant. 
La capacité est le nombre de listes. Le load factor (0.75 par défaut) est  la limite de remplissage de la table à partir de laquelle la table est automatiquement agrandie.

1 Constructeurs :

HashSet()Crée une HashSet de capacité initiale 16 et de loadFactor 0.75.
HashSet( int capaciteInitiale)Crée une HashSet de capacité initiale capaciteInitiale et de loadFactor 0.75.
HashSet( int capaciteInitiale, float loadFactor)Crée une HashSet de capacité initiale capaciteInitiale et et de loadFactor loadFactor.
HashSet(Collection<? extends E> c)Crée une HashSet contenant tous les élément de la Collection c.

2 Méthodes :

void clear()Supprime tous les élément du Set.
boolean add(E o)Ajoute o dans le Set et  retourne true si o a été effectivement ajouté et false sinon (o était déjà présent dans le Set)
boolean contains(Object o)Retourne true si l’objet o est dans le Set et false sinon.
boolean isEmpty()Retourne true si le Set est vide et false sinon.
boolean remove(Object o)Enlève du Set l’objet o et retourne true, retourne false si o n’est pas dans le Set.
int size()Retourne le nombre d’éléments du Set.
Iterator<E> iterator()Retourne un itérateur sur les éléments du Set.

TreeSet

Les données stockées dans un TreeSet sont représentées dans un TreeMap, ou suivant le constructeur plus généralement dans un SortedMap.
Un TreeMap est un arbre binaire équilibré par la technique rouge-noir.

public class TreeSet<E>  extends AbstractSet<E> 
                         implements SortedSet<E>, Cloneable, java.io.Serializable {
   private transient SortedMap<E,Object> m; /// L'arbre binaire des données
   private transient Set<E> keySet; // La vue clé de cet arbre binaire
   // valeur "bidon" associée à un objet stocké dans le TreeMap
    private static final Object PRESENT = new Object();
    ...
    

1 Les constructeurs :

private TreeSet(SortedMap<E,Object> m) {
   this.m = m;
   keySet = m.keySet();
}

public TreeSet() {
   this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> c) {
   this(new TreeMap<E,Object>(c));
}

public TreeSet(Collection<? extends E> c) {
   this();
   addAll(c);
}

public TreeSet(SortedSet<E> s) {
   this(s.comparator());
   addAll(s);
}

2 Les méthodes :

Les méthodes se résument toutes à un appel de la méthode correspondante de la classe TreeMap. Exemples :

  • la méthode add ajoute un couple (o,PRESENT), elle utilise la méthode put de TreeMap, qui retourne null si l’objet était absent du TreeMap avant ajout.public boolean add(E o) { return m.put(o, PRESENT)==null; }
  • la méthode remove enlève un couple (o, PRESENT), elle utilise la méthode remove de TreeMap, qui retourne la valeur associée à la clé o, si celle-ci était présente dans le TreeMap, et nullsinon.public boolean remove(Object o) { return m.remove(o)==PRESENT;< }
  • la méthode clear vide le TreeSet.public void clear() { m.clear(); }
  • les méthodes subSet, headSet et tailSet :public SortedSet<E> subSet(E fromElement, E toElement) { return new TreeSet<E>(m.subMap(fromElement, toElement)); }Retourne l’ensemble des éléments supérieurs ou égaux à fromElement et inférieurs strictement à toElement.public SortedSet<E> headSet( E toElement) { return new TreeSet<E>(m.subMap(fromElement, toElement)); }Retourne l’ensemble des éléments strictement inférieurs à toElement.public SortedSet<E> tailSet(E fromElement) { return new TreeSet<E>(m.tailMap(fromElement)); }Retourne l’ensemble des éléments supérieurs ou égaux à fromElement.
  • les méthodes first et last  :
  • la méthode contains :public boolean contains(Object o) { return m.containsKey(o); }

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *