This is a very old (and nice) problem in streaming algorithms. The solution currently used in most places is HyperLogLog[1], which basically uses the distribution of log(minimum value of hash) for a set of hashes.

[1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf