1. A method of estimating deduplication potential, comprising: identifying duplicates of fingerprints of a sampling portion of a data set occupying at least a portion of a storage space; for each unique fingerprint for the sampling portion, recording a duplicate counter number in a fingerprint data store, wherein the duplicate counter number indicates a number of data blocks in the sampling portion all of which have that unique fingerprint; for each duplicate counter number in the fingerprint data store, changing that duplicate counter number to a common clamp value if that duplicate counter number is larger than the common clamp value; determining a sampling count of the identified duplicates of fingerprints in the sampling portion, by summing the duplicate counter numbers in the fingerprint data store; determining, by a processor, a data set count of duplicates of fingerprints in the data set depending on the sampling count of the identified duplicates of fingerprints in the sampling portion, based on a probability of fingerprints from the data set colliding in the sampling portion; and estimating, by the processor, a potential saving of the storage space occupied by the data set from a data deduplication, based on the determined data set count of duplicates of fingerprints in the data set.