Without looking at all the data, how can I test whether a collection only contains unique objects? I have collection of data objects distributed across multiple machines. An O(n) lookup is not feasible, so I will need to sample. Is there an algorithm that I can use (preferably one that can relate sampling size to margin of error)?
Context: I am using Modin. The data is rows in pandas Dataframes and are just int types. Nothing is known about the underlying structure of these ints however (prior to sampling).

To expand Stephan's comment about the probability of detecting the duplicate, suppose there are $N$ objects with exactly 1 pair of duplicate values and the rest are unique. We propose taking a sample of $n$ objects and checking if any of the $n$ objects are duplicates. How large does $n$ have to be to give a $X\%$ chance of detecting the duplicates in $N$?
There are $N\choose n$ possible samples of size $n$ we can take, and ${N-2}\choose{n-2}$ of those possible samples will contain the two duplicates. (First choose the 2 duplicates, then choose the other $n-2$ values from the remaining $N-2$ in the population.)
The probability that a randomly selected sample contains both duplicates is
$$
\frac{N-2\choose n-2}{N\choose n} = \frac{n(n-1)}{N(N-1)}
$$
For a given $N$ and desired probability $X$, we can find the value of $n$ such that
$$
\frac{n(n-1)}{N(N-1)} > X\%
$$
Eg, suppose $N = 100$ and we want the probability of detecting duplicates to be at least 95%. Then we find $n$ such that
$$
\frac{n(n-1)}{100*99} > 0.95
$$
Giving $n > 97.48$. Therefore to have at least a 95% chance of detecting the duplicates, we need to sample at least 98 out of the 100 objects.
For $N = 100000$, we find $n \geq 97468$.
This is such a small improvement over checking all objects that it's probably not worth doing, although if you're willing to tolerate a lower chance of detecting the duplicates the required sample size does decrease.
