Théorie 5.1: Map naïf #

Un map permet d’associer une clé à une valeur
- chaque clé est unique
Par exemple, le map ci-bas associe la clé "xdf" à la valeur 12:
- {"sdx":5,"xdf":12,"lkm":54}
Un map est aussi appelé: dictionnaire, liste associative, objet JSON
On peut voir un map comme un tableau où les indices ne sont pas des entiers:

// Java valide
Character[] tableauChar = new String[3];

tableauChar[0] = 'a';        // l'indice est un entier
tableauChar[1] = 'b';
tableauChar[2] = 'c';

//  0   1   2
// ['a','b','c']         


// Ce qu'on aimerais avoir (pas du Java valide)
<String, Character>[] mapChar; 
mapChar = new <String, Character>[3]; 

mapChar["premier"]   = 'a';  // l'indice est une chaîne!
mapChar["deuxième"]  = 'b';
mapChar["troisième"] = 'c';

//   "premier" "deuxième" "troisième"
// [ 'a',      'b',       'c']

Interface d’un map #

public interface MapJava<C extends Cle<?>, V extends Object> {
	
	void       put(C c, V v);      // associe la valeur v à la clé c
	V          get(C c);           // obtenir la valeur associée à la clé c
	void       clear();            // vide le map
	int        size();             // taille du map
	boolean    isEmpty();          // si vide
	boolean    containsKey(C c);   // si le map contient la clé c
	boolean    containsValue(V v); // si le map contient la valeur v
	void       remove(C c);        // effacer la clé c (et la valeur associée)
	List<C>    keys();             // retourner une liste de clés

}

Implantation naïve d’un map #

On utilise deux listes:
- la liste des clés
- la liste des valeurs
Une paire clé/valeur est mémorisée au même indice
Par exemple:

// Le map
{"sdx":5,"xdf":12,"lkm":54}

// Les clés
//         0     1     2
cles =    ["sdx","xdf","lkm"]

// Les valeurs
//         0     1     2
valeurs = [5,    12,   54]

Si la clé "xdf" est à l’indice 1 dans cles
Alors la valeur associée à "xdf" est aussi à l’indice 1, mais dans valeurs
En général:

public class MapJavaNaif <C extends Cle<?>, V extends Object> extends MapJava<C,V> {
	
	private List<C> cles = new ArrayList<>();
	private List<V> valeurs = new ArrayList<>();

	@Override
	public void put(C c, V v) {
		int indiceCle = cles.indexOf(c);
		
		if(indiceCle != -1) {
			valeurs.set(indiceCle, v);
		}else {
			cles.add(c);
			valeurs.add(v);
		}
	}

	@Override
	public V get(C c) {
		V valeur = null;
		
		int indiceCle = cles.indexOf(c);
		
		if(indiceCle != -1) {
			valeur = valeurs.get(indiceCle);
		}

		return valeur;
	}

	@Override
	public void remove(C c) {
		int indiceCle = cles.indexOf(c);
		
		if(indiceCle != -1) {
			cles.remove(indiceCle);
			valeurs.remove(indiceCle);
		}
	}

	@Override
	public List<C> keys() {
		return cles;
	}
}

Chaque clé doit héritée de la classe Cle:

public class Cle<T extends Object> {

	private T valeur;
	
	public Cle(T valeur) {
		this.valeur = valeur;
	}
	
	public T valeur() {
		return valeur;
	}
}

on veut ainsi rendre explicite la notion de clé

Problème d’efficacité #

Modifier une valeur dans notre map naïf n’est pas efficace:

Le problème est que indexOf fait une boucle sur la liste des clés
Mais on aimerait que ça soit efficace:
- on veut utiliser le map comme un tableau