109Strategy Pattern of HashCode Equality

Author: Dr. Heinz M. KabutzDate: 2005-05-18Java Version: 5Category: Language

Abstract: Instead of auto-generating our hashCode() and equals() methods, why not use the strategy pattern to do this for us? In this newsletter, we examine different approaches and their benefits.

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!

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

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 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:

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 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:

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:

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

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive