# why we can't avoid hash collision in practice ?

Edward Chen

Ranch Hand

Posts: 798

Mike Simmons

Ranch Hand

Posts: 3080

14

posted 5 years ago

Well, sometimes you can avoid it, and sometimes you can't. What if the key is a String? How many different possible Strings are there that might go into a Map? Hint: it's a really, really big number. The hashCode() must be an int however. How many different possible ints are there? Hint: Integer.MAX_VALUE is a big number, but much much smaller than the previous big number. Therefore, out of all possible Strings, some Strings must have the same hashCode() - no matter

*how*you choose to calculate hashCode(). This leads to the possibility of hash collisions.
posted 5 years ago

Mike already explained the reason.

Let's have a look at String objects that consist of exactly 10 letters of the alphabet (A-Z). How many different strings are possible? The answer is: 26^10 = 141.167.095.653.376 different strings.

The hash code of an object is a 32-bit integer. So, how many different hash codes are possible? 2^32 = 4.294.967.296 different hash codes.

You see that there are many more possible strings than there are hash codes. Therefore, there must be different strings that have the same hash code.

Let's have a look at String objects that consist of exactly 10 letters of the alphabet (A-Z). How many different strings are possible? The answer is: 26^10 = 141.167.095.653.376 different strings.

The hash code of an object is a 32-bit integer. So, how many different hash codes are possible? 2^32 = 4.294.967.296 different hash codes.

You see that there are many more possible strings than there are hash codes. Therefore, there must be different strings that have the same hash code.