Fingerprinting for dynamic sets
This answer is a bit hand-wavey.

Select a function $h$ uniformly at random from the set of all functions from w-bit words to w-bit words. For each set, maintain a w-bit fingerprint as follows:


The empty set has the fingerprint 0.
add(x) and remove(x) update a fingerprint $f$ to $f \oplus h(x)$, where $\oplus$ is xor.


Let $S \neq T$ be two sets of w-bit integers. If their fingerprints are the same, then the fingerprint of $S \triangle T$, the symmetric difference of $S$ and $T$, is 0, which happens with probability $2^{-w}$.