Easy to Learn Java: Programming Articles, Examples and Tips

Start with Java in a few days with Java Lessons or Lectures

Home

Code Examples

Java Tools

More Java Tools!

Java Forum

All Java Tips

Books

Submit News
Search the site here...
Search...
 
Search the JavaFAQ.nu
1000 Java Tips ebook

1000 Java Tips - Click here for the high resolution copy!1000 Java Tips - Click here for the high resolution copy!

Java Screensaver, take it here

Free "1000 Java Tips" eBook is here! It is huge collection of big and small Java programming articles and tips. Please take your copy here.

Take your copy of free "Java Technology Screensaver"!.

I defined an equals method, but Hashtable ignores it. Why?

JavaFAQ Home » Java IAQ by Peter Norvig Go to all tips in Java IAQ by Peter Norvig


Bookmark and Share

Q: I defined an equals method, but Hashtable ignores it. Why?

Answer: equals methods are surprisngly hard to get right. Here are the places to look first for a problem:
  1. You defined the wrong equals method. For example, you wrote:

    public class C {
      public boolean equals(C that) { return id(this) == id(that); }
    }

    But in order for table.get(c) to work you need to make the equals method take an Object as the argument, not a C:

    public class C {
      public boolean equals(Object that) { 
        return (that instanceof C) && id(this) == id((C)that); 
      } 
    }

    Why? The code for Hashtable.get looks something like this:

    public class Hashtable {
      public Object get(Object key) {
        Object entry;
        ...
        if (entry.equals(key)) ...
      }
    }

    Now the method invoked by entry.equals(key) depends upon the actual run-time type of the object referenced by entry, and the declared, compile-time type of the variable key. So when you as a user call table.get(new C(...)), this looks in class C for the equals method with argument of type Object. If you happen to have defined an equals method with argument of type C, that's irrelevent. It ignores that method, and looks for a method with signature equals(Object), eventually finding Object.equals(Object). If you want to over-ride a method, you need to match argument types exactly. In some cases, you may want to have two methods, so that you don't pay the overhead of casting when you know you have an object of the right class:

    public class C {
      public boolean equals(Object that) {
        return (this == that) 
                || ((that instanceof C) && this.equals((C)that)); 
      }
    
      public boolean equals(C that) { 
        return id(this) == id(that); // Or whatever is appropriate for class C
      } 
    }
    

  2. You didn't properly implement equals as an equality predicate: equals must be symmetric, transitive, and reflexive. Symmetric means a.equals(b) must have the same value as b.equals(a). (This is the one most people mess up.) Transitive means that if a.equals(b) and b.equals(c) then a.equals(c) must be true. Reflexive means that a.equals(a) must be true, and is the reason for the (this == that) test above (it's also often good practice to include this because of efficiency reasons: testing for == is faster than looking at all the slots of an object, and to partially break the recursion problem on objects that might have circular pointer chains).
  3. You forgot the hashCode method. Anytime you define a equals method, you should also define a hashCode method. You must make sure that two equal objects have the same hashCode, and if you want better hashtable performance, you should try to make most non-equal objects have different hashCodes. Some classes cache the hash code in a private slot of an object, so that it need be computed only once. If that is the case then you will probably save time in equals if you include a line that says if (this.hashSlot != that.hashSlot) return false.
  4. You didn't handle inheritance properly. First of all, consider if two objects of different class can be equal. Before you say "NO! Of course not!" consider a class Rectangle with width and height fields, and a Box class, which has the above two fields plus depth. Is a Box with depth == 0 equal to the equivalent Rectangle? You might want to say yes. If you are dealing with a non-final class, then it is possible that your class might be subclassed, and you will want to be a good citizen with respect to your subclass. In particular, you will want to allow an extender of your class C to use your C.equals method using super as follows:

    public class C2 extends C {
    
      int newField = 0;
    
      public boolean equals(Object that) {
        if (this == that) return true;
        else if (!(that instanceof C2)) return false;
        else return this.newField == ((C2)that).newField) && super.equals(that);
      }
    
    } 

    To allow this to work, you have to be careful about how you treat classes in your definition of C.equals. For example, check for that instanceof C rather than that.getClass() == C.class. See the previous IAQ question to learn why. Use this.getClass() == that.getClass() if you are sure that two objects must be of the same class to be considered equals.

  5. You didn't handle circular references properly. Consider:

    public class LinkedList {
    
      Object contents;
      LinkedList next = null;
    
      public boolean equals(Object that) {
        return (this == that) 
          || ((that instanceof LinkedList) && this.equals((LinkedList)that)); 
      }
    
      public boolean equals(LinkedList that) { // Buggy!
       return Util.equals(this.contents, that.contents) &&
              Util.equals(this.next, that.next); 
      }
    
    } 

    Here I have assumed there is a Util class with:

      public static boolean equals(Object x, Object y) {
        return (x == y) || (x != null && x.equals(y));
      } 

    I wish this method were in Object; without it you always have to throw in tests against null. Anyway, the LinkedList.equals method will never return if asked to compare two LinkedLists with circular references in them (a pointer from one element of the linked list back to another element). See the description of the Common Lisp function list-length for an explanation of how to handle this problem in linear time with only two words of extra storge. (I don't give the answer here in case you want to try to figure it out for yourself first.)

This tip is reprinted on JavaFAQ.nu by by courtesy of Peter Norvig I am thankful for his important contributions to my site - 21 Infrequently Answered Java Questions. Alexandre Patchine


 Printer Friendly Page  Printer Friendly Page
 Send to a Friend  Send to a Friend

.. Bookmark and Share

Search here again if you need more info!
Custom Search



Home Code Examples Java Forum All Java Tips Books Submit News, Code... Search... Offshore Software Tech Doodling

RSS feed Java FAQ RSS feed Java FAQ News     

    RSS feed Java Forums RSS feed Java Forums

All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest 1999-2006 by Java FAQs Daily Tips.

Interactive software released under GNU GPL, Code Credits, Privacy Policy