why collection uses hashcode ?

[ankur rathi]

Why collections ( some ) uses hashcode to search the object .

 
 _________
| k1 | v1 |
| k2 | v2 |
|_k3_|_v3_|
 

where k1,k2,k3,v1,v2 & v3 are the reference variable that are refering corresponding objects in GCH . so my question is why they uses hashcode for searching purpose and why not equals() method .

like k4.equals(k1) then give value v1 to k4 .... where hashcode came in between ?

i hope question is clear .
please help .
thanks .

[Steven Bell]

This question is actually fairly involved. It has to do with performance when working with large collections.

Lets say you have 10,000 Objects and you want to search for one. If you keep them sorted you can do a binary search and find them fairly fast, but that means every time you insert an object you have to find it's position and all the objects have to have some sort of order.

The way hash collections work is they perform a math function on the hashcode to map it to an index. Now when you go to look for that object again the same math function is performed and you only need to look at one spot for the object. At this point equals() is called to check if it is the right object.

This is why it is so important to always override equals and hashcode in data Objects or Objects that may be used as a key in a hashMap or may be put into a hash collection. Also equals() and hashcode() should be consistent meaning that if equals() returns true the hashcode() method should return the same value.