Module: Hachage

En plus des séquences, vous pouvez également hacher des ensembles. C'est-à-dire des ensembles d'objets sans ordre. Il est calculé selon la formule suivante :
hachage(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- tout compter modulo
où ord est une fonction qui attribue à un objet de l'ensemble son nombre ordinal absolu parmi tous les objets possibles (par exemple, si les objets sont des nombres naturels, alors ord(x) = x, et si des lettres latines minuscules, alors ord(& #39;a' ;) = 1, ord('b') = 2 etc.)

C'est-à-dire que pour chaque objet on associe une valeur égale à la base à la puissance du nombre de cet objet et on additionne toutes ces valeurs afin d'obtenir un hachage de l'ensemble entier. Comme il ressort clairement de la formule, le hachage est facilement recalculé si un élément est ajouté ou supprimé de l'ensemble (il suffit d'ajouter ou de soustraire la valeur requise). Même logique,  si ce ne sont pas des éléments uniques qui sont ajoutés ou supprimés, mais d'autres ensembles (il suffit d'ajouter/soustraire leur hachage).

Comme vous pouvez déjà le comprendre, les éléments simples sont considérés comme des ensembles de taille 1, pour lesquels nous pouvons calculer le hachage. Et les ensembles plus grands ne sont qu'une union de ces ensembles uniques, où en combinant des ensembles, nous ajoutons leurs hachages.

En fait, c'est toujours le même hachage polynomial, mais avant le coefficient à p^m  nous avions la valeur de l'élément de séquence sous le numéro n - m - 1 (où n est la longueur de la séquence), et maintenant c'est le nombre d'éléments dans l'ensemble dont le nombre ordinal absolu est égal à m.

Dans un tel hachage, il faut prendre une base suffisamment grande (supérieure à la taille maximale de l'ensemble), ou utiliser un double hachage pour éviter les situations où un ensemble de p objets de nombre ordinal absolu m a le même hachage qu'un ensemble à un objet avec un nombre ordinal absolu m+1.