Théorie 5.2: Map avec hachage #

Fonction et table de hachage #

• On veut éviter de chercher l’indice de la clé avec un indexOf

• On utiliser une fonction de hachage, c-à-d une méthode qui va

  • calculer un indice pour chaque clé
  • sans chercher d’information sur les autres clés

• Une clé hachable doit implanter la méthode indice qui retourne l’indice de la clé

public abstract class CleHachable <T extends Object> extends Cle<T> {
	
	public CleHachable(T valeurJava) {
		super(valeurJava);
	}

	public abstract int indice();
}

• Voici par exemple une clé hachable quand la clé est une chaîne:

public class ChaineHashb extends CleHachable<String> {

	public ChaineHashb(String valeurJava) {
		super(valeurJava);
	}

	@Override
	public int indice() {
		return valeurJava().length();
	}

}

• l’indice est simplement la longueur de la clé

• Une fois qu’on a un indice, on peut mémoriser la valeur dans un tableau

List<Character> valeurs = new ArrayList<>();

cle01 = new ChaineHashb("v");
cle02 = new ChaineHashb("yf");
cle03 = new ChaineHashb("asf");

map.put(cle01, 'a'):

    // la clé est "v",   l'indice est 1 (la longueur)
    int indice01 = cle01.indice();
    valeurs.set(indice01, 'a');

map.put(cle02, 'b'):

    // la clé est "yf",  l'indice est 2 (la longueur)
    int indice02 = cle02.indice();
    valeurs.set(indice02, 'b');

map.put(cle03, 'c'):

    // la clé est "asf", l'indice est 3 (la longueur)
    int indice03 = cle03.indice();
    valeurs.set(indice03, 'c');

• IMPORTANT: la fonction de hachage ne doit pas être aléatoire
  • sinon on ne peut plus retrouver une valeur mémorisée par indice!

Quoi faire en cas de collision? #

• Quoi faire s’il y a une collision, c-à-d si deux clés ont le même indice?

List<Character> valeurs = new ArrayList<>();

cle01 = new ChaineHashb("x");
cle02 = new ChaineHashb("y");

map.put(cle01, 'a'):

    // la clé est "x", l'indice est 1 (la longueur)
    int indice01 = cle01.indice();
    valeurs.set(indice01, 'a');

map.put(cle02, 'b'):

    // la clé est "y", l'indice est encore 1!
    int indice02 = cle02.indice();
    valeurs.set(indice02, 'b');      

    // oups! On vient d'écraser la paire "x":'a'

• En fait, on ne peut pas associer un indice directement à une valeur

• Il faut plutôt associer l’indice à un map naïf:

MapJava<Cle,Character>[] valeurs = new MapJava<Cle,Character>[1000];

cle01 = new ChaineHashb("x");
cle02 = new ChaineHashb("y");
cle03 = new ChaineHashb("z");

map.put(cle01, 'a'):

    // la clé est "x", l'indice est 1 (la longueur)
    int indice01 = cle01.indice();

    // insérer d'abord un map à l'indice
    valeurs[indice01] = new MapJavaNaif<>();

    valeurs[indice01].put(cle01, 'a');

map.put(cle02, 'b'):

    // la clé est "y",  l'indice est encore 1
    int indice02 = cle02.indice();
    valeurs[indice02].put(cle02, 'b');

map.put(cle03, 'c'):

    // la clé est "z", l'indice est encore 1
    int indice03 = cle03.indice();
    valeurs[indice03].put(cle03, 'c');

• S’il n’y a pas souvent de collision:

  • on accède aux valeurs surtout par indice
  • le map naïf associé à l’indice va contenir très peu de valeurs
  • c’est alors efficace

• Au contraire, s’il y beaucoup de collisions:

  • on accède presque toujours aux mêmes indices
  • le map naïf associé à un indice va contenir beaucoup de valeurs
  • on accède donc aux valeurs surtout en cherchant la clé
  • c’est alors inefficace

• Donc, une bonne fonction de hachage doit:

  • retourner le plus souvent possible un indice différent
  • retourner toujours le même indice pour la même clé (ne pas être aléatoire)

Implantation d’un map avec hachage #

• Voici le début de l’implantation

public class   MapHash <C extends CleHachable<?>, V extends Object> 
       extends MapJava<C,V> {
	
	private static final int TAILLE_TABLE_HACHAGE = 1000;
	
	@SuppressWarnings("unchecked")
	private MapJavaNaif<C,V>[] table = new MapJavaNaif[TAILLE_TABLE_HACHAGE];
	private int taille = 0;

• IMPORTANT:
  • la méthode CleHachable.indice peut retourner un indice >= table.length
  • il faut adapter l’indice à la table de notre tableau
  • habituellement, on fait ça avec l’opérateur modulo %

Efficacité #

• L’efficacité dépend du nombre de collisions, ce qui dépend en fait de:

  • la taille de la table de hachage
  • la qualité de la fonction de hachage

• On a encore le compromis temps/espace mémoire:

  • pour obtenir plus d’efficacité en temps, on va utiliser plus d’espace mémoire

• Exemple:

• La fonction Hashc est très efficace, alors que
  • Hashb est un peu efficace
  • Hasha équivaut à l’implantation naïve