HASHAGE

Le hachage est une méthode est une méthode pour entreposer des données dans un tableau, liste... Les recherches, insertion et les effacements de données sont très rapide. La complexité est théoriquement de O(1). Pour arriver à un tel résultat, chaque valeur doit avoir sa propre clé. Il y a une fonction de hashage qui retourne la position.
Dans cet exemple, nous dirons que Jean hashe 0, Paul hashe 1...

0	Jean	Durocher
1	Paul	Rivet
2
3
4	Sam	Piq
5	Eric	Melvin

Il faut avoir une fonction de hashage qui permet de placer chaque clé au bon endroit. Il faut aussi décider ce qu'on va faire lorsque deux clés hashe la même valeur.

type
  THash_Record = record
  cle   : integer;
  donne  : integer;
end;

const
  HASH_LENGTH = 100;

type
  THash_Table = array[0..HASH_LENGTH-1] of THash_Record;

function fonction_hash(cle : integer) : integer;
begin
  Hash_Function := cle MOD HASH_LENGTH;
end;

procedure Inserer( var hash : THash_table;rec  : THash_record);
begin
  hash[ fonction_hash(rec.cle) ] := rec;
end;

Telle que je l'ai souvent vu, j'ai décidé d'employer le modulo pour la fonction d'hashage. Il est possible lors d'insertion d'enregistrement qu'il y ait des collisions. C'est-à-dire que deux clés différentes retournent la même adresse avec la même fonction de haschage. En pratique ça arrive rarement, mais faut tenir compte de cette situation.

Nous allons un peu modifier la structure de départ pour nous adapter à cette réalité. La technique ici utilisée est dite ouverte. C'est-à-dire que nous allons mettre les éléments qui hashent sur la même valeur dans une liste. Cette méthode est moins performante.

const
  HASH_LENGTH = 100;

type
  PHash_Record = ^THash_Record;
  THash_Record = record
    cle   : integer;
    donne  : integer;
    prochain  : PHash_Record; //pointeur sur le prochain élément
  end;

THash_Table = array[0..HASH_LENGTH-1] of PHash_Record;

procedure Inserer( var hash : THash_Table; rec  : THash_Record);
var
  hash_address : integer;
  item         : PHash_record;
begin
  hash_address := fonction_hash(rec.cle);
  new(item);
  item^ := rec;
  item^.prochain = hash[ hash_address ];
  hash[ hash_address ] := item;
end;

procedure Obtenir(hash : THash_Table;cle  : integer; var rec  : THash_Record);
var
  hash_address : integer;
  item         : PHash_record;
begin
  hash_address := fonction_hash(rec.cle);
  item := hash[ hash_address ];
  while (item <> nil) and (item^.cle <> cle) do
    item := item^.next;
  if (item<>nil) then //si dans la liste
    rec := item^
end;

Maintenant si une clé retourne la même adresse de hashage (élément du tableau), nous insérons cette donnée dans la liste de cette donnée hashé.

Afin d'améliorer les performances, il est possible au lieu de mettre les éléments qui hashent sur la même valeur dans la liste, d'utiliser des fonctions quadratiques ou faire du double hashage.