13.5 Les fonctions de h-code

Dans les discussions précédentes nous avons supposé l'existence d'une fonction H qui fasse correspondre, avec toutes les exigences nécessaires (rapidité, uniformité, etc.), au domaine de valeurs des clés K celui des adresses [0 .. M-1] du tableau de h-code. La question est alors : comment construire (ou choisir) une telle fonction H ?

De toutes les formes de fonctions H (cf. Knuth, vol. III déjà cité) nous n'en retiendrons que 2 :

a)

Les fonctions basées sur une méthode de division.

b)

Les fonctions basées sur une méthode de multiplication.

Le papier suivant constitue une excellente synthèse sur les fonctions de h-code et contient une bibliographie très étendue sur ce sujet :

G.D. Knott, "Hashing functions".
The Computer Journal, vol. 18, No. 3, 1975, pp. 265-278.

13.5.1 Les méthodes de division

La méthode de division pour une fonction de h-code est celle que nous avons employée dans les exemples traités jusqu'ici. Elle consiste à prendre comme indice dans le tableau le reste de la division de la clé (il faut qu'elle soit entière !) par la taille du tableau.

c'est-à-dire H(k) = k mod M (1)

Il est toujours possible, par un procédé adéquat, de transformer une clé quelconque en une valeur entière, ne serait-ce qu'en déterminant son ordinal dans un ensemble de valeurs possibles.

Dans la formule (1) il faut cependant choisir M avec soin. Ainsi, si M est une puissance de la base numérique de la machine, M = 2^r, alors le calcul de H(k) revient à isoler les r bits les moins significatifs de la clé K (par divisions entières successives dont on ne considère que le reste).

Prendre M parmi les nombres premiers est un pas dans la bonne direction, cependant il faut alors faire attention au fait que dans certains cas le calcul de H(k) revient à simplement superposer les valeurs des composantes d'une clé. Par exemple :

• Soit une clé constituée de 3 caractères C₁ C₂ C₃ (pris dans l'ensemble des 64 caractères EBCDIC par exemple). Soit une table de 4097 positions, ce qui correspond à 2¹² + 1 (ou 64²+1) et démontré par Fermat comme étant un nombre premier.

  Si pour la fonction de h-code on considère

  H(C₁ C₂ C₃) = (C₁ C₂ C₃) mod (2¹² + 1)

  et, si on exprime (C₁ C₂ C₃) comme une combinaison linéaire dans la base 64, on obtient :

  H(C₁ C₂ C₃) = (C₁ * 64² + C₂ * 64 + C₃) mod (64² + 1)

  alors, si (C₃ + 64*C₂) > C₁ , le quotient de (C₁ C₂ C₃) divisé par 2¹²+1 est simplement C₁ et le reste est de la forme :

  (C₁*64² + C₂*64 + C₃) - (C₁*(64² + 1)) = (C₂*64 + C₃) - C₁

  Ainsi exprimée en base 64, la valeur de H(C₁ C₂ C₃) est (C₂ C₃-C₁)₆₄ , qui est une simple superposition des caractères de la clé K. On voit donc que différentes permutations des mêmes lettres donneront le même résultat et augmenteront ainsi le risque de collision.

  En généralisant on dira que choisir la taille M d'un tableau de h-code comme étant de la forme

  b^ra,

  où b est la base de l'ensemble des caractères et r ainsi que a sont de petites constantes, est à éviter!

  Si ce choix est évité, l'expérience montre que la méthode de division présente de bons résultats. De plus la méthode de division semble (expérimentalement) se combiner valablement avec un traitement de collisions par chaînage externe.

  13.5.2 Les méthodes multiplicatives

  Ces méthodes reposent souvent sur les propriétés de distribution de nombres particuliers. Ainsi, si l'on considère le nombre d'or

  

  et que l'on calcule ses multiples i* pour i [1,10], que l'on isole la partie fractionnaire de ces multiples et que l'on détermine le plus grand entier plus petit ou égal à 10 fois la partie fractionnaire, on obtient le tableau suivant (avec {i*} = (i* - i*), où { } signifie partie fractionnaire) :

  	multiple	partie fract.	plancher de  10*partie fract.
  i	i*	{i*}	10*{i*}
  1	0.618034	.618034	6
  2	1.236068	.236068	2
  3	1.854102	.854102	8
  4	2.472136	.472136	4
  5	3.090170	.090170	0
  6	3.708204	.708204	7
  7	4.326238	.326238	3
  8	4.944272	.944272	9
  9	5.562306	.562306	5
  10	6.180340	.180340	1

  L'examen de ce tableau appelle quelques remarques :

  1. Les dix premières valeurs de la dernière colonne sont des permutations des nombres entiers entre 0 et 9. Ainsi, on peut utiliser, comme indice primaire, la partie fractionnaire du multiple du nombre d'or, mis à l'échelle de la taille de la table et arrondi de manière appropriée.

  2. Si on considère les parties fractionnaires des multiples du nombre d'or {i*} (3ème colonne du tableau), on constate que ces valeurs sont comprises dans l'intervalle [0,1] et qu'elles le subdivisent de manière particulièrement subtile. En effet chaque nouvelle valeur partage le plus grand intervalle restant (c'est-à-dire qui n'est pas le résultat de la dernière subdivision) en parties respectant le nombre d'or. Ceci est illustré par la figure 13.6.

  

  Ces différentes constatations peuvent conduire à la généralisation suivante. Si R est un nombre irrationnel, alors la suite obtenue par :

  {R}, {2R}, ... {nR} où {x} indique la partie fractionnaire de x

  lorsqu'elle est placée dans l'intervalle [0,1], le subdivise en M + 1 segments de façon identique au nombre d'or .

  Ainsi, si l'on a une table de dimension M et une clé entière K qui est utilisée comme multiplicateur de R, on peut construire la fonction de h-code suivante :

  H(K) = M * {KR} (2)

  La formule (2) est générale et, dans une application réelle, il faut, si possible, une fonction de h-code qui :

  a)

  soit rapide à calculer;

  b)

  minimise les collisions.

  Un développement complexe (cf. Knuth) permet de montrer que ces objectifs sont atteints si l'on considère la formule suivante :

  étant donné un nombre irrationnel R et un tableau de stockage de taille M=2^m, on détermine un entier A tel que R A/w
  où w représente le nombre d'entiers représentables sur 1 mot machine de r bits (w = 2^r)

  on obtient alors :

  H(k) = M * ((k* A/w ) mod 1) = (M*(A*k mod w)) / w

  (k représente la valeur entière de la clé) ce qui revient à multiplier k par A, tronquer le résultat à 1 mot machine et conserver les m bits de gauche ( M=2^m).

  En conclusion, on peut dire que la méthode du h-code constitue une alternative à la structure d'arbre binaire lorsque :

  1. il n'est pas nécessaire de gérer dynamiquement les données;

  2. il n'est pas important de traiter les cas les plus défavorables avec un maximum de performances (ce que font les arbres binaires équilibrés en garantissant un nombre de comparaisons maximum de l'ordre de log₂(N), mais ce que ne peut garantir la méthode du h-code à cause des taux de collisions qui sont non déterministes);

  3. il n'est pas demandé d'effectuer d'autres opérations que la recherche, sur les données une fois structurées. En effet il est impossible de trier le tableau de h-code en déplaçant les valeurs (d'autres solutions existent mais elles sont moins efficaces, telles que le tri par pointeurs sans déplacer les données).

  A noter que si l'on désire pouvoir supprimer des éléments du tableau en cours de traitement, un algorithme de traitement de collisions par chaînage externe est préférable car plus efficace.

14. Structures à support mixte

Table des matières.

Site Hosting: Bronco