Mise en œuvre des collections : ensembles

Etant donné la nécessité d'éviter les doublons, l'ajout dans la liste sous-jacente ne doit se faire que si l'élément reçu ne s'y trouve pas déjà. En conséquence, l'ajout dans un ensemble représenté par une liste a une complexité de O(n), alors que l'ajout dans une liste peut, sous certaines conditions, avoir une complexité de O(1) seulement !

@Override
public void add(E e) {
  if (! list.contains(e))
    list.add(0, e);
}

Si l'élément n'appartient pas encore à l'ensemble, la position à laquelle l'ajouter dans la liste est arbitraire. La mise en œuvre ci-dessus l'ajoute en tête de liste, car cela peut se faire très rapidement dans une liste chaînée.

La suppression d'un élément de l'ensemble implique de rechercher celui-ci, puis de le supprimer si on le trouve. Cela se fait facilement au moyen d'un itérateur. Sachant que la liste ne contient pas de doublons, la recherche peut s'arrêter dès que la première occurrence de l'élément à supprimer l'a été.

@Override
public void remove(E e) {
  Iterator<E> listIt = list.iterator();
  while (listIt.hasNext()) {
    E e1 = listIt.next();
    if (e1.equals(e)) {
      listIt.remove();
      return;
    }
  }
}

Etant donné l'existence de la méthode contains dans l'interface SList, le test d'appartenance est trivial à mettre en œuvre :

@Override
public boolean contains(E e) {
  return list.contains(e);
}

L'itération sur les éléments de l'ensemble peut se faire simplement par itération sur les éléments de la liste. Dès lors, il est valide de simplement retourner un itérateur sur cette dernière dans la méthode iterator.

@Override
public Iterator<E> iterator() {
  return list.iterator();
}

Comme expliqué plus haut, l'index, dans la table de hachage, de la liste correspondant à un élément s'obtient en ramenant sa valeur de hachage à un index valide. Pour ce faire, on peut simplement utiliser le reste de la division entière de la valeur de hachage par la capacité de la table¹.

En Java, il faut néanmoins prendre gardre à utiliser la bonne version de la division entière. Pour mémoire, l'opérateur « reste de la division », noté %, retourne une valeur ayant le signe du dividende. Sachant que la méthode hashCode peut retourner un entier int quelconque, y compris négatif, l'opérateur % n'est pas idéal ici. Il faut donc lui préférer la méthode floorMod de la classe Math, qui utilise une autre définition de la division entière et retourne une valeur ayant le signe du diviseur.

Etant donné qu'il est souvent nécessaire d'obtenir la liste de la table de hachage correspondant à un élément donné, il est utile de définir une méthode faisant cela :

private static <E> SList<E> listFor(SList<E>[] table,
				    E elem) {
  return table[Math.floorMod(elem.hashCode(),
			     table.length)];
}

Il aurait pu sembler plus logique de définir une méthode non statique utilisant directement l'attribut table de la classe comme table de hachage. La version plus générale définie ci-dessus est toutefois utile lors du rehachage, comme nous le verrons plus bas.

L'ajout d'un élément à l'ensemble se fait en deux phases :

1. la liste correspondant à l'élément est obtenue,
2. l'élément est ajouté à cette liste, pour peu qu'il n'y soit pas déjà.

La seconde phase est exactement identique à l'ajout dans un ensemble représenté par une unique liste !

@Override
public void add(E e) {
  SList<E> list = listFor(table, e);
  if (! list.contains(e)) {
    list.add(0, e);
    size += 1;
  }
}

Notez au passage que la manière dont l'ajout est fait permet de comprendre pourquoi les méthodes hashCode et equals doivent être compatibles : la première phase ci-dessus utilise hashCode pour déterminer la liste correspondant à l'élément, tandis que la seconde phase utilise equals pour déterminer si l'élément si trouve déjà.

La suppression d'un élément de l'ensemble se fait également en deux phases, qui sont similaires à celles de l'ajout :

1. la liste correspondant à l'élément est obtenue,
2. l'élément est supprimé de cette liste, s'il s'y trouve.

Une fois de plus, la seconde phase est en tous points identique à la suppression d'un ensemble représenté par une unique liste !

@Override
public void remove(E e) {
  Iterator<E> listIt = listFor(table, e).iterator();
  while (listIt.hasNext()) {
    E e1 = listIt.next();
    if (e1.equals(e)) {
      listIt.remove();
      size -= 1;
      return;
    }
  }
}

Le test d'appartenance se fait, sans surprise, lui aussi en deux phase, similaires à celles de l'ajout et de la suppression :

1. la liste correspondant à l'élément est obtenue,
2. le test d'appartenance est fait dans cette liste.

@Override
public boolean contains(E e) {
  return listFor(table, e).contains(e);
}

Le parcours des éléments stockés dans la table de hachage n'est pas totalement trivial, étant donné la nature bidimensionnelle de cette table. L'itérateur doit parcourir chacune de ses deux dimensions, et possède deux attributs dans ce but :

1. listIndex est l'index de la liste en cours de parcours,
2. listIt est un itérateur parcourant la liste d'index listIndex.

Pour déterminer s'il reste encore des éléments à parcourir, le plus simple est d'ajouter un troisième attribut à l'itérateur, nommé remaining ci-dessous, qui compte le nombre d'éléments restants à parcourir.

@Override
public Iterator<E> iterator() {
  return new Iterator<E>() {
    int remaining = size;
    int listIndex = 0;
    Iterator<E> listIt = table[listIndex].iterator();

    @Override
    public boolean hasNext() {
      return remaining > 0;
    }

    @Override
    public E next() {
      if (! hasNext())
	throw new NoSuchElementException();
      remaining -= 1;
      while (! listIt.hasNext()) {
	listIndex += 1;
	listIt = table[listIndex].iterator();
      }
      return listIt.next();
    }

    @Override
    public void remove() {
      listIt.remove();
      size -= 1;
    }
  };
}

Etant donné la manière dont les éléments de l'ensemble sont placés dans les différentes listes de la table de hachage, il devrait être clair que l'ordre dans lequel l'itérateur ci-dessus parcourt ces éléments est quelconque. En particulier, il peut dépendre de l'ordre dans lequel les éléments ont été ajoutés à l'ensemble, et de la capacité de la table de hachage !

Jusqu'à présent, nous avons fait l'hypothèse que la table de hachage avait une capacité constante, arbitrairement fixée à 10. Bien entendu, cela ne permet pas d'obtenir les performances souhaitées : les opérations principales (ajout, suppression, test d'appartenance) n'ont une complexité de O(1) que si la longueur des listes de la table ne dépend pas du nombre d'éléments qu'elle contient.

Dès lors, il faut faire en sorte de redimensionner la table afin que sa capacité soit toujours proche de sa taille — le nombre d'éléments qu'elle contient. Cette condition peut s'exprimer succinctement au moyen du concept de facteur de charge (load factor) introduit plus haut. Pour mémoire, le facteur de charge \(l\) est le rapport entre la taille \(s\) de la table et sa capacité \(c\) : \[ l = \frac{s}{c} \]

Si la fonction de hachage répartit parfaitement les éléments sur les entiers \(\{0, 1, \ldots, c\}\), un facteur de charge de 1 garantit que toutes les listes de la table contiennent exactement un élément. En pratique, il est très peu probable que cette condition soit satisfaite, et il est dès lors préférable que la capacité de la table soit légèrement supérieure au nombre d'éléments qu'elle stocke. En d'autres termes, il est souhaitable que le facteur de charge soit légèrement inférieur à 1.

Afin d'éviter de redimensionner la table à chaque changement du nombre d'éléments qu'elle stocke, ce qui serait très inefficace, il faut toutefois tolérer que le facteur de charge varie dans un intervalle jugé acceptable. Etant donné ce qui précède, nous fixerons cet intervalle à [0.4, 1]. Lorsque le facteur de charge sort de cet intervalle, la table est redimensionnée, et sa nouvelle capacité est déterminée pour que son nouveau facteur de charge ait une valeur considérée idéale, fixée ici à 0.7. Les constantes ci-dessous contiennent ces différentes valeurs, ainsi que la capacité minimale (et initiale) de la table :

private static int MIN_CAPACITY = 10;
private static double MIN_LOAD_FACTOR = 0.4;
private static double MAX_LOAD_FACTOR = 1;
private static double IDEAL_LOAD_FACTOR = 0.7;

Ces constantes définies, il est ensuite possible d'ajouter à la classe SHashSet une méthode nommée rehashIfNeeded qui redimensionne la table — opération nommée rehachage — si le facteur de charge n'est pas dans l'intervalle jugé acceptable. Ce rehachage consiste simplement à créer une nouvelle table, y copier la totalité des éléments de la table actuelle, et finalement remplacer l'ancienne table par la nouvelle.

private void rehashIfNeeded() {
  double loadFactor = size / (double)table.length;
  if (MIN_LOAD_FACTOR <= loadFactor
      && loadFactor <= MAX_LOAD_FACTOR)
    return;

  int idealCapacity = (int) (size / IDEAL_LOAD_FACTOR);
  int newCapacity = Math.max(MIN_CAPACITY, idealCapacity);
  if (newCapacity == table.length)
    return;

  SList<E>[] newTable = newTable(newCapacity);
  for (E e: this)
    listFor(newTable, e).add(0, e);

  table = newTable;
}

Une fois cette méthode écrite, il ne reste plus qu'à l'appeler chaque fois qu'un rehachage peut être nécessaire, c-à-d chaque fois que la taille de l'ensemble change. En cherchant dans les méthodes écrites précédemment toutes les mises à jour de l'attribut size, on constate qu'il y en a trois : une dans la méthode add, une dans la méthode remove et une dans la méthode remove de l'itérateur.

Ajouter un appel à rehashIfNeeded juste après la mise à jour de la taille dans les deux premiers cas ne pose aucun problème :

public void add(E e) {
  SList<E> list = listFor(table, e);
  if (! list.contains(e)) {
    list.add(0, e);
    size += 1;
    rehashIfNeeded();
  }
}

public void remove(E e) {
  Iterator<E> listIt = listFor(table, e).iterator();
  while (listIt.hasNext()) {
    E e1 = listIt.next();
    if (e1.equals(e)) {
      listIt.remove();
      size -= 1;
      rehashIfNeeded();
      return;
    }
  }
}

Par contre, effectuer un rehachage de la table alors qu'elle est en train d'être parcourue par un itérateur n'est bien entendu pas correct, car la position des éléments est affectée par le rehachage. Dès lors, aucun appel à rehashIfNeeded n'est fait dans la méthode remove de l'itérateur.