Existe-t-il une fonction de hachage pour une collection (c'est-à-dire plusieurs ensembles) d'entiers présentant de bonnes garanties théoriques?

36

Je suis curieux de savoir s'il existe un moyen de stocker un hachage d'un ensemble multiple d'entiers possédant les propriétés suivantes, idéalement:

  1. Il utilise O (1) espace
  2. Il peut être mis à jour pour refléter une insertion ou une suppression dans le temps O (1)
  3. Deux collections identiques (c.-à-d. Des collections contenant les mêmes éléments avec les mêmes multiplicités) doivent toujours avoir la même valeur et deux collections distinctes doivent avoir des valeurs différentes avec une probabilité élevée (c.-à-d. Que la fonction est indépendante ou indépendante par paire).

Une première tentative consisterait à stocker le produit modulo de manière aléatoire au sein des hachages des éléments individuels. Cela satisfait 1 et 2, mais il n'est pas clair si cela, ou une variante proche, satisferait 3.

J'ai initialement posté ceci sur StackOverflow .

* Les propriétés 1 et 2 pourraient être légèrement assouplies, par exemple, sur O (log n) ou sur un petit polynôme sous-linéaire. Le but est de voir si nous pouvons identifier plusieurs ensembles et tester de manière fiable l’égalité sans stocker les éléments eux-mêmes.

Jonderry
la source
Quelle est votre représentation des multisets? Comment coder un multiset en tant que chaîne de bits? Si vous voulez vraiment obtenir des opérations de temps (indépendamment de la taille du multiset), je pense que vous devriez rendre l'encodage explicite. O(1)
Jukka Suomela
Le codage des ensembles n'a pas d'importance. La fonction de hachage doit être indépendante de la représentation des ensembles. Si j'utilisais une représentation canonique d'un ensemble de hachage, alors tout hachage standard sur la représentation en bits de l'ensemble satisferait 3 et probablement 1, mais pas 2. J'ajouterais que deux collections égales doivent toujours avoir la même valeur de hachage.
jeudi
Qu'entendez-vous exactement par 2? Obtenez-vous l'ancien jeu, l'ancien code de hachage et le nouvel élément et souhaitez-vous calculer le nouveau code de hachage? Ou obtenez-vous uniquement l'ancien code de hachage et le nouvel élément?
Mihai
Idéalement, vous n'auriez pas besoin de l'ancien jeu. Vous n'avez même pas besoin de pouvoir effectuer de requêtes sur les membres (important, compte tenu des limites d'espace), mais simplement de tester l'égalité, probablement en comparant les valeurs de hachage présentant une faible probabilité de résultat faussement positif.
Jonderry

Réponses:

17

Si vous pensez que des ensembles vivent dans l’univers , il est assez facile de résoudre votre problème avec le temps de mise à jour de . Tout ce dont vous avez besoin est une fonction de hachage rapide pour un vecteur de nombres , avec des "mises à jour locales" rapides.[u]O(lgu)u

Le hachage de Wikipedia / Universal suggère , où est un nombre premier suffisant et est uniformément tiré de . Lorsque vous ajoutez ou supprimez l'élément , vous devez ajouter / soustraire du code de hachage, ce qui prend un temps utilisant divide and conquer pour l'exponentiation. Puisqu'un polynôme de degré ne peut avoir que des racines , la probabilité de collision pour deux ensembles distincts est de . Ceci peut être rendu très petit en prenant comme assez grand (par exemple,h(x)=(i=1uxiai)modppa[p]iaiO(lgi)uuO(u/p)pp=u2et vous travaillez en "double précision"). Si les ensembles sont beaucoup plus petits que , vous pouvez bien sûr commencer par réduire l'univers à un univers plus petit.[u]

Est-ce que quelqu'un connaît une solution avec une probabilité de collision lors d'un hachage allant de ? Cela devrait être possible.O(1/p)[p]

Mihai
la source
0

Carter et Wegman couvrent cela dans New hash functions (Fonctions de hachage) et leur utilisation dans l'authentification et définissent l'égalité ; c'est très similaire à ce que vous décrivez. Une fonction de hachage commutative peut être mise à jour élément par élément pour les insertions et les suppressions, et les correspondances à haute probabilité, dans O (1).

KWillets
la source
Je pense que cela ne fonctionne que sur les ensembles, pas multisets (comme la question posée). Dans la section 5, au bas de la page 274: "AJOUTER (x, S) - Ajoute l'élément x à l'ensemble nommé S. Cette opération ne peut pas être utilisée si x est déjà membre de S."
Jbapple
Tu as raison; J'ai raté la partie "multi". Il semble probable qu'une fonction de hachage puisse gérer les doublons, bien que je ne la cite pas.
KWillets
-2

La qualité d’une fonction de hachage dépendra toujours des propriétés des éléments qu’elle doit hacher. Pouvez-vous dire quelque chose à ce sujet? Par exemple, votre suggestion de produit est probablement une mauvaise fonction de hachage si les éléments x_i de votre multiset ont généralement de nombreux petits facteurs premiers. Mais vous pouvez l’améliorer dans ce cas en prenant simplement le produit de tous les x_i + p mod q pour certains nombres premiers p et q.

TonyK
la source
1
Oui, c’est la raison pour laquelle nous prenons le hash des éléments individuels avant de les multiplier ensemble.
Jonderry
Quelle? La suggestion du PO est simplement de les multiplier tous ensemble, n'est-ce pas? Je dis que si vous ajoutez une constante à chacun avant de faire cela, vous obtiendrez probablement un meilleur hash.
TonyK
-5
A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1 
N = size of set before addition/removal<P>
Add X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U+X)&M)<<16) + ((V^X)&M)
H *= A
H += N+1

Remove X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U-X)&M)<<16) + ((V^X)&M)
H *= A
H += N-1

la somme nous permet d'avoir plusieurs occurrences de la même valeur
le xor nous permet d'avoir des ensembles qui totalisent le même montant

Louis Reinitz
la source