Empreinte digitale pour les ensembles dynamiques

Existe-t-il une structure de données de mots-RAM de w bits avec O (1) temps par opération pour le problème suivant?: Maintenir un ensemble d'entiers non négatifs de w bits qui prend en charge les opérations

add (x): ajoutez x à l'ensemble
remove (x): supprime x de l'ensemble
fingerprint (): retourne une empreinte digitale de l'ensemble. Cette empreinte numérique w-bit a la propriété que deux ensembles identiques ont la même empreinte digitale tandis que deux ensembles différents ont probablement des empreintes digitales différentes

Toutes les opérations doivent s'exécuter en temps constant.

F (S) = (\sum_{X \in S} 2^{X}) mod p

$f(S) = \left(\sum_{x\in S} 2^x\right) \bmod p$

2^{X} mod p

$2^x \bmod p$

ds.data-structures Pat Morin
la source

Je vois qu'une question similaire a déjà été publiée ici , mais aucune solution à temps constant n'a été donnée.

Pat Morin

Réponses:

Cette réponse est un peu vague.

Sélectionnez une fonction uniformément au hasard dans l'ensemble de toutes les fonctions, des mots w-bit aux mots w-bit. Pour chaque ensemble, conservez une empreinte digitale w-bit comme suit: $h$

L'ensemble vide a l'empreinte digitale 0.
ajouter (x) et supprimer (x) mettre à jour une empreinte digitale à , où est xor. $f$ $f \oplus h(x)$ $\oplus$

Soit deux ensembles d'entiers w bits. Si leurs empreintes digitales sont les mêmes, alors l'empreinte digitale de , la différence symétrique de et , est 0, ce qui se produit avec la probabilité . $S \neq T$ $S \triangle T$ $S$ $T$ $2^{-w}$

jbapple
la source

h

$h$