En java nous avons les ensembles représentés par des Set
Dans l’implémentation, on en tire des informations sur sa taille, de quoi ajouter et enlever des informations. Il faut également pouvoir itérer sur les ensembles.
public interface SSet<E> extends Iterable<E> {
int size();
boolean isEmpty();
void add(E e);
void remove(E e);
boolean contains(E e);
Iterator<E> iterator();
}Il est possible de facilement décrire des comportements par défaut; comment pour imprimer les ensembles, et quand est-il vide.
public abstract class SAbstractSet<E> implements SSet<E> {
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public String toString() {
StringJoiner j = new StringJoiner(", ", "{", "}");
for (E e: this)
j.add(e.toString());
return j.toString();
}
}En utilisant une liste
Utilisons une liste pour définir un ensemble. Une idée est d’utiliser une liste chaînée pour l’implémenter. Il ne faut pas oublier d’enlever les doublons.
public final class SListSet<E> extends SAbstractSet<E> {
private final SList<E> list = new SLinkedList<>();
@Override
public int size() {
return list.size();
}
@Override
public void add(E e) { // O(n)
if (! list.contains(e)) // On évite qu'un élément s'y trouve
list.add(0, e);
}
@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; // la liste ne contient pas de doublons
}
}
}
@Override
public boolean contains(E e) {
return list.contains(e); // la liste définit déjà cela
}
@Override
public Iterator<E> iterator() {
return list.iterator(); // la liste définit déjà cela
}
}Ensemble par table de hachage
Cette implémentation ci-dessus n’est pas forcément très optimale (du à la nature de l’implémentation des listes chaînées)
On voudrait pouvoir trouver nos valeurs rapidement, et pour cela nous utilisons la notion de hachage vu plus tôt. L’idée est de stocker des valeurs dans beaucoup de listes de taille plus ou moins
Pour trouver l’index d’un élément dans la liste, il suffit de hacher la valeur que nous voulons stocker, et de faire le reste de la division par la capacité, pour trouver son index.
public final class SHashSet<E> extends SAbstractSet<E> {
private int size = 0;
private SList<E>[] table = newTable(10);
@Override
public int size() {
return size;
}
// Pour ajouter, on récupère la liste, et on y ajoute l'élément
@Override
public void add(E e) {
SList<E> list = listFor(table, e);
if (! list.contains(e)) {
list.add(0, e);
size++;
}
}
@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--;
return; // Il n'y a pas plus qu'une fois cet élément (set)
}
}
}
@Override
public boolean contains(E e) {
return listFor(table, e).contains(e);
}
// L'itération est naturellement plus complexe, car on doit itérer sur des listes imbriquées
@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--;
while (!listIt.hasNext()) {
listIndex++;
listIt = table[listIndex].iterator();
}
return listIt.next();
}
@Override
public void remove() {
listIt.remove();
size--;
}
};
}
/// Récupère la liste associée à un élément (hash)
private static <E> SList<E> listFor(SList<E>[] table, E e) {
return table[Math.floorMod(e.hashCode(), table.length)];
}
/// Crée un tableau de listes, avec une capacité
private static <E> SList<E>[] newTable(int capacity) {
@SuppressWarnings("unchecked")
SList<E>[] table = new SList[capacity];
for (int i = 0; i < capacity; i++)
table[i] = new SLinkedList<>();
return table;
}
}Bien sûr, dans une implémentation plus complète, la capacité n’est pas fixée à listes. Il faut pouvoir étendre la collection, et ainsi il faut re-hacher les index des listes. Idéalement, les sous listes qui stockent les éléments, ne devraient pas contenir une grande quantité d’éléments, afin de garder les fonctions à des complexités raisonnables.
On a donc la notion de charge (load), qui est le rapport entre la taille et la capacité :
On définit ainsi des constantes qui gardent ce rapport entre des valeurs idéales, disons
On essaie ainsi de augmenter la capacité de l’ensemble quand sort de ces valeurs, soit quand on enlève des éléments, soit quand on en rajoute.