Let’s assume that we have a HashMap with initial size = 65536. How many random elements should we put into a HashMap to get the first collision?
The formula for calculating the average value of such elements is 1.25 * sqrt (N).
What’s the answer? 1.25 * 256 = 320. This means that average count of elements for this map for which the first collision occurs is 320. Which is just 0.4%!