Les tables de hachage

La particularité du code qui va suivre est la suivante : l'utilisateur peut choisir, s'il le souhaite, la méthode de gestion des collisions. Ainsi, il pourra adapter le comportement de la table en fonction des situations… Et aussi parce que ce n'est pas spécialement plus compliqué à coder !
Pour l'instant, on ne va pas voir le code des méthodes (même s'il est simple), mais sachez que j'implémenterai l'interface suivante.

public interface CollisionManagement
{
    public int nextIndex(Object key, int n, int i);
}

L'idée de la méthode nextIndex est très simple : si le premier indice calculé pour une clé donne une case occupée, on va l'appeler et elle va renvoyer le prochain indice à vérifier. Voici la signification des arguments :

• Object key : la clé dont on cherche l'indice, utile pour la seconde fonction de hachage ;
• int n : la taille du tableau, pour pouvoir renvoyer un indice valable ;
• int i : l'itération à laquelle on se trouve.

Le but de la manœuvre est que, lors de l'instanciation de la table de hachage, on passe au constructeur une référence vers une classe implémentant cette interface. Par exemple, pour du sondage linéaire :

HashTable<Key, Object> h = new HashTable<Key, Object>(new LinearProbing());

Dans la suite du code, j'ai fait le choix de placer la fonction de compression du hash code dans ce gestionnaire de collisions. Cela peut paraître bizarre comme choix, mais si je l'avais mis dans la clé, je n'aurais pas pu utiliser la classe Object pour la désigner (vu que cette méthode n'existe pas dedans). De plus, comme dit dans la partie théorie, ça sera plus facile pour introduire des facteurs destinés à protéger le système d'une attaque DDOS, ou encore dans le cas du double hachage, d'utiliser l'astuce pour parcourir toutes les cases.
Nous reviendrons sur ces points un peu plus loin, quand nous implémenterons les méthodes de gestion de collision.

Entrons enfin dans le vif du sujet ! La table de hachage en elle-même ne constituera qu'une seule et même classe, qui implémente l'interface SymbolTable. Au niveau des méthodes, on a donc toutes celles des tables de symboles, mais on va en ajouter une autre qui va nous simplifier grandement la vie : getBucketIndex.
En effet, dans le code une action reviendra systématiquement : celle de chercher l'emplacement d'une clé, qu'elle existe ou qu'elle n'existe pas. Ainsi, getBucketIndex va prendre en entré une clé, et, à l'aide de la fonction de hachage et du module de gestion des collisions, va retourner l'indice de la case de la table dans laquelle la clé devrait se trouver. Lorsque cette méthode sera écrite, 90% du travail sera fait !
Il ne faudra pas non plus oublier de coder une fonction de hachage, sinon on n'ira pas loin.

Au niveau des variables membres, on va définir les éléments suivants :

• un tableau d'emplacements pour des clés. Chacun de ces emplacements sera défini par une classe Bucket ;
• un entier pour compter le nombre d'objets entrés dans la table ;
• une référence vers le module de gestion des collisions (l'interface CollisionManagement).

Des variables seront rajoutées par après, nous les verrons en temps voulu. Pour l'instant, on va se contenter de remplir le code qui suit.

Notez qu'il faut prendre aussi en compte les cas où l'utilisateur n'entre pas de gestionnaire de collisions, ainsi que celui où il ne spécifie pas de taille. Pour cela, on va définir une constante qui indiquera la taille par défaut.
Je vous épargne ainsi le code des constructeurs : il ne s'agit que d'une instanciation. Par défaut, le système de gestion des collisions sera le sondage linéaire, mais libre à vous d'en mettre un autre !

public class HashTable <K,V> implements SymbolTable<K,V>
{
    private Bucket<K,V>[] bucketArray;        // Tableau contenant les paires "clé-valeur"
    private int nbrObject = 0;           // Nombre d'éléments insérés
    private CollisionManagement manager; // Gestionnaire de collision
    private static final int DEFAULTSIZE = 16;

    public HashTable()
    {
        this(DEFAULTSIZE);
    }
    
    public HashTable(int size)
    {
        this(size, new LinearProbing());
    }
    
    public HashTable(CollisionManagement manager)
    {
        this(DEFAULTSIZE, manager);
    }    
    
    public HashTable(int size, CollisionManagement manager)
    {
        this.manager = manager;
        bucketArray = (Bucket<K,V>[]) new Bucket<?,?>[size];
    }
    
    public void put(K key, V value) throws HashTableException {}

    public V get(K key) throws HashTableException {}

    public V remove(K key) throws HashTableException {}
        
    public boolean contains(K key) {}
        
    public int size() {}

    private int getBucketIndex(K key) {}
}

II-C-2-a. La méthode getBucketIndex▲

private int getBucketIndex(K key)
{
    return getBucketIndex(key, true); // Par défaut, on cherche la clé en ignorant les cases libres
}

private int getBucketIndex(K key, boolean ignoreFreeBucket)
{
    int index = manager.nextIndex(key, bucketArray.length, 0); // Calcul du premier indice
    
    for(int i = 0 ;
                bucketArray[index] != null                            // Tant que la case n'est pas vide...    
            && (!bucketArray[index].isFree() || ignoreFreeBucket)    // ... ou qu'elle n'est pas libre et que cela importe
            && !key.equals(bucketArray[index].getKey())             // ... ou qu'on ne trouve pas la clé
            ; i++)
    {
        index = manager.nextIndex(key, bucketArray.length, i); // On va à la prochaine case
    }
    return index;
}

II-C-2-b. La méthode put▲

public void put(K key, V value) throws HashTableException
{
    if(bucketArray.length == nbrObject) // D'abord vérifier s'il reste de la place
        throw new HashTableException("Table pleine.");
    
    int index = getBucketIndex(key, false); // L'emplacement de la paire "clé-valeur"
    
    if(bucketArray[index] == null || bucketArray[index].isFree())
        nbrObject++;
    
    bucketArray[index] = new Bucket<K,V>(new Entry<K,V>(key, value));    
}

II-C-2-c. La méthode get▲

public V get(K key) throws HashTableException
{
    if(nbrObject == 0) // Si la table est vide, cela ne sert à rien de continuer.
        throw new HashTableException("Table vide.");
        
    Bucket<K,V> bucket = bucketArray[getBucketIndex(key)]; // Case dans laquelle devrait se trouver la clé
    
    if(bucket != null && !bucket.isFree()) // Si la case est occupée, on a trouvé notre clé !
        return bucket.getValue();
    else
        throw new HashTableException("Clé non trouvée");
}

II-C-2-d. La méthode contains▲

public boolean contains(K key) throws HashTableException
{
    if(nbrObject == 0) // Si la table est vide, cela ne sert à rien de continuer.
        throw new HashTableException("Table vide.");
    
    Bucket<K,V> bucket = bucketArray[getBucketIndex(key)];
    return (bucket != null && !bucket.isFree());
}

II-C-2-e. La méthode remove▲

public V remove(K key) throws HashTableException
{
    if(nbrObject == 0) // Si la table est vide, cela ne sert à rien de continuer
        throw new HashTableException("Table vide.");
            
    Bucket<K,V> delete = bucketArray[getBucketIndex(key)]; // La case à nettoyer
        
    if(delete == null || delete.isFree()) // Si la case est vide ou déjà nettoyée, on peut s'arrêter
        throw new HashTableException("Clé non trouvée.");
    
    V temp = delete.getValue(); // Valeur à retourner
    delete.clean(); // On marque la case comme libre
    nbrObject--;
    
    return temp;
}

II-C-2-f. Les méthodes size et isEmpty▲

public int size()
{
    return nbrObject;
}
public boolean isEmpty()
{
    return (nbrObject == 0);
}

Passons à la partie la plus amusante, qui consiste à implémenter nos méthodes de gestion de collision. Grâce à l'interface CollisionManagement et la manière dont est construite la table, cela va être un jeu d'enfant !
Nous n'avons donc qu'une seule méthode à implémenter : nextIndex. N'oubliez pas non plus qu'il faudra compresser le hash code de la clé.

public interface CollisionManagement
{
    public int nextIndex(Object key, int n, int i);
}

II-C-3-a. Implémentation du sondage linéaire▲

public class LinearProbing implements CollisionManagement
{
    public int nextIndex(Object key, int n, int i)
    {
        int h = compression(key.hashCode(), n);
        
        return (h + i) % n;
    }
    private int compression(int h, int n)
    {
        return h % n;
    }
}

II-C-3-b. Implémentation du sondage quadratique▲

public class QuadraticProbing implements CollisionManagement
{    
    private int c1, c2;
    
    // Si l'utilisateur ne spécifie pas les constantes lors de l'instanciation
    public QuadraticProbing()
    {
        this(0, 1); // Ou les générer aléatoirement
    }
    
    public QuadraticProbing(int c1, int c2)
    {
        this.c1 = c1;
        this.c2 = c2;
    }
    public int nextIndex(Object key, int n, int i)
    {
        int h = compression(key.hashCode(), n);
        return (h+ c1 * i + c2 * (i * i))% n;
    }
    private int compression(int h, int n)
    {
        return h % n;
    }
}

II-C-3-c. Implémentation du double hachage▲

public class DoubleHash implements CollisionManagement
{    
    public int nextIndex(Object key, int n, int i)
    {
        int h = compression(key.hashCode(), n);
        return (h + i * hash2(key, n)) % n;
    }
    private int compression(int h, int n)
    {
        return h % n;
    }
    private int hash2(Object key, int n)
    {
        int h = key.hashCode();
        n--;
            
        return 1 + (h % n);
    }
}

II-C-3-d. Sécurisation de la table avec le hachage universel▲

import java.util.Random;

public class LinearProbing implements CollisionManagement
{
    private int a, b, p;

    public LinearProbing()
    {
        p = 1073676287; // Grand nombre premier

        Random generator = new Random(); // Générateur de nombres aléatoires
        
        a = (Math.abs(generator.nextInt()) % p)  + 1;
        b = Math.abs(generator.nextInt()) % p;
    }
    public int nextIndex(Object key, int n, int i)
    {
        int h = compression(key.hashCode(), n);
    
        return (h + i) % n;
    }
    private int compression(int h, int n)
    {
        return Math.abs(a * h + b) % n;
    }
}

Il s'agit d'un nœud de liste doublement liée classique, avec une référence vers la case précédente, une autre vers la suivante, et une référence vers le conteneur Entry.
Pour universaliser le tout, on va paramétrer la classe du conteneur, pour éventuellement réutiliser le nœud plus tard.

public class Node<E>
{
    private E entry;
    private Node<E> next, prev; // Noeuds précédent et suivant
    
    public Node(E entry)
    {
        this(entry, null);
    }
    
    public Node(E entry, Node<E> next)
    {
        this.entry = entry;
        this.next = next;
        this.prev = null;
    }
    
    // Accesseurs
    public E getEntry() { return entry; }
    public Node<E> getNext()    { return next;  }
    public Node<E> getPrev()    { return prev;  }
    
    // Mutateurs
    public void setNext(Node<E> next) { this.next = next;      }
    public void setPrev(Node<E> prev) { this.prev = prev;      }
}

Notez que le premier constructeur va créer un nœud « seul », sans lien vers un autre, tandis que le second va, lui, définir un nœud suivant. Cela nous servira pour la classe Bucket quand on ajoutera un nœud dans la liste.

La classe Bucket va donc gérer une liste. On va y implémenter des méthodes qui permettent d'ajouter, de chercher et de supprimer un nœud en connaissant la clé qu'il contient.
En variable membre, on va retenir le nombre de nœuds qui ont été insérés et le premier nœud de la liste. On va implémenter les méthodes suivantes :

public class Bucket<K,V>
{
    private int nbrNode = 0;

    private Node<Entry<K,V>> list; // Tête de liste
    
    public Bucket(Entry<K,V> e)
    {
        this.addNode(e);
    }
    public Node<Entry<K,V>> getFirstNode() {}
    
    public boolean addNode(Entry<K,V> e) {}
    
    public V removeNode(K key) throws HashTableException {}
    
    public Node<Entry<K,V>> getNode(K key) {}
    
    public boolean containsNode(K key) {}
    
    public int getNbrNode() {}
}

Elles seront toutes utilisées par la classe HashTable. On passera sur la méthode qui retourne le nombre de nœuds et le constructeur, vu qu'ils sont très simples.

II-D-2-a. La méthode getNode▲

public Node<Entry<K,V>> getNode(K key)
{
    Node<Entry<K,V>> n = list;
    
    /*     Tant qu'on n'a pas la clé ou qu'on n'est pas dans un noeud vide,
        on avance dans la liste */
    while(n != null && !n.getEntry().getKey().equals(key))
        n = n.getNext();
    return n;
}

II-D-2-b. La méthode addNode▲

public boolean addNode(Entry<K,V> e)
{
    if(list == null)
    {
        list = new Node<Entry<K,V>>(e);
        nbrNode++;
        return true;
    }
    
    Node<Entry<K,V>> n = getNode(e.getKey());

    if(n != null) // Si la clé est déjà dans la liste, on change la valeur
    { 
        n.getEntry().setValue(e.getValue());
        return false;
    }

    // Si la clé n'est pas dans la liste, on ajoute un noeud
    
    nbrNode++;
    Node<Entry<K,V>> v = new Node<Entry<K,V>>(e, list); // Nouveau noeud, future tête de liste
        
    if(list != null) // S'il y a déjà un noeud en tête, on met à jour la référence prev
        list.setPrev(v);
        
    list = v; // Mise à jour de la tête de liste
    return true;
}

II-D-2-c. La méthode removeNode▲

public V removeNode(K key) throws HashTableException
{
    Node<Entry<K,V>> n = getNode(key);
    
    if(n == null)
        throw new HashTableException("Clé non trouvée.");
    
    V temp = n.getEntry().getValue();
    nbrNode--;
    
    if(n.getPrev() != null) // Si le noeud est dans la liste
        n.getPrev().setNext(n.getNext());
    else // Si le noeud est le premier de la liste
        list = n.getNext();
    
    if(n.getNext() != null)
        n.getNext().setPrev(n.getPrev());
    
    return temp;
}

II-D-2-d. La méthode containsNode▲

public boolean containsNode(K key)
{
    return (getNode(key) != null);
}

On arrive enfin à la partie amusante ! Tout ce que nous allons faire est de la manipulation de listes.

On va cependant se retrouver confronté à un « petit » problème : vu qu'il n'y a qu'un seul moyen de gérer les collisions, on n'a pas besoin de module de gestion des collisions (l'interface CollisionMangement). Or, c'est ce module qui se charge de donner l'indice en hachant et compressant la clé.
On va donc définir deux méthodes privées, une qui va donner l'indice d'une clé et une autre qui va compresser le hash code.

private int getIndex(K key)
{
    return compress(key.hashCode());
}
private int compress(int h)
{
    return h % bucketArray.length;
}

Bien évidemment, vous pouvez utiliser le code de hachage universel de la section précédente.

II-D-3-a. La méthode put▲

public void put(K key, V value)
{
    int index = getIndex(key);
    
    Entry e = new Entry(key, value);
    
    if(bucketArray[index] != null) // Si la liste est instanciée
    {
        if(bucketArray[index].addNode(e))
            nbrObject++;
    }
    else
    {
        bucketArray[index] = new Bucket<K,V>(e);
        nbrObject++;
    }
}

II-D-3-b. La méthode get▲

public V get(K key) throws HashTableException
{
    // Si la table est vide, on ne trouvera jamais notre clé
    if(nbrObject == 0)
        throw new HashTableException("Table vide.");
        
    int index = getIndex(key);
    
    // Si la liste n'est pas instanciée ou est vide, on s'arrête également
    if(bucketArray[index] == null || bucketArray[index].getNbrNode() == 0)
        throw new HashTableException("Clé non trouvée");
    
    Node<Entry<K,V>> n = bucketArray[index].getNode(key);
    
    // Si le noeud existe, on retourne la valeur
    if(n != null)
        return n.getEntry().getValue();
    else
        throw new HashTableException("Clé non trouvée.");
}

II-D-3-c. La méthode contains▲

public boolean contains(K key)
{
    if(nbrObject == 0)
        return false;
        
    int index = getIndex(key);
    Bucket<K,V> b = bucketArray[index];
    
    // Retourne vrai si la liste existe et contient un noeud de clé key
    return (b != null && b.containsNode(key));
}

II-D-3-d. La méthode remove▲

public V remove(K key) throws HashTableException
{
    if(nbrObject == 0)
        throw new HashTableException("Table vide.");
        
    int index = getIndex(key);
    
    if(bucketArray[index] == null)
        throw new HashTableException("Clé non trouvée.");

    nbrObject--;
    return bucketArray[index].removeNode(key);
}

Pour rappel, le facteur de charge est le rapport entre le nombre d'objets insérés et la taille de la table. Une petite division suffit, suivie d'une comparaison.
La stratégie que j'ai suivie est de créer une nouvelle table de hachage plus grande, et d'y insérer toutes les entrées de la table à redimensionner. Il suffira ensuite de mettre à jour la référence de la table, et le tour sera joué.

float loadFactor = (float) nbrObject / bucketArray.length;
if(loadFactor >= MAXLOADFACTOR)
{
    int t =  (int) (bucketArray.length * 1.5); // Nouvelle taille
    
    HashTable<K,V> tmp = new HashTable<K,V>(t, management);
    
    /* Récupérer les entrées et les insérer dans tmp */
    
    bucketArray = tmp.bucketArray;
}

Vous êtes bien évidemment libre de choisir la nouvelle taille que vous voulez, sans prendre une taille plus petite, sinon vous allez entrer dans une boucle de redimensionnements sans fin. Par contre, n'oubliez surtout pas de spécifier le type de gestion des collisions, sinon il y aura des inconsistances !

Pour les sondages, il suffit de parcourir le tableau : si la case est instanciée et non libre, on ajoute la clé et la valeur dans la table temporaire.

for(int i = 0 ; i < bucketArray.length ; i++)
{
    Bucket<K,V> b = bucketArray[i];
    
    if(b != null && !b.isFree())
        tmp.put(b.getKey(), b.getValue());
}

Le code de calcul et de création de la nouvelle table de hachage est exactement le même, si ce n'est qu'il ne faut pas spécifier de méthode de gestion des collisions dans le constructeur de cette dernière. Seul le code de parcours est à adapter.
Pour nous faciliter grandement la vie, on va définir une méthode removeFirstNode dans la classe Bucket, et qui va retourner le premier nœud de la liste tout en le supprimant. Ainsi, on n'aura qu'à itérer sur le nombre de nœuds de l'alvéole ; tant qu'il y aura des nœuds, on retirera le premier et on l'ajoutera dans la nouvelle table.

Le code est très similaire à la suppression de n'importe quel nœud, si ce n'est qu'on retire le nœud de tête. Il va donc falloir redéfinir le nœud de tête (s'il existe) et mettre à jour la référence du nœud précédent, pour autant que ces nœuds existent.

public Node<Entry<K,V>> removeFirstNode()
{
    if(list == null || nbrNode == 0)
        return null;
    
    /* Mise à jour de la référence du second élément de la liste, pour 
     * autant qu'il existe. */
    Node<Entry<K,V>> newList = list.getNext();
    
    if(newList != null)
        newList.setPrev(null);
    
    // Le noeud à retourner, pour ne pas perdre la référence
    Node<Entry<K,V>> firstNode = list;
        
    // Mise à jour du noeud de tête
    list = newList;
    nbrNode--;
    
    return firstNode;
}

Le code pour le redimensionnement devient alors extrêmement simple, puisqu'il suffit d'itérer sur le nombre de nœuds et de retirer chaque fois le premier nœud, tant qu'il y en a, et ce pour chaque alvéole de la table.

for(int i = 0 ; i < bucketArray.length ; i++)
{
    Bucket<K,V> b = bucketArray[i];
    
    if(b == null)
        continue;
        
    while(b.getNbrNode() > 0)
    {
        Node<Entry<K,V>> n = b.removeFirstNode();
        tmp.put(n.getEntry().getKey(), n.getEntry().getValue());
    }
}