Partage maximal
# Partage maximal

En programmation informatique, le partage maximal, ou hash consing, est une technique utilisée pour économiser de la mémoire et du temps de calcul. Dans un programme qui manipule des structures de données que l'on ne cherche pas à déconstruire, mais seulement à comparer entre elles, la partage maximal fonctionne ainsi : lorsqu'une structure de données est créée, on vérifie si une structure de donnée identique 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. D'autre part, on associe à chaque structure un nombre unique (hachage) qui permet de ramener la comparaison des deux structures à la comparaison de deux nombres, ce qui est beaucoup plus économique que la comparaison récursive de deux structures.

## Explications détaillées

Cela nécessite que la structure de donnée ne puisse pas être modifiée ; on parle alors de structure de données immutable.

Le hash consing attache à chaque structure une valeur de hachage qui est un nombre associé de façon unique. Si deux structures sont égales, elles auront la même valeur de hachage. Pour tester l'égalité, il suffira donc de comparer deux nombres.

En pratique, pour utiliser le hash consing, on crée une valeur puis on recherche une valeur égale dans une table de hachage. Si la valeur existe dans la table, c'est que la structure a déjà été créée et on utilise cette valeur. Si on ne la trouve pas, alors on ajoute la valeur à la table de hachage.

On peut aussi gagner du temps de calcul avec le hash consing en utilisant les valeurs de hachage pour mémoïser.

