Finding a collision probability in a hashmap

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%!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s