Delphi Container Library: Les maps

Dans le précédent article nous avons abordé les listes de la DCL. Nous allons dans cet article voir un autre type de conteneur: les maps. Plus précisément ce sera les classes implémentant les maps avec hachage. Nous verrons donc en même temps les techniques de hachage.

La DCL est téléchargeable ici.

Une map est un conteneur qui pour chaque entité présente dans celui-ci fait l'association entre 2 objets. Cette association est souvent appelée pair. Un des objets de cette entité est considéré comme la clé, et l'autre comme la valeur. Ceci permet de stocker des objets par une référence (la clé) qui ne correspond pas a l'objet lui-même. On peut ainsi 'accéder à un objet dont on a comme connaissance que sa clé. La clé peut avoir différente forme : entier, chaîne de caractère, objets, etc. Typiquement, un tableau est une sorte de map : il associe un index à un élément du tableau.

Mais ce qui reste le plus intéressant c'est d'associer une chaîne de caractère à un objet, permettant ainsi de le nommer. Malheureusement, accéder à un élément à partir d'un nom au lieu d'un index, par exemple, implique un parcours du conteneur le rendant moins efficace. pour résoudre ce problème, on introduit la notion de hachage.

Le hachage permet de découper un grand ensemble d'entités en de plus petits sous-ensembles accessibles par ce que l'on appelle une clé. Le hachage le plus intuitif que l'on peut rencontrer dans la vie courante est le dictionnaire: Un dictionnaire est une grande liste de mots avec leur définition. Pour pouvoir rechercher rapidement dans un dictionnaire, cette liste de mots est hachée selon la première lettre du mot. Les mots sont donc regroupés dans des sous-ensembles dont la clé correspond à la première lettre du mot. Pour rechercher un mot on va directement au sous-ensemble qui correspond à la première lettre.

Au niveau algorithmique, on définit le hachage par une fonction (notée h(x)) qui a une clé (x) passée en paramètre fait correspondre une valeur hachée, représentant le plus souvent un index de tableau dont on va pouvoir accéder directement.

Pour reprendre l'exemple du dictionnaire, on aura une table de 26 éléments correspondant aux valeurs hachées (l'alphabet). la fonction de hachage fera correspondre une lettre à son index dans la table (A -> 0, B -> 1, C -> 2, D -> 3, …, X -> 23, Y -> 24 et Z -> 25). Les mots seront stockés sous forme de liste dont la tête sera une cellule de la table.

La recherche sera d'autant plus efficace que la table sera grande, et les collisions moins nombreuses. L'idéal serait d'avoir qu'un élément dans chaque cellule de la table. Mais ceci dépend de la nature des données et du choix de la fonction de hachage.

Une bonne fonction de hachage serait donc celle qui distribue le mieux les éléments dans la table. On considère que la fonction prend toujours comme clé une valeur entière. Pour les chaînes de caractères, on effectuera, au préalable, un calcul à partir de la valeur ascii des caractères. Par exemple on fera leur somme, pondérer chaque caractère par sa position, etc. L'objectif dans le choix d'une fonction de hachage est de séparer dans des cellules différentes de la table, des clés qui sont proches dans un certain sens. Il faut donc peut être faire varier la fonction avec la nature des clés à hacher.

C'est la fonction la plus simple. Elle fait correspondre une clé au reste de la division entière de cette clé avec la taille de la table. Par exemple pour une clé de valeur 100 et une taille de table de 26 on aura: 100 mod 26 = 22.

Cette méthode est très rapide mais souffre du défaut suivant : le choix de la taille de la table :

• si la taille de la table est une puissance de 2, le hachage va dépendre que des premiers bits de la puissance. Si la taille vaut 2, cela dépendra que du premier bit de la clé, si la taille vaux 4, des 2 premiers bits, si la taille est 16, des 3 premiers bits, etc. ;
• si on utilise des nombres décimaux, ne pas utiliser des puissances de 10 pour la taille de la table, car la fonction ne dépendra pas de tous les chiffres.

Bref, une taille assez éloignée des puissances de 2 est une bonne valeur. Par exemple, si on veut traiter 2000 chaînes de caractères et que l'on se fixe un maximum de 3 chaînes par cellule en collision, une bonne taille serait 701, car elle est proche de 2000/3 sans être trop proche d'une puissance de 2.

Elle consiste à multiplier la taille de la table (Capacity) par la partie fractionnaire de la clé (Key) multipliée par une constante (A) réelle entre 0 et 1. En code Delphi, ca donne:

Trunc(Capacity * (Frac(Key * A)));

Cette fonction n'est pas sujette aux problèmes que l'on rencontre dans la méthode de la division concernant la taille de la table.

La mise au point de cette fonction réside dans le choix de la constante A. Knuth (oui le Grand Knuth, encore lui) suggère pour A la valeur suivante:

(sqrt(5) - 1) / 2 = 0,6180339887...

Pour une taille de 256, et une valeur de 123456 on aura: 1.

Cette méthode donne de très bons résultats en pratique quant à la distribution des valeurs.

V-A. Les HashMap de la DCL▲

IPerson = interface
['{755C857B-A9E2-4D9D-8418-541CAEA79679}']
  function GetAge: Integer;
  function GetMarried: Boolean;
  function GetName: string;
  procedure SetAge(Value: Integer);
  procedure SetMarried(Value: Boolean);
  procedure SetName(const Value: string);
  property Age: Integer read GetAge write SetAge;
  property Married: Boolean read GetMarried write SetMarried;
  property Name: string read GetName write SetName;
end;

TPerson = class(TInterfacedObject, IPerson)
private
  FAge: Integer;
  FMarried: Boolean;
  FName: string;
protected
{ IPerson }
  function GetAge: Integer;
  function GetMarried: Boolean;
  function GetName: string;
  procedure SetAge(Value: Integer);
  procedure SetMarried(Value: Boolean);
  procedure SetName(const Value: string);
end;

var
  Map: IStrIntfMap;
  APerson: IPerson;
begin
  Map := TStrIntfHashMap.Create(16); // spécifie la taille de la table à 16
  APerson := TPerson.Create;
  APerson.Age := 42;
  APerson.Name := 'Hari Seldon';
  APerson.Married := True;
  Map.PutValue('Hari Seldon', APerson);
  APerson := TPerson.Create;
  APerson.Age := 30;
  APerson.Name := 'Golan Trevize';
  APerson.Married := False;
  Map.PutValue('Golan Trevize', APerson);

  APerson := IPerson(Map.GetValue('Hari Seldon')); // Récupère la personne selon son nom
  ShowMessage(APerson.Name + ' ' + IntToStr(APerson.Age));
end;

La DCL utilise la méthode de la multiplication, la fonction de hachage est définie de la façon suivante :

function TStrIntfHashMap.HashMul(Key: Integer): Integer;
const
  A = 0.6180339887; // (sqrt(5) - 1) / 2
begin
  Result := Trunc(FCapacity * (Frac(Key * A)));
end;

Il est bien sûr tout a fait possible de changer cette fonction grâce à la propriété HashFunction des classes.

Pour les strings, la méthode consiste a faire la somme des valeurs ascii des caractères pondérées par leur position:

function TStrIntfHashMap.HashString(const Key: string): Integer;
var
  I: Integer;
begin
  Result := 0;
  for I := 1 to Length(Key) do
    Result := Result + (Ord(Key[I]) * (I - 1) * 256);
end;

Un autre conteneur de la DCL est haché : Les HashSets.

Nous avons vu ce qu'était une map et différentes méthodes de hachage ainsi que leur intérêt dans la recherche à partir de clé.

D'autre part, il a été présenté un exemple d'utilisation de HashMap fournit par la bibliothèque  DCL.

Si vous avez des remarques, des idées d'améliorations, ou des bugs, n'hésitez pas à les reporter sur le site du projet: http://sourceforge.net/projects/dclx ou par E-Mail : .

Introduction à l'algorithmique (Thomas Cormen, Charles Leiserson, Ronald Rivest). Édition Dunod, ISBN: 2 10 003128 7