Sorry I am new here and learning mathematics and cryptographic problems.
Assume an hash algorithm is collision resistant like SHA256, and the hash value is 64bit in length, (2^{64} possibilities)
Now there is known 20k different hashes.
A brute-force cracker can generate 1e9 hashes per second.
How many days will the cracker have 50% change to hit at least 1 of the 20k hashes? What will be the formula or code to calculate?
Suppose there are N different possible hash outputs. Then the probability of a particular hash colliding with k known outputs is k/N. The probability that it will not collide is therefore (1-k/N). If you have n hashes, the probability that none will collide with one of the k known outputs is (1-k/N)^n. For large N, that can be approximated with e^-(kn/N). So if you want a probability of .5, you have
e^-(kn/N) = .5
kn/N = -ln(.5)
n = -N ln(.5)/k
ln(.5) ~= -0.693, so you have 0.693(N/k). Plugging in N = 2^64, k = 20,000 yields n = 6.3931543 * 10^14. Divide that by 10^9/second, and that's 6.3931543 * 10^5, or 639315.43 seconds, or about 178 hours, or about 7.399 days.
So every week or so, the probability of not having a collision decreases by a factor of 2: after one week, there's a 50% chance of no collisions, after two weeks, 25%, after three weeks 12.5%, etc.