Introduction
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.
Les maps
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
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
lette.
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.
La méthode de la division
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
veux 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.
La méthode de la multiplication
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.
Les HashMap de la DCL
La DCL fournit 5 interfaces concernant les
maps:
-
IIntfIntfMap :
associe une interface à une autre interface.
-
IStrIntfMap
: associe une string à une interface.
-
IStrStrMap
: associe une string à une autre string.
-
IStrMap
: associe une string a un objet (TObject)
-
IMap :
associde un objet (TObject) à un autre objet (TObject)
Pourquoi tant d'interfaces ? Simplement pour
gérer la majorité des types de Delphi et les façons dont
on pourrait les associer. Selon la combinatoire, il faudrait
beaucoup plus d'interfaces, mais je me suis limité à ce
qui serait intéressant d'avoir en pratique.
Pour chacune des interfaces ci-dessus, une
HashMap est implémentée:
-
TIntfIntfHashMap
-
TStrIntfHashMap
-
TStrStrHashMap
-
TStrHashMap
-
THashMap
Exemple
Nous voulons avoir une map qui pour un nom
associe une personne définie par:
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; |
On définit la HashMap de cette
façon:
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; |
Méthode de hachage utilisée
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.
Conclusion
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 : rdm_30@yahoo.com.
Référence
Introduction à l'algorithmique
(Thomas Cormen, Charles Leiserson, Ronald Rivest). Edition
Dunod, ISBN: 2 10 003128 7
par Jean-Philippe
BEMPEL
|
