Table de hachage

Les fonctions de recherche précédemment citées opèrent sur les listes. Elles sont parfaitement utilisables lorsque le nombre d'éléments ne dépasse pas la cinquantaine. Au-delà, le temps de recherche devient prohibitif et on est amené à utiliser d'autres méthodes d'indexation.

Dans les moteurs de bases de donnée, la méthode d'indexation la plus souvent utilisée repose sur l'algorithme des b-arbres (b-tree). C'est un algorithme complexe qui garanti un temps maximum dans la recherche d'un élément.

Une autre technique couramment utilisée repose sur les tables de hachage, plus simples à réaliser.

L'élément de base d'une table de hachage est toujours un couple constitué d'un index et d'une valeur. Mais au lieu de conserver une liste unique de couples, une table de hachage est un tableau de taille constante contenant des listes de couples.

Les couples de chaque liste ont un point commun : La valeur de hachage de leur index est identique et vaut le numéro de la ligne du tableau.

Ainsi, au lieu de rechercher l'index dans tous les couples, on calcule d'abord sa valeur de hachage qui donne la ligne du tableau concernée. La recherche s'effectue alors dans la liste de couples de cette ligne du tableau.

Il en va de même pour le remplissage de la table : La valeur de hachage est préalablement calculée, ce qui retourne la ligne du tableau concernée. Le couple est alors ajouté dans cette liste.

Nous allons maintenant réaliser notre bibliothèque pour manipuler les tables de hachage.

Une table de hachage est définie comme étant un vecteur. Elle est construite avec :

(define (new-hash size)
  (let ((hash (make-vector size)))
    (vector-fill! hash '())
    hash))

On définit aussi un prédicat qui retourne #t si l'objet est une table de hachage :

(define (hash? object)
  (vector? object))

Supposons que nous ayons à notre disposition une fonction hash. Cette fonction retourne un entier positif unique à partir d'un objet et d'une valeur maximale. L'entier retourné est le modulo de la valeur maximale. L'objet peut être un symbole, une chaîne de caractère ou un entier.

La fonction permettant de retrouver la valeur associée à un index s'écrit alors :

(define (hash-get index hash)
  (let* ((offset (hash object
                       (vector-length hash)))
         (value  (assq object
                       (vector-ref hash
                                   offset))))
    (if value
       (cdr value)
       #f)))

Notons la présence de let* qui permet d'utiliser la variable offset dans le calcul de value.

La fonction permettant d'ajouter une association entre un index et une valeur dans la table s'écrit alors :

(define (hash-put object value hash)
  (let* ((offset (hash object
                       (vector-length hash)))
         (assocs (vector-ref hash offset))
         (old    (assq object assocs)))
    (if old
       (set-cdr! old value)
       (vector-set! hash
                    offset
                    (cons (cons object value)
                          assocs)))))

Définissons maintenant la fonction hash. Pour une valeur et une longueur, elle retourne un entier constant inférieur à la longueur. Elle peut être réalisée comme suit :

(define (hash index len)
  (cond ((symbol? index)
         (hash (symbol->string index)))
        ((string? index)
         (let ((somme 0))
           (do ((i 0 (+ i 1)))
                ((>= i (string-length index)))
             (set! somme
                   (+ somme
                      (char->integer
                      (string-ref index i)))))
           (modulo somme len))))
        ((integer? index)
         (modulo index len))))

Nous disposons maintenant d'une table de hachage permettant de réaliser une base de données. La technique du hachage reste utilisable jusqu'à plusieurs millier d'enregistrements.

Notons aussi que la table de hachage peut être facilement sauvegardée et restaurée sur disque. Considérons :

Osm> (define h (new-hash 100))
  => #unspecified

Osm> (hash-put 'dupont
               (construit-client "Dupont"
                                 "Robert"
                                 26)
               h)
  => #unspecified

Osm> ...
  => #unspecified

Osm>(with-output-to-file "client.db"
                         (lambda ()
                           (write h)))
  => #unspecified

L'utilisation de write est nécessaire pour conserver les chaînes de caractères entre guillemets. En effet, display n'affiche pas les guillemets entourant les chaines de caractères.

Quittons maintenant notre environnement Scheme, éteignons la machine serveur, allons boire un café:).

Après ce divertissement, revenons aux choses sérieuses, allumons le serveur, ouvrons une session Scheme et tapons :

Osm> (define h #f)
  => #unspecified

Osm>(with-input-from-file "client.db"
                           (lambda ()
                             (set! h (read)))
  => #unspecified
     ; notre base est maintenant restaurée!

Il est possible d'imaginer les choses de manière plus complexes, avec une pagination de la base, une répartition sur plusieurs machines, etc.