Home | JSP | EJB | JDBC | Java Servlets | WAP  | Free JSP Hosting  | Spring Framework | Web Services | BioInformatics | Java Server Faces | Jboss 3.0 tutorial | Hibernate 3.0 | XML

Tutorial Categories: Ajax | Articles | JSP | Bioinformatics | Database | Free Books | Hibernate | J2EE | J2ME | Java | JavaScript | JDBC | JMS | Linux | MS Technology | PHP | RMI | Web-Services | Servlets | Struts | UML


 

Search Host

Monthly Fee($)
Disk Space (MB)
Register With us for Newsletter!
Visit Forum! Post Questions!
Jobs At RoseIndia.net!

Have tutorials?
Add your tutorial to our Java Resource and get tons of hits.

We offer free hosting for your tutorials. and exposure for thousands of readers. drop a mail
roseindia_net@yahoo.com
 
   

Tutorials

Java Server Pages

JAXB

Java Beans

JDBC

MySQL

Java Servlets

Struts

Bioinformatics

Java Code Examples

Interview Questions

 
Join For Newsletter

Powered by groups.yahoo.com
Visit Group! Post Questions!

Web Promotion

Web Submission

Submit Sites

Manual Submission?

Web Promotion Guide

Hosting Companies

Web Hosting Guide

Web Hosting

Linux

Beginner Guide to Linux Server

Frameworks

Persistence Framework

Web Frameworks

Free EAI Tools

Web Servers

Aspect Oriented Programming

Free Proxy Servers

Softwares

Adware & Spyware Remover

Open Source Softwares

Strategy Pattern of HashCode Equality
   

       

 

2005-05-18 The Java Specialists' Newsletter [Issue 109] - Strategy Pattern of HashCode Equality

Author: Dr. Heinz M. Kabutz

JDK version: Sun JDK 1.5.0_02

If you are reading this, and have not subscribed, please consider doing it now by going to our subscribe page. You can subscribe either via email or RSS.


Welcome to the 109th edition of The Java(tm) Specialists' Newsletter. A few days ago, I was sitting on a balcony in a typical little Greek village house in Western Macedonia. It was wonderfully relaxing and quiet there, a perfect place for a programmer to go. Now I am in Crete, where I will present a talk tomorrow at the University of Crete in Iraklion on the Proxy Pattern and how Java works with dynamic proxies.

Crete is a treat. Went swimming several times already, even though it is only May! The water is cool, but not nearly as cold as Cape Town. The coldest water in Cape Town I spearfished in with my big brother was 9 degrees Celsius. That was very very cold!

Here is a question for you: Would you enjoy coming to the Mediterranean Greek island of Crete to attend a Design Patterns Course (or something else, such as Java Performance Tuning)? If YES, please click on this link. If NO, please click on this link (and tell us the reason).

Strategy Pattern of HashCode Equality

A few weeks ago, we were looking at the Strategy Design Pattern, which gets far less attention than it deserves. Gerhard Radatz from Alcatel Austria, asked whether the hashCode() function is an example of the Strategy. I do not think it is, but the question triggered an idea. I have written many hashCode() and equals() functions and they usually follow the same pattern. In IntelliJ IDEA, it even autogenerates them for you. But this is dumb copy + paste code, even if it is generated, so why could we not replace that with a Strategy instead, and how would it perform?

Here is an example of IntelliJ IDEA generated equals() and hashCode() functions:

public class PersonNormal {
  private final String name;
  private final String address;
  private final int age;
  public PersonNormal(String name, String address, int age) {
    this.name = name;
    this.address = address;
    this.age = age;
  }
  public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof PersonNormal)) return false;

    final PersonNormal personNormal = (PersonNormal) o;

    if (age != personNormal.age) return false;
    if (address != null ?
        !address.equals(personNormal.address) :
        personNormal.address != null)
      return false;
    if (name != null ?
        !name.equals(personNormal.name) :
        personNormal.name != null)
      return false;
    return true;
  }
  public int hashCode() {
    int result;
    result = (name != null ? name.hashCode() : 0);
    result = 29 * result + (address != null ? address.hashCode() : 0);
    result = 29 * result + age;
    return result;
  }
}
  

We could extract these functions and put them into a Strategy interface. This would allow us to write the function once, and never again. To make a link between the strategy and its owner object, we add a setOwner method to the strategy interface:

public interface EqualityStrategy {
  /**
   * Sets the owner object of the strategy.  This will be the
   * object for which the hashCode() needs to be calculated and
   * which will be compared through equals().
   */
  void setOwner(Object o);
  /** Calculates the hashcode for the owner object. */
  int hashCode();
  /** Compares the owner object to other. */
  boolean equals(Object other);
}
  

Field Based EqualityStrategy

The first implementation of EqualityStrategy is based on calculating a hash value over the fields of the object using reflection. An improvement would be to cater for arrays as fields using the Arrays.deepHashCode() method in JDK 1.5 (or write an equivalent method yourself).

import java.lang.reflect.Field;
import java.util.*;

public class FieldEqualityStrategy implements EqualityStrategy {
  private Object obj;
  private Field[] fields;
  public void setOwner(Object obj) {
    this.obj = obj;
    // we want to filter out the strategy field!
    List fields = new ArrayList();
    Field[] tempFields = obj.getClass().getDeclaredFields();
    for (int i = 0; i < tempFields.length; i++) {
      Field field = tempFields[i];
      if (!field.getType().isAssignableFrom(getClass())) {
        field.setAccessible( true);
        fields.add(field);
      }
    }
    this.fields = new Field[fields.size()];
    fields.toArray( this.fields);
  }
  public int hashCode() {
    try {
      int hashCode = 0;
      for ( int i = 0; i < fields.length; i++) {
        Object o = fields[i].get(obj);
        // you might need to make special provisions for arrays
        hashCode = 29 * hashCode + (o == null ? 0 : o.hashCode());
      }
      return hashCode;
    } catch (IllegalAccessException e) {
      throw new SecurityException(e);
    }
  }
  public boolean equals(Object o) {
    if (o == obj) return true;
    if (!obj.getClass().isInstance(o)) return false;
    try {
      for (int i = 0; i < fields.length; i++) {
        Object val1 = fields[i].get(obj);
        Object val2 = fields[i].get(o);
        // you might need to make special provisions for arrays
        if (val1 != null ? !val1.equals(val2) : val2 != null)
          return false;
      }
    } catch (IllegalAccessException e) {
      throw new SecurityException(e);
    }
    return true;
  }
}
  

I will introduce the performance values as we go along:

Equality Function Speed (ms)
Plain equals() 170
Plain hashCode() 251
FieldEqualityStrategy equals() 1482
FieldEqualityStrategy hashCode() 3285

We see that the field based equality strategy is 8.7x slower for equals() and 13x slower for hashCode(). This seems like a wasteful approach.

Value Based EqualityStrategy

Another approach is to let the strategy ask the owner for the field values. This way, we can avoid the runtime overhead of reflection. This only works with JDK 1.5, due to the new java.util.Arrays.deepHashCode() function. To use these with JDK 1.4, just write your own deepHashCode() and deepEquals() methods.

import java.util.Arrays;

public class ValueBasedEqualityStrategy
    implements EqualityStrategy {
  private ValueSupplier supplier;
  public void setOwner(Object o) {
    if (!(o instanceof ValueSupplier)) {
      throw new IllegalArgumentException();
    }
    this.supplier = (ValueSupplier) o;
  }
  public int hashCode() {
    return Arrays.deepHashCode(supplier.getValues());
  }
  public boolean equals(Object o) {
    if (o == supplier) return true;
    if (!supplier.getClass().isInstance(o)) return false;
    Object[] values1 = supplier.getValues();
    Object[] values2 = ((ValueSupplier) o).getValues();
    return Arrays.deepEquals(values1, values2);
  }
  public interface ValueSupplier {
    Object[] getValues();
  }
}
  

The performance values are a bit better with this approach:

Equality Function Speed (ms)
Plain equals() 170
Plain hashCode() 251
ValueBasedEqualityStrategy equals() 1051
ValueBasedEqualityStrategy hashCode() 1733

Cached Hash Code Values

In some rare circumstances, it pays to cache the hashCode() inside the strategy. Usually this does not give you a gain because you often just calculate the hashCode() once for an object. In this CachedEqualityStrategy, the hashCode() result is remembered inside the Strategy. Be careful with caching hash codes, often the microbenchmarks are not a true reflection of real program performance. Note that the equals() method still delegates the decision to the individual strategies. However, in this equals() method we first compare the hash codes (which would probably be cached already). This gives us an extra performance benefit.

public class cachedequalitystrategy
    implements equalitystrategy {
  private int hashcode = 0;
  private final equalitystrategy strat;
  public cachedequalitystrategy(equalitystrategy strat) {
    this.strat = strat;
  }
  public int hashcode() {
    if (hashcode == 0) {
      hashcode = strat.hashcode();
    }
    return hashcode;
  }
  public boolean equals(object obj) {
    return obj != null && (hashcode() == obj.hashcode())
      && strat.equals(obj);
  }
  public void setowner(object o) {
    strat.setowner(o);
    hashcode = 0;
  }
}
  

We see the performance of the microbenchmark improve, but as mentioned before, this is probably not a true reflection of real life:

Equality Function Speed (ms)
cached Plain equals() 170
cached Plain hashCode() 251
cached FieldEqualityStrategy equals() 450
cached FieldEqualityStrategy hashCode() 161
cached ValueBasedEqualityStrategy equals() 300
cached ValueBasedEqualityStrategy hashCode() 150

Null Equality Strategy

A nice pattern, based on the Strategy Pattern, is the Null Object Pattern. This defines an object that implements what would happen if there was no strategy. For example:

public class NullEqualityStrategy implements EqualityStrategy {
  private Object owner;
  public void setOwner(Object owner) {
    this.owner = owner;
  }
  public int hashCode() {
    return System.identityHashCode(owner);
  }
  public boolean equals(Object obj) {
    return owner == obj;
  }
}
  

New Person Class with EqualityStrategy

This new Person class contains everything that we need for the various strategies. Note that we do not need to write the actual code of the hashcode and equals methods anymore. Note also that I have implemented the ValueSupplier interface which will only be necessary for the ValueBasedEqualityStrategy. This currently returns a new Object[] every time it is called, which could be optimised further. However, I did not detect much difference in performance when I cached the Object[] in the Person class. However, the cost of creating lots of objects is not felt during the construction phase, but during garbage collection.

public class PersonWithStrategy
    implements ValueBasedEqualityStrategy.ValueSupplier {
  private final String name;
  private final String address;
  private final int age;
  private final EqualityStrategy strategy;
  public PersonWithStrategy(String name, String address,
                            int age, EqualityStrategy strategy) {
    this.name = name;
    this.address = address;
    this.age = age;
    this.strategy = strategy;
    this.strategy.setOwner(this);
  }
  /** This is an example of a constructor that uses a
      NullEqualityStrategy as default. */
  public PersonWithStrategy(String name, String address, int age) {
    this(name, address, age, new NullEqualityStrategy());
  }
  public int hashCode() {
    return strategy.hashCode();
  }
  public boolean equals(Object obj) {
    return strategy.equals(obj);
  }
  public Object[] getValues() {
    return new Object[]{name, address, age};
  }
}
  

For completeness, here is the performance class, which also shows how to use the strategy objects:

import java.util.Arrays;

public class PerfTest {
  public static void main(String[] args) {
    PersonNormal[] ppl = {
      new PersonNormal("Heinz Kabutz", "no", 33),
      new PersonNormal(new String("Heinz Kabutz"), "no", 33),
      new PersonNormal("Znieh", "no", 33),
      new PersonNormal(null, "no", 33),
      new PersonNormal("Heinz", null, 33),
      new PersonNormal("Heinz", "no", 0),
      null,
    };
    boolean[][] check = compare("Plain", ppl);

    PersonWithStrategy[] ppl2 = {
      new PersonWithStrategy("Heinz Kabutz", "no", 33,
          new FieldEqualityStrategy()),
      new PersonWithStrategy(new String("Heinz Kabutz"),
          "no", 33, new FieldEqualityStrategy()),
      new PersonWithStrategy("Znieh", "no", 33,
          new FieldEqualityStrategy()),
      new PersonWithStrategy(null, "no", 33,
          new FieldEqualityStrategy()),
      new PersonWithStrategy("Heinz", null, 33,
          new FieldEqualityStrategy()),
      new PersonWithStrategy("Heinz", "no", 0,
          new FieldEqualityStrategy()),
      null,
    };
    boolean[][] fieldCheck = compare("FieldEqualityStrategy",
        ppl2);
    check(check, fieldCheck);

    PersonWithStrategy[] ppl3 = {
      new PersonWithStrategy("Heinz Kabutz", "no", 33,
          new CachedEqualityStrategy(
              new FieldEqualityStrategy())),
      new PersonWithStrategy(new String("Heinz Kabutz"), "no", 33,
          new CachedEqualityStrategy(
              new FieldEqualityStrategy())),
      new PersonWithStrategy("Znieh", "no", 33,
          new CachedEqualityStrategy(
              new FieldEqualityStrategy())),
      new PersonWithStrategy(null, "no", 33,
          new CachedEqualityStrategy(
              new FieldEqualityStrategy())),
      new PersonWithStrategy("Heinz", null, 33,
          new CachedEqualityStrategy(
              new FieldEqualityStrategy())),
      new PersonWithStrategy("Heinz", "no", 0,
          new CachedEqualityStrategy(
              new FieldEqualityStrategy())),
      null,
    };
    boolean[][] cachedFieldCheck = compare(
        "cached FieldEqualityStrategy", ppl3);
    check(check, cachedFieldCheck);

    PersonWithStrategy[] ppl4 = {
      new PersonWithStrategy("Heinz Kabutz", "no", 33,
          new ValueBasedEqualityStrategy()),
      new PersonWithStrategy(new String("Heinz Kabutz"), "no", 33,
          new ValueBasedEqualityStrategy()),
      new PersonWithStrategy("Znieh", "no", 33,
          new ValueBasedEqualityStrategy()),
      new PersonWithStrategy(null, "no", 33,
          new ValueBasedEqualityStrategy()),
      new PersonWithStrategy("Heinz", null, 33,
          new ValueBasedEqualityStrategy()),
      new PersonWithStrategy("Heinz", "no", 0,
          new ValueBasedEqualityStrategy()),
      null,
    };
    boolean[][] varArgsCheck = compare(
        "ValueBasedEqualityStrategy", ppl4);
    check(check, varArgsCheck);

    PersonWithStrategy[] ppl5 = {
      new PersonWithStrategy("Heinz Kabutz", "no", 33,
          new CachedEqualityStrategy(
              new ValueBasedEqualityStrategy())),
      new PersonWithStrategy(new String("Heinz Kabutz"), "no", 33,
          new CachedEqualityStrategy(
              new ValueBasedEqualityStrategy())),
      new PersonWithStrategy("Znieh", "no", 33,
          new CachedEqualityStrategy(
              new ValueBasedEqualityStrategy())),
      new PersonWithStrategy(null, "no", 33,
          new CachedEqualityStrategy(
              new ValueBasedEqualityStrategy())),
      new PersonWithStrategy("Heinz", null, 33,
          new CachedEqualityStrategy(
              new ValueBasedEqualityStrategy())),
      new PersonWithStrategy("Heinz", "no", 0,
          new CachedEqualityStrategy(
              new ValueBasedEqualityStrategy())),
      null,
    };
    boolean[][] cachedVarArgsCheck = compare(
        "cached ValueBasedEqualityStrategy", ppl5);
    check(check, cachedVarArgsCheck);

    PersonWithStrategy[] ppl6 = {
      new PersonWithStrategy("Heinz Kabutz", "no", 33),
      new PersonWithStrategy(new String("Heinz Kabutz"), "no", 33),
      new PersonWithStrategy("Znieh", "no", 33),
      new PersonWithStrategy(null, "no", 33),
      new PersonWithStrategy("Heinz", null, 33),
      new PersonWithStrategy("Heinz", "no", 0),
      null,
    };
    compare("NullEqualityStrategy", ppl6);
  }

  private static boolean[][] compare(String strategy,
                                     Object[] ppl) {
    // first check correctness
    boolean[][] result = new boolean[ppl.length][ppl.length];
    for (int i = 0; i < ppl.length; i++) {
      for (int j = 0; j < ppl.length; j++) {
        if (ppl[i] != null) {
          result[i][j] = ppl[i].equals(ppl[j]);
        }
      }
    }
    // now check performance
    long time = System.currentTimeMillis();
    for (int k = 0; k < 100 * 1000; k++) {
      for (int i = 0; i < ppl.length; i++) {
        for (int j = 0; j < ppl.length; j++) {
          if (ppl[i] != null) ppl[i].equals(ppl[j]);
        }
      }
    }
    time = System.currentTimeMillis() - time;
    System.out.println(strategy + " equals() " + time + "ms");

    time = System.currentTimeMillis();
    for (int k = 0; k < 1000 * 1000; k++) {
      for (int i = 0; i < ppl.length; i++) {
        if (ppl[i] != null) ppl[i].hashCode();
      }
    }
    time = System.currentTimeMillis() - time;
    System.out.println(strategy + " hashCode() " + time + "ms");
    return result;
  }

  private static void check(boolean[][] check,
                            boolean[][] fieldCheck) {
    if (!Arrays.deepEquals(check, fieldCheck)) {
      System.out.println(
          "check = " + Arrays.deepToString(check));
      System.out.println(
          "other = " + Arrays.deepToString(fieldCheck));
      throw new RuntimeException();
    }
  }
}
  

All things considered, I will probably stick with my IntelliJ autogenerated hashCode() and equals() since they are faster and less complicated. This is one of the drawbacks with this pattern - the client code needs to know that there are different strategies, and has to choose the correct one consistently.

Kind regards

Heinz

This material from The Java(tm) Specialists' Newsletter by Maximum Solutions (South Africa). Please contact Maximum Solutions for more information.

       

Useful Links
  JDO Tutorials
  EAI Articles
  Struts Tutorials
  Java Tutorials
  Java Certification
Tell A Friend
Your Friend Name
Search Tutorials

 

 
Browse all Java Tutorials
Java JSP Struts Servlets Hibernate XML
Ajax JDBC EJB MySQL JavaScript JSF
Maven2 Tutorial JEE5 Tutorial Java Threading Tutorial Photoshop Tutorials Linux Technology
Technology Revolutions Eclipse Spring Tutorial Bioinformatics Tutorials Tools SQL
 

Home | JSP | EJB | JDBC | Java Servlets | WAP  | Free JSP Hosting  | Search Engine | News Archive | Jboss 3.0 tutorial | Free Linux CD's | Forum | Blogs

About Us | Advertising On RoseIndia.net

Send your comments, Suggestions or Queries regarding this site at roseindia_net@yahoo.com.

Copyright 2007. All rights reserved.