Steven Levine
Steven Levine
1 min read

Tags

What happens if two different object hash to the same hashcode and then are placed in a HashMap?

If two keys hash to the same hashCode, or to the same hashCode modulo the size of the table, all still works. It just takes a little longer to look up that key, since get() has to chase a chain of clashing keys to find the match. Keys are matched with the equals() method, not ==, or simply by comparing hashCodes.

Let me repeat this another way. Collisions happen not only when two of the HashCodes are identical, (quite infrequent) but when two of the Hashcodes modulo the initial capacity are equal (which almost always happens at least a few times). Collisions are unavoidable. The Hashtable class deals with them automatically. They slow down lookup, but do not derail it. The smaller the load factor, the more RAM you waste, but the fewer the collisions, so the faster the lookup. Using prime numbers for the divisor/capacity also tends to reduce collisions.

HashCodes are usually not unique. If you think about it, how could they be? Consider Strings of length 10 characters (20 bytes, 160 bits). How many different possible strings are there? 2\^160. HashCodes are only 32 bits long. How many possible different hashCodes are there? 2\^32. You can see there are way more strings that HashCodes, so strings would have to share HashCodes.