Partage maximal

En informatique, le partage maximal, 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éée, 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'appliquerait à toutes les instances de cette structure, et non pas simplement à l'instance qu'on voulait modifier.

Grâce à cette méthode, si deux structures sont égales, 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 prend la structure existante 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 tags 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 puis on recherche une valeur égale dans une table de hachage. Le cas échéant, on utilise cette valeur. Si on ne la trouve pas, alors on rajoute la valeur à la table de hachage. Il peut être bon d'utiliser une table de hachage à pointeurs faibles 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 structures 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 structure égale partagera le résultat, et on évite les coûts de création d'une table de hachage pour chaque fonction mémoisée.

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

Cette idée est similaire au design pattern poids mouche.

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