image/svg+xml $ $ ing$ ing$ ces$ ces$ Res Res ea ea Res->ea ou ou Res->ou r r ea->r ch ch ea->ch r->ces$ r->ch ch->$ ch->ing$ T T T->ea ou->r

Les collections en Java

  1. Au commencement étaient les tableaux...
  2. Collection
  3. Listes
    1. Comparaison de LinkedList et ArrayList
    2. ArrayDeque : une liste basée sur un tableau circulaire
      1. Pourquoi utiliser ArrayDeque ?
      2. Méthodes utiles d'ArrayDeque
    3. Utilisation d'une liste
    4. PriorityQueue
    5. Tableaux et listes
  4. Égalité d'objets
  5. Tri de liste (Comparable et Comparator)
    1. Comparaisons idiomatiques
      1. Comparaison de chaînes de caractères
      2. Comparaison d'entiers
      3. Comparaison de flottants
  6. Ensembles (Set)
  7. hashCode() et HashSet
  8. Exemple d'utilisation de TreeSet
  9. Map
    1. Première application directe de Map : un cache LRU
    2. Deuxième application directe de Map : un sac
  10. Itérateur
    1. Principe
    2. Un itérateur pour Bag

Au commencement étaient les tableaux...

Collection

Listes

Comparaison de LinkedList et ArrayList

Deux principales types de listes disponibles en Java :

  1. LinkedList<T>
    • Liste chaînée avec un double maillage (précédent, suivant)
    • Maintien d'une référence vers le premier et dernier maillon
    • Ajouter ou supprimer un élément en tête ou fin de liste est en temps constant
      • Structure utile pour l'implantation de file (FIFO) ou de pile (LIFO)
    • Accéder à un élément d'indice i nécessite de parcourir depuis le début ou la fin les maillons jusqu'à i
    • Gourmande en mémoire (une référence précédent, une référence suivant et une référence maillon pour chaque valeur)
    • Dispersion en mémoire
    • Liste chaînée = arbre unaire (arbre en forme de peigne)
  2. ArrayList<T>
    • Liste utilisant un tableau pour le stockage (références d'objets stockées)
    • Les éléments sont contigüs en mémoire : itération optimisée
    • Supprimer un élément en fin de liste est en temps constant
    • Ajouter un élément en fin de liste
      • Soit se fait simplement par affectation de la prochaine cellule libre
      • Soit nécessite une réallocation d'un tableau plus grand (gérée par ArrayList)
      • Dans tous les cas, le temps d'ajout est considéré (par amortissement) constant
    • Ajouter/supprimer un élément vers le début de la liste
      • Nécessite le décalage des éléments suivants
    • Accéder à un élément d'indice i est instantané (ième cellule du tableau)

LinkedList n'a pratiquement pas d'utilité !

ArrayDeque : une liste basée sur un tableau circulaire

Pourquoi utiliser ArrayDeque ?

Comment créer une liste :

En utilisant un tableau (comme pour une ArrayList) mais circulaire :

Comment ajouter (ou supprimer) rapidement (O(1)) un élément en début de liste :

Limitation non résolue par l'ArrayDeque :

⚠ Contrairement à LinkedList et ArrayList, ArrayDeque interdit l'ajout de références nulles dans la liste.

Méthodes utiles d'ArrayDeque

Utilisation d'une liste

  1. Il faut d'abord l'instantier (avec un constructeur sans argument) : List<Integer> l = new ArrayList<>()
  2. Nous pouvons la peupler :
    • Soit en ajoutant les éléments un par un avec la méthode void add(T element) : par exemple l.add(10)
    • Soit en ajoutant tous les éléments d'une autre collection : void addAll(Collection<? extends T> c)
  3. Nous pouvons accéder à l'élément d'indice i avec T get(int i) (l'accès est rapide si la liste implante l'interface RandomAccess ce qui est le cas de ArrayList mais pas de LinkedList)
  4. Nous pouvons récupérer l'indice d'un élément avec int indexOf(T element) (retourne -1 si l'élément n'est pas présent, à éviter cependant car en temps linéaire)
  5. Nous pouvons supprimer l'élément d'indice i avec T remove(int i) (retourne l'élément supprimé)
  6. Nous pouvons remplacer l'élément d'indice i par une nouvelle valeur avec T set(int i, T newValue) (retourne l'ancienne valeur)

PriorityQueue

Exemple : utilisons PriorityQueue pour récupérer les n plus petits éléments triés d'une collection

/**
 * Find the n smallest elements from a collection (in sorted order).
 *
 * @param c the collection on which we search the smallest elements
 * @param n the number of smallest elements we want
 * @return the n smallest elements from the collection in sorted order
 */
public static <T extends Comparable<? super T>> ArrayList<T> heapSort(Collection<T> c, int n) {
	// first we use a priority queue to keep the n smallest elements
	// reverseOrder is required because we want to be able to remove quickly the greatest (useless) element
	var q = new PriorityQueue<T>(Collections.reverseOrder()); // the greatest element is at the top
	int i = 0;
	for (T element: c) {
		assert(q.size() <= n); // there are always less than n elements in the queue
		q.add(element);
		if (i >= n)
			q.poll(); // remove the largest element (we can ignore the returned value)
		i++;
	}
	// q contains the smallest elements

	// we must sort the elements of q from the smallest to the largest
	var q2 = new PriorityQueue<T>();
	for (T element: q)
		q2.add(element);
	var result = new ArrayList<T>();
	while (q2.size() > 0) {
		result.add(q2.poll());
	}
	return result;
}

Cas extrêmes de l'exemple :

Tableaux et listes

  1. Conversion d'un tableau en liste (ArrayList) avec Arrays.asList(E... elements)
  2. Conversion d'une liste en tableau avec list.toArray()

Un petit exemple :

package fr.upem.jacosa.collections;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// @run; ArraysAndLists
public class ArraysAndLists 
{
	public static void main(String[] args)
	{
		List<String> list = Arrays.asList(args);
		// list.add("foobar"); // will throw an exception since the list is backed by the array (the size of the list is not modifiable)
		list.set(0, "foobar"); // will works if the args array has at least one element, the list is mutable
		
		List<Integer> list2 = new ArrayList<>();
		list2.add(0);
		list2.add(1);
		list2.add(2);
		list2.add(4);
		Object[] elements = list2.toArray(); // convert to an array of Objects
		Integer[] typedElements = list2.toArray(new Integer[elements.length]); // convert to a typed array (it is required to instantiate an array since the toArray method cannot instantiate a "generically" typed array
		System.out.println("elements=" + elements + "," + Arrays.toString(elements));
		System.out.println("typedElements=" + typedElements + "," + Arrays.toString(elements));
	}
}

Égalité d'objets

Implantation typique de la méthode int indexOf(T element) d'une liste :

public int indexOf(T element)
{
	for (int i = 0; i < size(); i++)
	{
		final T a = this.get(i);
		if ((element == null && a == null)
			|| (element != null && element.equals(a)))
				return i;
	}
	return -1;
}

Un (mauvais) exemple de méthode equals pour Point et son utilisation :

package fr.upem.jacosa.collections;

// @run: PointTester

class Point
{
	private final int x;
	private final int y;
	
	public Point(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
	
	public int getX() { return x; }
	public int getY() { return y; }
	
	@Override
	public boolean equals(Object o)
	{
		if (o == null) return false;
		if (this == o) return true;
		if (! (o instanceof Point)) return false;
		Point p = (Point)o;
		return x == p.x && y == p.y;
	}
}

class GrayColoredPoint extends Point
{
	private final int grayLevel;
	
	public GrayColoredPoint(int x, int y, int grayLevel) 
	{
		super(x, y);
		this.grayLevel = grayLevel;
	}
	
	@Override
	public boolean equals(Object o)
	{
		if (o == null) return false;
		if (this == o) return true;
		if (! (o instanceof GrayColoredPoint)) return false;
		GrayColoredPoint p = (GrayColoredPoint)o;
		return getX() == p.getX() && getY() == p.getY() && grayLevel == p.grayLevel;
	}
}

public class PointTester
{
	public static void main(String[] args)
	{
		Point p = new Point(0, 0);
		GrayColoredPoint gcp = new GrayColoredPoint(0, 0, 128);
		System.out.println(p.equals(gcp)); // true
		System.out.println(gcp.equals(p)); // false: symmetry not respected!
	}
}

Un exemple de méthode equals pour une arbre binaire :

package fr.upem.jacosa.collections;

import java.util.Objects;

// @run: BinaryTree

public class BinaryTree<T>
{
	private T value;
	private BinaryTree<T> child1, child2;
	
	public BinaryTree(T value, BinaryTree<T> child1, BinaryTree<T> child2)
	{
		this.value = value;
		this.child1 = child1;
		this.child2 = child2;
	}
	
	@Override
	public boolean equals(Object o)
	{
		if (o == null) return false;
		if (this == o) return true;
		if (! (o.getClass().equals(this.getClass()))) return false;
		@SuppressWarnings("unchecked")
		BinaryTree<T> o2 = (BinaryTree<T>)o;
		return Objects.equals(child1, o2.child1)
			&& Objects.equals(child2, o2.child2)
			&& Objects.equals(value, o2.value);
	}
	
	public static void main(String[] args) 
	{
		BinaryTree<Integer> bt1 = new BinaryTree<Integer>(0, new BinaryTree<Integer>(1, null, null), null);
		BinaryTree<Integer> bt2 = new BinaryTree<Integer>(0, new BinaryTree<Integer>(1, null, null), null);
		System.out.println(bt1.equals(bt2));
		bt1.child1 = bt1;
		bt2.child1 = bt2;
		System.out.println(bt1.equals(bt2)); // StackOverflowException !
	}
}

Tri de liste (Comparable et Comparator)

Comment rendre sa classe Comparable ? En implantant l'interface avec sa méthode int compareTo(T other)

Comparons des points (on ordonne les points par abscisse croissante puis par ordonnée croissante) :

public class Point implements Comparable<Point>
{
	int x;
	int y;
	
	public Point(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
	
	public Point getInvertedPoint()
	{
		return new Point(y, x); // inversion of the coordinates
	}
	
	@Override
	public String toString()
	{
		return String.format("%d,%d", x, y);
	}
	
	@Override
	public int compareTo(Point other)
	{
		if (other == null) return 1;
		if (this.x < other.x) return -1;
		if (this.x > other.x) return 1;
		// now the x values are equal
		if (this.y < other.y) return -1;
		if (this.y > other.y) return 1;
		return 0; // the points are equal
	}
	
	// Crééons une liste et trions la :
	// @run: Point
	public static void main(String[] args)
	{
		List<Point> l = new ArrayList<>();
		l.add(new Point(1,2));
		l.add(new Point(0,1));
		l.add(new Point(7,0));
		Collections.sort(l);
		System.out.println(l);
	}
}

Comment faire si nous souhaitons utiliser un autre critère de tri (par exemple trier selon y, puis selon x) ? En créant un Comparator :

Comparator<Point> yxComparator = new Comparator<>()
{
	@Override
	public int compare(Point p1, Point p2)
	{
		if (p1 == null && p2 == null) return 0;
		if (p1 == null) return -1;
		return p1.getInvertedPoint().compareTo(p2.getInvertedPoint());
		// it works but it is not efficient since two points are allocated for each comparison
		// it would be better to directly compare the y then x values
	}
};

On trie maintenant selon ce comparateur :

Collections.sort(l, yxComparator);

Depuis Java 8, on peut de manière équivalente réaliser :

l.sort(yxComparator)

Pour résumer :

Comparaisons idiomatiques

Comparaison de chaînes de caractères

String implante Comparable<String> : la méthode int compareTo(String s) de String permet le tri par ordre lexicographique (ordre du dictionnaire).

Cette méthode de comparaison sur String utilise l'ordre défini sur les char (caractères Unicode). Ainsi par exemple en consultant les plans Unicode, nous constatons que :

Faisons quelques tests :

package fr.upem.jacosa.collections;

import java.text.Collator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// @run: SortingString alphabet écriture Étuve éléphant ALPHABET essai
public class SortingString
{
	public static void main(String[] args)
	{
		List<String> l1 = Arrays.asList(args);
		l1.sort(null);
		System.out.println("Sorted using default compareTo of String: " + l1);
		// Create a copy of the list
		List<String> l2 = new ArrayList<>(l1);
		// Now we sort using the current locale (e.g. é should be closer to e than to a)
		l2.sort(Collator.getInstance());
		System.out.println("Sorted using current locale: " + l2);
	}
}

Comparaison d'entiers

Soient deux entiers a et b. Nous n'avons pas nécessairement a-b < 0 ssi b>a en arithmétique modulaire. Par exemple si a == Integer.MIN_VALUE (soit -2^31) et b == 1, nous avons a - b == 2^31-1 > 0 avec pourtant b > a.

Pour comparer correctement, on pourra utiliser la méthode statique int Integer.compare(int a, int b) (une version existe aussi pour Long).

package fr.upem.jacosa.collections;

// @run: SortingInt -2147483648 1
public class SortingInt
{
	public static int badIntComparisonMethod(int a, int b)
	{
		return a - b;
	}
	
	public static void main(String[] args)
	{
		int a = Integer.parseInt(args[0]);
		int b = Integer.parseInt(args[1]);
		System.out.println(String.format("a=%d, b=%d", a, b));
		System.out.println("Bad comparator result: " + badIntComparisonMethod(a, b));
		System.out.println("Good comparator result: " + Integer.compare(a, b));
	}
}

Comparaison de flottants

Comparer des flottants est délicat à cause de NaN (Double.NaN, Float.NaN). Théoriquement Double.NaN != Double.NaN.

La méthode Double.compare(double a, double b) (méthode existant aussi en version float) considère que Double.NEGATIVE_INFINITY < -0.0 < 0.0 < Double.POSITIVE_INFINITY < Double.NaN == Double.NaN.

Testons cela :

package fr.upem.jacosa.collections;

import java.util.ArrayList;
import java.util.List;

// @run: FloatTest
public class FloatTest
{
	public static void main(String[] args)
	{
		System.out.println("Double.NaN == Double.NaN ? " + (Double.NaN == Double.NaN));
		System.out.println("Test with compare: " + Double.compare(Double.NaN, Double.NaN));
		// Let's sort!
		List<Double> l = new ArrayList<>();
		l.add(0.0);
		l.add(-0.0);
		l.add(42.0);
		l.add(-42.0);
		l.add(Double.POSITIVE_INFINITY);
		l.add(Double.NEGATIVE_INFINITY);
		l.add(Double.NaN);
		l.sort(null);
		System.out.println("Sorted double list: " + l);
	}
}

Ensembles (Set)

hashCode() et HashSet

Implantons une méthode hashCode() pour la classe Point :

public class Point
{
	...
	
	@Override
	public int hashCode()
	{
		return x * 65537 + y; // TODO
	}
}

On pourrait ensuite redéfinir hashCode pour AbstractColoredPoint :

public abstract class AbstractColoredPoint extends Point
{
	...
	
	@Override
	public int hashCode()
	{
		return super.hashCode() ^ getColor().hashCode();
	}
}

Nous pouvons maintenant créer un ensemble utilisant une table de hachage et y ajouter des points :

Set<Point> pointSet = new HashSet<>();
pointSet.add(new Point(0, 0));
pointSet.add(new Point(1, 0));
pointSet.add(new Point(0, 0)); // should not add since a point with the same content already exists
System.out.println(pointSet.size()); // should display 2

Exemple d'utilisation de TreeSet<T>

Les programmes Unix sort et uniq permettent respectivement de trier des lignes communiquées sur l'entrée standard et supprimer les doublons. Ainsi la commande shell suivante lit toutes les lignes d'un fichier, les trie par ordre lexicographique et supprime les doublons :
cat monFichier.txt | sort | uniq
Réalisons la même tâche par un programme Java :
package fr.upem.jacosa.collections;

import java.io.IOException;
import java.util.Collections;
import java.util.Scanner;
import java.util.SortedSet;
import java.util.TreeSet;

/** Sort the lines from the standard input and remove the duplicates */
public class UniqSort
{
	public static void main(String[] args) throws IOException
	{
		Scanner scanner = new Scanner(System.in);
		TreeSet<String> set = new TreeSet<>(Collections.reverseOrder());
		while (scanner.hasNextLine())
			set.add(scanner.nextLine());
		// We display only the (sorted) lines starting with 'a'
		for (String line: set.subSet("b", "a")) 
			System.out.println(line);
		scanner.close();
	}
}

On note que TreeSet<T> nécessite que le type T des éléments implante l'interface Comparable afin de pouvoir comparer les éléments entre-eux (et avoir un ordre total).

Si l'on veut maintenant uniquement les lignes commençant par la lettre a on écrit la boucle for-each ainsi :
for (String line: set.subSet("a", "b")) System.out.println(line);
Si l'on souhaitait réaliser un tri par ordre lexicographique inverse, on pourrait appeler ainsi le constructeur de TreeSet<String>` :
Set<String> set = new TreeSet<>(Collections.reverseOrder());

Map

Première application directe de Map : un cache LRU

Un cache LRU (Least Recently Used) conserve en mémoire uniquement les dernières clés créées ou accédées.
Une telle structure est utile pour conserver des résultats coûteux (calculs, informations récupérées) qui pourront être réutilisés.

Méthode fournie :

Le cache ne doit conserver qu'un nombre limité d'entrées.
Si sa capacité est dépassée, on supprime les entrées les plus vieilles. Comment connaître les entrées les plus vieilles ? En sauvegardant l'ordre d'insertion utilisant une LinkedHashMap. 

package fr.upem.jacosa.collections;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;

// @run: LRUCacheTest

/** Interface for a cache map that keeps the Least Recently Used entries */
interface LRUCache<K, V>
{
	/** Get the value linked to key or insert it in the cache by computing it with the computer */
	public V get(K key, Function<K, V> computer);
	
	/** Number of values that has been computed */
	public int getMisses();
}

/** Default implementation of the LRU cache */
class LRUCacheImpl<K, V> implements LRUCache<K, V>
{
	private final int capacity;
	private LinkedHashMap<K,V> map = new LinkedHashMap<>();
	private int missCounter = 0;
	
	public LRUCacheImpl(int capacity)
	{
		this.capacity = capacity;
	}
	
	@Override
	public int getMisses()
	{
		return missCounter;
	}
	
	@Override
	public V get(K key, Function<K, V> computer)
	{
		V result = map.remove(key); // remove from the map
		if (result == null) 
		{
			result = computer.apply(key);
			missCounter++;
		}
		
		map.put(key, result); // put in the map (key will now be in last position in the LinkedHashMap)
		
		// check if we are in over-capacity
		// in this case we remove the first elements of the map
		int toRemove = map.size() - capacity;
		if (toRemove > 0)
			for (Iterator<Map.Entry<K, V>> it = map.entrySet().iterator(); it.hasNext() && toRemove > 0; )
			{
				it.next();
				it.remove();
				toRemove--;
			}
			
		return result;
	}
}

public class LRUCacheTest
{
	public static void main(String[] args)
	{
		LRUCacheImpl<Integer, Integer> cache = new LRUCacheImpl<>(5);
		for (int i = 0; i < 100; i++)
			System.out.println(cache.get(i, x -> x * x ));
		for (int i = 99; i >= 0; i--)
			System.out.println(cache.get(i, x -> x * x ));
		System.out.println("Number of misses: " + cache.getMisses());
	}
}

Deuxième application directe de Map : un sac

Un sac (Bag pour les anglophones) est une structure de données qui généralise le concept d'ensemble : il est possible d'avoir plusieurs exemplaires du même élément. Mais contrairement à une liste, il est possible de connaître rapidement le nombre d'exemplaires d'un élément.

// @run: Bag toto titi tutu toto toto toto titi gaga
public class Bag<T>
{
	private Map<T, Integer> content;
	
	public Bag()
	{
		this.content = new HashMap<T, Integer>();
	}
	
	/** Get the current number of samples of an element */
	public int get(T element)
	{
		Integer samples = content.get(element);
		return (samples == null)?0:samples;
	}
	
	/** Add a new sample of the element and return the current number of samples in the bag */
	public int add(T element)
	{
		int newSamples = get(element) + 1;
		content.put(element, newSamples);
		return newSamples;
	}
	
	/** Remove a sample of the element and return the remaining number of samples */
	public int remove(T element)
	{
		int newSamples = get(element) - 1;
		switch (newSamples)
		{
			case -1: break; // nothing to do, the element was not present
			case 0: content.remove(element); break; // no more samples
			default: content.put(element, newSamples);
		}
		return Math.max(0, newSamples);
	}
	
	/** We delegate the work to the underlying map */
	@Override
	public String toString()
	{
		return content.toString();
	}
	
	public static void main(String[] args)
	{
		// add in the bag all the arguments of the main
		Bag<String> b = new Bag<>();
		for (String arg: args)
			b.add(arg);
		System.out.println(b);
	}
}

Itérateur

Principe

Toutes les classes héritant de Collection<T> implantent la méthode Iterator<T> iterator() retournant un itérateur pour obtenir les valeurs.

Un itérateur peut par exemple s'utiliser ainsi :

Set<Integer> set = new TreeSet<>();
for (int i = 100; i >= 0; i--)
	set.add(i);
Iterator<Integer> it = set.iterator();
while (it.hasNext())
	System.out.println(it.next());

Deux méthodes principales sont donc utilisables pour Iterator<T> :

Il existe également une méthode void remove() permettant de supprimer l'élément que l'on vient d'obtenir avec next(). Cette méthode peut lever UnsupportedOperationException si on ne supporte pas la suppression.

Une autre façon (plus légère syntaxiquement) d'utiliser l'itérateur d'une classe Iterable<T> est d'employer une boucle for-each :

...
for (Integer i: set)
	System.out.println(i);

☠ Il est interdit de modifier une collection pendant l'utilisation de son itérateur. Cela peut conduire à un effet imprévisible (dépendant de l'implantation de l'itérateur). Certaines implantations d'itérateur testent les modifications concurrentes et lève une ConcurrentModificationException lorsqu'un tel évènement se produit. Nous pouvons l'expérimenter avec le code suivant :

for (Integer i: set)
	set.remove(i);

Un itérateur pour Bag

Implantons maintenant un itérateur pour la classe Bag que nous avons écrite :

public class BagIterator<T> implements Iterator<T>
{
	private final Iterator<Map.Entry<T, Integer>> entriesIterator;
	private T currentElement = null;
	private int remainingSamples = 0;
	
	public BagIterator(Bag<T> bag)
	{
		this.entriesIterator = bag.content.entrySet().iterator();
		if (entriesIterator.hasNext())
		{
			Map.Entry<T, Integer> entry = entriesIterator.next();
			currentElement = entry.getKey();
			remainingSamples = entry.getValue();
		}
	}
	
	@Override
	public boolean hasNext()
	{
		return remainingSamples > 0;
	}
	
	@Override
	public T next()
	{
		if (! hasNext()) throw new NoSuchElementException();
		T element = currentElement;
		remainingSamples--;
		if (remainingSamples == 0 && entriesIterator.hasNext())
		{
			Map.Entry<T, Integer> entry = entriesIterator.next();
			currentElement = entry.getKey();
			remainingSamples = entry.getValue();
		}
		return element;
	}
}

Et nous pouvons maintenant faire en sorte que Bag<T> implante Iterable<T> :

public class Bag<T> implements Iterable<T>
{
	...
	
	@Override
	public Iterator<T> iterator()
	{
		return new BagIterator(this);
	}
}