This question is very similar to this unanswered one https://math.stackexchange.com/questions/242607/estimate-number-of-distinct-items .

Suppose I have a large array of $n$ integers and I want to estimate how many distinct integers it contains. I can sample uniformly from the positions of the array (with replacement) and suppose the true number of distinct integers is $N$ . I would like to do as few samples as possible. What is the best way to get an estimate for $N$?

This appears to be closely related to the problem of estimating species richness, but having looked at as much literature as I could (being a non-expert) I didn't see a perfect fit.