Introduction

Une fonction de hachage est une fonction au sens informatique du terme, qui convertit un élément quelconque (un entier, un fichier, un objet représentant une personne) en une valeur. Cette valeur est souvent représentée par un nombre ou une chaîne de caractères.

Toute fonction de hachage respecte deux propriétés:

1. Une fonction de hachage, appliquée à plusieurs reprises au même élément, donne toujours le même résultat. Autrement dit, une fonction de hachage est déterministe. Comme elle n’a normalement pas d’effet de bord, elle est également dite pure. En conséquence, si deux résultats de l’application d’une fonction de hachage sont différents, alors les éléments sur lesquels la fonction s’est appliquée sont, eux aussi, différent.
2. Une bonne fonction de hachage, lorsqu’elle est appliquée à deux éléments différents, a de bonnes chances de produire des résultats différents.

Puisque, en général, il existe une infinité d’éléments potentiels différents mais que le résultat de la fonction est limité à une valeur d’un type défini (par exemple, un nombre entier), il existe forcément plusieurs éléments fournissant la même valeur de hachage. On cherche alors à créer des fonctions de hachage de qualité, selon des critères variables, mais généralement avec la volonté de faire en sorte que deux éléments différents produisent très souvent des résultats différents.

Pour les éléments les plus simples (nombres, fichiers, etc.), les outils informatiques proposent des fonctions de hachage prêtes à l’emploi: on indique l’élément, on choisit une fonction au sein d’une bibliothèque logicielle, et le résultat est obtenu de manière triviale. Lorsqu’on souhaite considérer des éléments plus complexes, les choses se corsent.

Hachage d’éléments composite

Partons du hachage d’un fichier. Supposons que nous ayons une fonction h capable de hacher un fichier, résumant son contenu en un nombre.

h("/bspringsteen/waiting-on-a-sunny-day.mp3") -> 123456
h("/bspringsteen/buffalo-gals.mp3") -> 987654
h("/bspringsteen/pay-me-my-money-down.mp3") -> 753258

On voudrait hacher tout le répertoire « /bspringsteen », par exemple pour s’assurer que son contenu ne change pas au cours du temps: si un seul fichier était ajouté, supprimé, ou modifié même légèrement, le hachage du répertoire devrait changer radicalement.

La solution la plus simple consiste à convertir chaque élément en son hachage, puis d’appliquer une opération de composition sur ces valeurs. Si on a + une telle opération de composition, on peut dire que

h("/bspringsteen") = h("/bspringsteen/waiting-on-a-sunny-day.mp3") + h("/bspringsteen/buffalo-gals.mp3") + h("/bspringsteen/pay-me-my-money-down.mp3")

On veut pouvoir hacher une collection d’éléments, par exemple des fichiers, de sorte que le résultat ne dépend pas de l’ordre dans lequel on présente les éléments. Autrement dit, on souhaite que l’opération de composition de hachage soit commutative. Concaténer les éléments à hacher n’est typiquement pas une solution, car, la plupart des fonctions de hachage fournies transforment un flux de données au fur et à mesure de sa lecture, et mettent progressivement à jour un état qui fournira le hachage du flux.

Une solution classique consiste à trier les fichiers, de sorte que les hachages se produisent toujours dans le même ordre. Ainsi, même si l’opération de composition n’est en elle-même pas commutative, le résultat sera insensible à l’ordre des fichiers.

Cependant, cette approche ne présente pas que des avantages. Tout d’abord, elle nécessite de conserver en mémoire la liste de tous les fichiers impliqués dans le hachage. Lorsque le répertoire contient des milliers voire des millions de fichiers, cela devient non négligeable. Le tri de ces fichiers a également un coût en temps de calcul. La mémorisation et le tri de l’ensemble des fichiers doivent se faire avant que le hachage ne commence. Cela empêche un hachage en flux, ce qui retarde le début de ce traitement.

Lorsqu’aucun ordre naturel n’existe pour les éléments considérés, la notion de tri elle-même est problématique. On peut s’en remettre à un identifiant unique et ordonnable de l’élément, mais celui-ci doit être connu de tous les systèmes souhaitant comparer les collections, ce qui nécessite typiquement leur communication. Le hachage de l’élément peut faire office d’identifiant: on calcule dans un premier temps le hachage de chaque élément, puis on ordonne ces hachages selon leur ordre naturel afin de les composer.

Un opérateur de composition commutatif et associatif

Un opérateur de composition des hachages est le OU exclusif (souvent noté ⊕) appliqué sur chaque paire de bits de deux valeurs de hachage. Cet opérateur fournit le même résultat si les deux valeurs de hachage sont échangées. En d’autres termes, le OU exclusif est commutatif.

0 ⊕ 0 = 0
1 ⊕ 0 = 0 ⊕ 1 = 1
1 ⊕ 1 = 0

L’ordre dans lequel on considère les fichiers n’a ainsi plus d’importance: étant donné un hachage partiel, il suffit de lui appliquer un OU exclusif avec le hachage du fichier suivant pour obtenir un nouvel hachage partiel, et de poursuivre de la sorte jusqu’à avoir considéré l’ensemble des fichiers.

Il n’est alors plus nécessaire de trier les fichiers avant de les traiter, ce qui réduit la latence, le temps d’exécution et les besoins en mémoire du traitement. Le principal inconvénient de cette approche est qu’elle augmente légèrement le risque de collision, c’est-à-dire d’obtenir la même valeur de hachage pour deux répertoires différents. Elle n’est pas cryptographiquement sûre, car il est facile de créer un répertoire fournissant une valeur de hachage arbitraire.

Petit bonus: le OU exclusif, en plus d’être commutatif, est associatif:

(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

Cela signifie qu’il est possible de distribuer le calcul du hachage de sous-ensemble de fichiers, puis de concaténer les résultats intermédiaires obtenus afin d’obtenir le hachage du répertoire entier. Cela est particulièrement intéressant lorsque les sous-ensembles de fichiers sont situés sur des points de montage différents du système de fichiers, voire sont physiquement présents sur des systèmes distincts: on peut ainsi solliciter chaque sous-système pour calculer une partie du hachage, et ne communiquer que les valeurs de hachage intermédiaires pour calculer le hachage final. Cela s’avère rapidement plus efficace que la récupération des fichiers eux-mêmes pour un traitement local.

Cet avantage est très recherché en programmation distribuée, car il permet de réordonnancer des traitements sans conséquence sur le résultat final. C’est une des raisons pour lesquelles la programmation fonctionnelle et son usage des monades (qui comprennent un opérateur associatif) est populaire dans ce milieu.

Au-delà de la comparaison stricte

Les valeurs de hachage permettent de vérifier si le contenu de deux ensembles d’éléments (deux répertoires, par exemple) ont un contenu identique. La réponse n’est pas très nuancée: c’est identique, ou différent. Il est parfois souhaitable d’avoir une réponse plus nuancée, par exemple en déterminant le pourcentage d’éléments communs, ou en précisant le nombre d’éléments d’un ensemble qu’on ne retrouve pas dans l’autre.

Une première approche pourrait consister à convertir chaque élément à sa valeur de hachage et à travailler sur ces valeurs. Malheureusement, cela fonctionne assez mal pour les grands ensembles: imaginez par exemple devoir comparer deux listes de milliers voire de millions de nombres entiers, cherchant à déterminer si un nombre d’une liste se retrouve dans l’autre.

Une approche probabiliste peut s’avérer utile.

L’algorithme HyperLogLog convertit un ensemble d’éléments en une structure de données de faible taille. Chaque élément est converti en un ensemble de valeurs de hachage, et chaque valeur vient altérer un registre qui agrège les valeurs reçues. La structure de données, qui est constituées des différents registres utilisés, peut être utilisée pour estimer le nombre d’éléments (distincts) qui sont venus altérer les registres. En comparant les structures HyperLogLog de deux ensembles, il est possible d’estimer précisément et efficacement (mais pas exactement) le nombre de leurs éléments communs et différents.

Application dans un contexte médical

Lors d’un projet passé, j’ai eu l’occasion d’exploiter de telles structures afin de permettre la comparaison de cohortes de patients sans risque de compromission de leur identité.

Supposez qu’un hôpital possède une liste de ses patients atteints d’un cancer du poumon. Par ailleurs, un autre hôpital possède une liste de ses patients traités pour un problème de diabète. On souhaiterait déterminer si les patients de ces deux listes se recoupent, par exemple pour étudier une possible interaction entre le cancer du poumon et le diabète (ou leurs traitements respectifs). Évidemment, aucun hôpital ne veut ni ne peut divulguer sa liste de patients, au mieux pourrait-il contacter un patient appartenant aux deux listes pour lui proposer de participer à une étude.

En transformant chaque patient en une valeur de hachage, il est possible de construire une structure HyperLogLog pour chacune des listes des hôpitaux. On peut ainsi déterminer si l’intersection de deux listes (ou davantage) est suffisamment importante que pour justifier une étude des patients qui s’y trouvent, sans rien connaître des patients eux-mêmes.

Il n’est pas possible de déterminer les éléments qui constituent l’intersection de deux structures HypeLogLog. Cela nécessite une communication plus lourde autres les hôpitaux concernés. Notre approche basée sur des structures HyperLogLog permet néanmoins de déterminer systématiquement les situations pour lesquelles des hôpitaux pourraient envisager une étude conjointe.