Hash consing

En informatique, le partage maximale, ou hash consing est une technique utilisée pour économiser de la mémoire, ou plus rarement du temps de calcul. Il s'agit, lorsqu'une structure de données est créé, de vérifier si une structure de donnée égale se trouve déjà en mémoire. Si c'est le cas, on réutilise cette même structure au lieu d'en créer une nouvelle.

Cela nécessite que la structure de donnée ne puisse pas être modifiée, en effet, si la structure est modifiable, alors la modification s'appliqueraient à toutes les instance de cette structure, et non pas simplement à l'instance qu'on voulait modifier.

Grâce à cette méthode, si deux structures sont égale, elles seront à la même position en mémoire, pour tester l'égalité, il suffira donc de comparer deux pointeurs. On peut aussi rajouter un tag unique pour chaque structure, le calcul du tag étant fait par le hash-consing. Si le terme est nouveau, c'est le plus grand des tags augmenté de un, sinon puisqu'on rend la structure existant en mémoire, le tag aura déjà la bonne valeur. Il suffira alors de comparer l'égalité sur les tags, or l'égalité sur des pointeurs ou des entiers est rapide. Enfin, la comparaison des tag permet de créer un ordre sur les structures, le plus petit tag appartenant à la première structure créée.

En pratique, pour utiliser le hash-consing, on crée une valeur, la hashe, on recherche une valeur égale dans une table de hashage, et on utilise cette valeur. Si on ne la trouve pas, alors on rajoute la valeur à la table de hashage. Il peut être bon d'utiliser une table de hashage à pointeur faible pour éviter de perdre de la mémoire avec des structures devenues inutiles.

Une autre manière de gagner du temps de calcul avec le hash-consing consiste à utiliser les structure pour mémoiser. Pour chaque fonction f pouvant utiliser la structure, on rajoute un champ mutable f à la structure s, au départ initialisé à une valeur dummy (ou nulle), la première fois qu'on veut f(s), on fait le calcul, et on stocke le résultat à la place de la valeur dummy. De cette manière chaque structures égales partagera le résultat, et on évite les cout de créer une table de hashage pour chaque fonction mémoisée.

Pour que cela fonctionne, il est indispensable que le teste d'égalité, et le hashage, ne tienne pas compte de la valeur stocké dans f.

Cette idée est similaire au design pattern poids mouche

Footnotes

Liens externes

1. (en) Allen, John, Anatomy of Lisp, McGraw Hill, 1978 
2. Ershov, A.P., « On programming of arithmetic operations », dans Communications of the ACM, vol. 1, n^o 8, 1958, p. 3–6 
3. «  ».
4. «  ».

• Portail de l’informatique