What's the best way to represent sets that support the following two operations:
- Insert(s, i) - adds nonnegative integer i to set s
- Equal(s1, s2) - Tests if s1 and s2 are the same set.
In addition, I have an upper bound on the integers added to each set. That is, I know $N$ such that $0 \le i < N$.
I'm also willing to accept that Equal is only approximate. ie Equal(s1,s2) could be true even if s1 != s2. I guess in that case I'm looking for a hash function. Does anyone know a good hash function?
We can assume that an integer is only inserted once into a set. $N$ can be about 3-5 million, and the number of sets I want to test for equality can be in the thousands.