Vivek,
If you access the source code of class HashSet, you'll notice that a HashSet uses an array to store its elements. Here's the array used to store the elements of a HashSet (copied from Java source code):
Class Entry is a static class, which stores the elements of a HashSet.
Understand the sequence of events that occur, when you create a HashSet and add elements to it:
1)
When you create a HashSet 'set' using the preceding command, it creats an array 'table' with an initial capacity, 8 (because you didn't specify an initial capacity).
2)
Execution of preceding command, results in multiple steps:
i) Retrieve hashCode value of object a1:
'set' retrieves the hashCode value of object 'a1' by calling its 'hashCode' method. Because class 'Animal' doesn't override the 'hashCode' method, 'set' calls the 'hashCode' method, defined by class 'Object'. The 'hashCode' method defined by class 'Object' returns distinct integers for distinct objects. This is typically implemented by converting the internal address of the object into an integer.
Let's assume that 'a1.hashCode()' returns a value '75432'.
ii) Calculate array position (or bucket) to store element:
'set' determines the array position (also referred to as a 'bucket') in which it can store object 'a1'. It does so by calling a method 'indexFor', which accepts 'hashCode' and array size and returns an array position. Here's the code of this method:
Let's assume that indexFor(75432, 8) method returns value 4. So, object 'a1' is stored at array position 4, in 'set'.
3)
When you execute the preceding code, the same set of steps execute as the ones that are outlined for addition of object 'a1' to 'set'.
Because 'a1.hashCode()' and 'a2.hashCode()' will return different hashCode values, they are not considered equal objects and so 'a2' WILL be added to 'set'. Note that 'equals' method hasn't been called yet.
Let's assume that a2.hashCode() returns 53168 and indexFor(53168, 8) returns a value 1. In this case, a2 will be added to array position 1 in 'set'.
Let's consider another case - What happen's if indexFor(53168, 8) returns value 4? As mentioned in step (2), a1 is already stored at position 4. In this case, 'set' will now compare the hashCode value of the entry already storted at position 4 (that is 'a1') with the new entry, that is, a2. Because these value differ, 'a2' will also be stored at arry position 4, 'chained' to object 'a1'. Chaining is a technique, in which you can make an object refer to another object (I didn't disclose the contents of class 'Entry'. It includes a variable to store HashSet element and another variable to store a reference to another 'Entry' object. You can access its complete code using Java source code)
Did you notice that because the hashCode values of objects 'a1' and 'a2' didn't match, its 'equals' method was never called!! You can add a 'System.out.println' line to your 'equals' method to
test whether it is called in your example.
The equals method is called by HashSet, if the hashCode values of two objects match. In this case, HashSet queries the equals method to determine whether two objects are 'equal' or not, before adding them to it.
Hope this clears all your doubts about how an element is added to a HashSet.
With respect,
Mala