When two unequal objects have the same hash value, this causes a collision in the hash table, because both objects want to be in the same slot (sometimes called a bucket). The hash algorithm must resolve such collisions. Reaching back into fading memories of my college algorithms course, I remember three basic ways of doing this:
1. Look for the next empty slot in the hash table and put the object there. Pros: easy to implement, cons: can lead to clustering of objects and degrade performance, capacity may be exceeded
2. Have a secondary hash function to use when there's a conflict: Pros: usually fast, cons: must write a second hash function and may still get collisions, and capacity may be exceeded
3. Make a linked-list of objects from the conflicted slot of the hash table. Pros/cons: usually fast for decent hash function and load factors, but can degrade to linear search in worst case
I think the
Java hash classes use the third method, but they might use a combination approach. The key to good hashing though is to make sure the hash table has a big enough capacity and to write good hash functions. A hash table that only has as many buckets as objects it is holding will probably have conflicts. Usually you want the hash table to be about twice as big as the number of objects it stores. Java's HashMap will grow as needed, but you can give it a starting capacity and load factor if you want.
The hash function is up to the programmer. You could just return 0 for all objects, but that will mean the hashing (both storage and retrieval) will become O(n) instead of O(1) ... or in lay terms, it will be dog slow.