• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

HashSet -- adding a new element concept not clear

 
Ranch Hand
Posts: 33
Eclipse IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


As per Java API, the method -- public boolean add(E e)
"Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false."

Here as per the overridden equals method a1.equals(a2) is true, so a2 should not be added in this HashSet, but it is adding the duplicate element. Why so?
 
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Vivek,

I hope you are aware of equality contract of objects in Java (popularly known as hashCode-equals contract).

I can see that your Animal class does not override hashCode method.
 
Vivek Raj
Ranch Hand
Posts: 33
Eclipse IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
yes I know about the hashCode-equals contract, that if two objects are equal their hashCode must also be equal.

But I am still not clear how the equals and hashCode work while adding the element in a HashSet (or any other collection using hashCode).
 
Anayonkar Shivalkar
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, you can find the explanation in any decent Java book.

But to cut long story short - the objects with same hashCode are stored in same 'bucket'.

Now, during equality, first, collection framework method ('add' in this case) tries to identify if the objects belong to same bucket. If yes, then it will further check if those objects are really equal (by calling equals method).

In your case, you have not overridden hashCode method. Thus, add method will call hashCode method of Object class. Now, if that method returns different hashCode (and mostly it does) for a1 and a2, then from add method's perspective, those objects belong to two different buckets, and hence cannot be equal.

Thus, add method allows to add another object to set.

I hope this helps.
 
Greenhorn
Posts: 29
Mac Java ME Chrome
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hey Vivek Raj ,
i juste want tell you part in the book K&B page 563

When using HashSet or LinkedHashSet, the objects you add to them
must override hashCode(). If they don't override hashCode(), the default Object.
hashCode() method will allow multiple objects that you might consider "meaningfully
equal" to be added to your "no duplicates allowed" set.



so like anayonkar say

In your case, you have not overridden hashCode method. Thus, add method will call hashCode method of Object class. Now, if that method returns different hashCode (and mostly it does) for a1 and a2, then from add method's perspective, those objects belong to two different buckets, and hence cannot be equal.

 
Author
Posts: 375
22
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Vivek Raj
Ranch Hand
Posts: 33
Eclipse IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you Mala.
This has clarified my doubts. I tried overriding both the hashCode() and equals() method from Object class and put SOP statement in both the methods.
I also tried same for TreesSet and put SOP in compareTo().

 
LOOK! OVER THERE! (yoink) your tiny ad is now my tiny ad.
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic