Efficient set data structure supporting insert and set equal
Let $F$ be a finite field with efficient procedures for addition and

multiplication and almost-uniform sampling. $\:$ Let $z$ be a field element.

(I use that letter because things will be slightly more convenient if $z$ is

the zero element, although efficient sampling means that even if one

can't find the zero of $F\hspace{-0.03 in}$, one should still be able to find a field element.)

To initialize the data structure, sample a field element $x$.

Empty sets are represented by $z$, Insert(s,i) adds $x^i$ to the representation of s,

and Equal(s1,s2) just tests if the two representing field elements are equal.

Since addition is associative and commutative, there are no false negatives. $\:$ If each integer is only inserted once into a set, then the probability of there being at least one false positive is at most

the distance from $x$'s distribution to uniform $\;+\;$ $((N\cdot \text{number of equality tests})\hspace{.02 in}/($$\hspace{-0.03 in}\operatorname{card}$$(F\hspace{.03 in})) \;\;$.

To efficiently compute $x^i\hspace{-0.04 in}$, see this paper, and either avoid the methods that involve negative

powers or make slightly stronger assumptions on $F$. $\:$ I would recommend 5.1 on page 14.