java LinkedHashSet

Question

I've been studying for OCJP (former SCJP) and I came across the following example which uses LinkedHashSet:

public class Test{

    int size;

    public Test(int s){
       this.size = s;
    }

    @Override
    public boolean equals(Object obj) {
         return (this.size == ((Test)obj).size);
    }

    public static void main(String[] args) {
      LinkedHashSet<Test> s = new LinkedHashSet<Test>();
      s.add(new Test(1));
      s.add(new Test(2));
      s.add(new Test(1));
      System.out.println(s.size());
    }
}

Now, the question is what is displayed if :
1) implementation stays as is
2) override of hashCode is inserted in the class Test as follows:

public int hashCode() {return size/5};

Running and compiling the code states that the size of set in the first case is 3, while in the second it is 2. Why?

In case 1, although equals method is overriden, it is never invoked. Does that mean that add() method does not check for object equality if hashCode method is not overriden?
In case 2, hashCode with the given implementation and the give set of Test objects always returns the same number. How is that different from the default hashCode implementation, and why does it cause equals to be invoked?

Striking

Answer 1

If you don't override hashCode(), then each of your instances will have hashcode calculated from some pre-defined Hashing algorithm in Object class. So, all your instances will possibly have different hashcode values (This is not for sure though). Means, each instance will go into its own bucket.

Now, even if you overridden equals() method make two instances equal based on some attribute, their hashcodes are still different.

So, two instances with a different hashcodes, can never be equal. So the size of the set is 3. Since it does not have any duplicate.

---

But, when you override hashCode() with following implementation: -

public int hashCode() {return size/5};

It will return same value for same size. So the instances with same value of size will have same hashcodes and also, since you have compared them in equals method on the basis of size, so they will be equal and hence they will be considered duplicate in your Set and hence will be removed.So, Set.size() is 2.

Moral: - You should always override hashCode() whenever you override equals() method, to maintain the general contract between the two methods.

General contract between hashcode and equals method: -

• When two objects are equal, their hashcode must be equal
• When two objects are not equal, their hashcode can be equal
• The hashCode algorithm should always generate same value for same object.
• If hashCode for two objects are different, they will not be equal
• Always use same attributes to calculate hashCode that you used to compare the two instances

Strongly suggested to read at least once: -

• Effective Java - Item#9: Always override hashCode when you override equals

Condyloma

So, simplified, when default hashCode implementation is used, every object is in its own "bucket". Since there is only one object in the bucket, there is nothing to compare it with, so it is just added to a collection? I think I'm starting to get it. – Striking

@Maggie. I suggest you to read that last link I gave. That gives the best explanation about this topic. – Condyloma

Yes, yes, I have that book also, and I think I read it a while ago, but this collection / generics topic just gives me too much headache. Thank you anyway. – Striking

@Maggie. You're welcome. And don't let that book lost in some dark room. That's worth reading 10 times. – Condyloma

Answer 2

Hashing structures rely on hashing algorithm which is represented by hashCode() in java. When you put something into a HashMap (or LinkedHashSet in your case), jvm invokes hashCode() on the objects that are being inserted into this structure. When it is not overriden, default hashCode() from Object class will be used and it is way inefficient -- all the objects get into their own buckets.

When you override the hashCode() the way that is shown in your example, all of objects in your example will get into the same bucket. And then (when adding them one after another), be compared with equals(). That's why in the first case (when equals() is not called) you get size of 3, and in the second -- 2.

Rather