This question is very similar to this unanswered one http://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.