Minborg

Minborg
Minborg

Monday, December 15, 2014

Java 8, BYO Super Efficient Maps! Quadruple Your Map Performance

Background

Maps are used ubiquitously in almost all Java applications. There are several built-in implementations of the Map interface tailored for different purposes. All these Map implementations rely on calculating a hash value for the key, and using that hash value, we are able to put or get objects from a backing array. But sometimes we know more about the keys than that they are just Objects. In this post I will show how you can take advantage of that fact to write super-fast and super-efficient Map implementations. The implementation devised here is really nothing more than an offsetted array decorated with the Map interface methods. Since it does not have to deal with hashing, rehashing and hash collision, it is unsurprising that it is so fast. Its potential memory efficiency is however, something to elaborate on.

Performance

When comparing one of the Map implementation depicted in this post (namely the IntArrayMap) we will see that it is substantially more memory efficient than any other of the built-in Map implementation.

           HashMap   5470 MB     54 bytes per entry 
           TreeMap   5599 MB     55 bytes per entry
     LinkedHashMap   6271 MB     62 bytes per entry 
 ConcurrentHashMap   5471 MB     54 bytes per entry 
       IntArrayMap    400 MB      4 bytes per entry

(Bytes per entry is excluding size of value object itself.)

Applying the same comparative test but for get() method performance, we will also be able to conclude that the IntArrayMap is much faster than the other Maps.

           HashMap    44864 ms,   111 MTPS
           TreeMap   364277 ms,    13 MTPS
     LinkedHashMap    74616 ms,    67 MTPS
 ConcurrentHashMap    62002 ms,    80 MTPS
       IntArrayMap(*) 29635 ms,   168 MTPS
       IntArrayMap(**) 9520 ms,   525 MTPS

All tests are made using a JIT warmup of 5 000 000 000 iterations and then an additional 5 000 000 000 iterations for actual testing.

So the IntArrayMap is potentially ten times more memory efficient and more than four times quicker than any other built-in Map.

IntArrayMap(*) using the get(Object) method.
IntArrayMap(**) using the get(int) method.

Restrictions

In this post, the keys in the Map implementations must be an Object that extends Number, for example Integer, Long or Byte. The Object must not be able to hold any decimals (excluding the classes Double, Float, BigInteger and BigDecimal). Furthermore the key space must be known in advance. This might first appear as an unacceptable restriction and I agree that this certainly is the case for many applications. However, there are, more often than one might think, times when we know the key space in advance. For example, when dealing with Enums or other static mappings or smaller dynamic maps. A final restriction in the solutions provided in this post is that the key set must be within the range of Integer.

Overall Solution

Because the key space is know, the solutions can rely on direct mapping of the key onto an array that holds the values. So, when we create a Map, we also provide the minBound and maxBound index we want to use. If we, for example, create a Map with key space (10-14) we will create an array with 5 elements (maxBound-minBound+1) and when we get() from that map, we will take the key, subtract it with 10 (the minBound) and then get the value in that array position. The solution is related to the way EnumMap works.

Benefits


  • Much more memory efficient because the key is not stored in the Map. It is instead derived implicitly from the index.
  • Deterministic behavior since we do not have to re-hash when the Map is too small and needs to be grown.
  • Faster put() and get() operations because no hash code needs to be computed.
  • Reduced object creation rate (no boxing/un-boxing) because the put() and get() methods can work directly with primitive classes (e.g. int instead of Integer)


Drawbacks


  • Static key space that must be decided upon before map creation.
  • Keys must extend Number.
  • Less memory efficient for sparse maps (i.e. maps with few entries in the key space).
  • Key space must be within Integer range.
  • The Map implementations does not support null values.


Base Number Array Map

This is how the overall abstract base class NumberArrayMap looks like (yes, I know it it a big class. There are many things a Map has to do):

public abstract class NumberArrayMap<K extends Number, V> extends AbstractMap<K, V> implements Map<K, V>, Serializable {

    private static final long serialVersionUID = -2304239764179123L;

    private int minBound;
    private int maxBound;
    //
    private transient int size;
    private transient int modCount;
    private transient int capacity;
    private transient V[] values;

    private transient Set<Map.Entry<K, V>> entrySet;

    protected NumberArrayMap(int minBound, int maxBound) {
        if (minBound > maxBound) {
            throw new IllegalArgumentException("Error: minBound (" + minBound + ") must not be greater than maxBound (" + maxBound + ")");
        }
        this.minBound = minBound;
        this.maxBound = maxBound;
        init();
    }

    private void init() {
        initCapacity();
        clear();
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        if (key instanceof Number) {
            return containsKey(((Number) key).intValue());
        }
        return false;
    }

    public boolean containsKey(int key) {
        return isInRange(key) && values[index(key)] != null;
    }

    @Override
    public boolean containsValue(Object value) {
        for (final V v : values) {
            if (v != null && v.equals(value)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public V get(Object key) {
        if ((key instanceof Number)) {
            return get(((Number) key).intValue());
        }
        return null;
    }

    public V get(int key) {
        if (isInRange(key)) {
            return values[index(key)];
        }
        return null;
    }

    @Override
    public V put(K key, V value) {
        return put(key.intValue(), value);
    }

    public V put(int key, V value) {
        assertInRange(key);
        Objects.requireNonNull(value, "This Map does not support null values");
        final V oldValue = get(key);
        if (oldValue == null) {
            // A new value, increment size
            size++;
        }
        values[index(key)] = value;
        modCount++;
        return oldValue;
    }

    @Override
    public V remove(Object key) {
        if (key instanceof Number) {
            return remove(((Number) key).intValue());
        }
        return null;
    }

    public V remove(int key) {
        final V oldValue = get(key);
        if (oldValue != null) {
            // An existing value, decrement size
            size--;
        }
        values[index(key)] = null;
        modCount++;
        return oldValue;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (final Entry<? extends K, ? extends V> e : m.entrySet()) {
            put(e.getKey(), e.getValue());
        }
    }

    @Override
    public void clear() {
        @SuppressWarnings("unchecked")
        final V[] newValues = (V[]) new Object[capacity];
        this.values = newValues;
        size = 0;
        modCount++;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        Set<Entry<K, V>> es;
        return (es = entrySet) == null ? (entrySet = new NumberArrayMap<K, V>.EntrySet()) : es;
    }

    final class EntrySet extends AbstractSet<Map.Entry<K, V>> {

        @Override
        public final int size() {
            return size;
        }

        @Override
        public final void clear() {
            NumberArrayMap.this.clear();
        }

        @Override
        public final Iterator<Map.Entry<K, V>> iterator() {
            return new NumberArrayMap<K, V>.EntryIterator();
        }

        @Override
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry)) {
                return false;
            }
            final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
            final Object key = e.getKey();
            final V valueCandidate = get(key);
            return valueCandidate != null && valueCandidate.equals(e.getValue());
        }

        @Override
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                final Object key = e.getKey();
                final V valueCandidate = get(key);
                if (valueCandidate != null && valueCandidate.equals(e.getValue())) {
                    return NumberArrayMap.this.remove(key) != null;
                }
            }
            return false;
        }

        @Override
        public final void forEach(Consumer<? super Map.Entry<K, V>> action) {
            Objects.requireNonNull(action);
            if (size > 0) {
                int mc = modCount;
                for (int i = minBound; i <= maxBound; ++i) {
                    final V value = get(i);
                    if (value != null) {
                        action.accept(makeEntry(makeKeyFromInt(i), value));
                    }
                    if (modCount != mc) {
                        throw new ConcurrentModificationException();
                    }
                }
            }
        }
    }

    private abstract class BucketIterator<N> implements Iterator<N> {

        private Entry<K, V> next;
        private Entry<K, V> current;
        private int expectedModCount;
        private int currentIndex;

        public BucketIterator() {
            expectedModCount = modCount;
            currentIndex = 0;
            if (size > 0) {
                // advance to first entry
                forwardToNext(minBound);
            }
        }

        @Override
        public final boolean hasNext() {
            return next != null;
        }

        public final Entry<K, V> nextEntry() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (next == null) {
                throw new NoSuchElementException();
            }
            current = next;
            forwardToNext(currentIndex + 1);
            return current;
        }

        @Override
        public final void remove() {
            final Entry<K, V> p = current;
            if (p == null) {
                throw new IllegalStateException();
            }
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            current = null;
            final K key = p.getKey();
            NumberArrayMap.this.remove(key);
            expectedModCount = modCount;
        }

        private void forwardToNext(int start) {
            if (start <= maxBound) {
                for (int i = start; i <= maxBound; ++i) {
                    final V value = get(i);
                    if (value != null) {
                        currentIndex = i;
                        next = makeEntry(makeKeyFromInt(i), value);
                        return;
                    }
                }
            }
            // We have reached the end...
            next = null;
        }

    }

    final class KeyIterator extends BucketIterator<K> {

        @Override
        public final K next() {
            return nextEntry().getKey();
        }
    }

    final class ValueIterator extends BucketIterator<V> {

        @Override
        public final V next() {
            return nextEntry().getValue();
        }
    }

    final class EntryIterator extends BucketIterator<Map.Entry<K, V>> {

        @Override
        public final Map.Entry<K, V> next() {
            return nextEntry();
        }
    }

    protected abstract K makeKeyFromInt(int k);

    private Entry<K, V> makeEntry(K key, V value) {
        return new AbstractMap.SimpleImmutableEntry<>(key, value);
    }

    private int index(int key) {
        return key - minBound;
    }

    private boolean isInRange(int key) {
        return (key >= minBound && key <= maxBound);
    }

    private void assertInRange(int key) {
        if (!isInRange(key)) {
            throw new ArrayIndexOutOfBoundsException("Key " + key + " out of range. Key shoud be >= " + minBound + " and <= " + maxBound);
        }
    }

    private void initCapacity() {
        this.capacity = maxBound - minBound + 1;
    }

    private void writeObject(java.io.ObjectOutputStream s) throws IOException {
        s.defaultWriteObject();
        s.writeInt(minBound);
        s.writeInt(maxBound);
        s.writeInt(size);
        for (final Entry<K, V> e : entrySet()) {
            final V value = e.getValue();
            if (value != null) {
                s.writeObject(e.getKey());
                s.writeObject(e.getValue());
            }
        }
    }

    private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
        s.defaultReadObject();
        minBound = s.readInt();
        maxBound = s.readInt();
        init();
        final int noItems = s.readInt();
        if (noItems < 0) {
            throw new InvalidObjectException("Illegal noItems count: " + noItems);
        }
        if (noItems > 0) {
            // Read the keys and values, and put the mappings in the NumberMap
            for (int i = 0; i < noItems; i++) {
                @SuppressWarnings("unchecked")
                final K key = (K) s.readObject();
                @SuppressWarnings("unchecked")
                final V value = (V) s.readObject();
                put(key, value);
            }
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public Object clone() throws CloneNotSupportedException {
        NumberArrayMap<K, V> result;
        try {
            result = (NumberArrayMap<K, V>) super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.init();
        result.putAll(this);
        return result;
    }


}


All concrete implementing classes that inherit from this class must implement the K makeKeyFromInt(int k) method in order to be able to reproduce a key for any given index. This is due to the reason that we do not store the keys as the built-in Map implementations do. If, for example, the key type K is Byte, then we need to cast k to byte like this: return (byte)k;  We will see how that works in the next chapter.

It is worth noticing that the normal contains(), get(), remove() and put() methods all have corresponding methods that works directly with int as key. This is important form a performance perspective because that way, we can avoid unnecessary boxing/un-boxing of keys.

By letting our class inherit from AbstractMap we get a number of methods for free, including the hashCode(), equals() and toString() methods. We also elect to override some of the AbstractMap methods for performance reasons.



Sub Classes

Now that the abstract NumberArrayMap class is implemented, it is very easy to create concrete Map implementations for different Number classes such as Integer and Long.  Here is a list of the ones I have made:

public class ByteArrayMap<V> extends NumberArrayMap<Byte, V> {

    private static final long serialVersionUID = -2304239764179124L;
  
    public ByteArrayMap() {
        this(Byte.MIN_VALUE, Byte.MAX_VALUE);
    }

    public ByteArrayMap(byte minBound, byte maxBound) {
        super(minBound, maxBound);
    }

    @Override
    protected Byte makeKeyFromInt(int k) {
        return (byte) k;
    }

}

public class ShortArrayMap<V> extends NumberArrayMap<Short, V> {

    private static final long serialVersionUID = -2304239764179125L;
  
    public ShortArrayMap(short minBound, short maxBound) {
        super(minBound, maxBound);
    }

    @Override
    protected Short makeKeyFromInt(int k) {
        return (short)k;
    }

}


public class IntArrayMap<V> extends NumberArrayMap<Integer, V> {

    private static final long serialVersionUID = -2304239764179126L;
  
    public IntArrayMap(int minBound, int maxBound) {
        super(minBound, maxBound);
    }

    @Override
    protected Integer makeKeyFromInt(int k) {
        return k;
    }

}


public class LongArrayMap<V> extends NumberArrayMap<Long, V> {

    private static final long serialVersionUID = -2304239764179127L;

    public LongArrayMap(int minBound, int maxBound) {
        super(minBound, maxBound);
    }

    @Override
    protected Long makeKeyFromInt(int k) {
        return (long) k;
    }

}



// This class will erroneously map Numbers with equal integers (e.g. 1.2 and 1.3) to the same key
// The same goes for Double and Float, so use only integer Number implementations
@Depricated

public class BigDecimalArrayMap<V> extends NumberArrayMap<BigDecimal, V> {

    private static final long serialVersionUID = -2304239764179128L;

    public BigDecimalArrayMap(int minBound, int maxBound) {
        super(minBound, maxBound);
    }

    @Override
    protected BigDecimal makeKeyFromInt(int k) {
        return new BigDecimal(k);
    }

}



Working with Enums

Often, Enums comes with additional properties of some kind. Consider the following Enum class:

public enum SomeEnum 

    ADAM(0, 4), BERT(1, 42), CHARLIE(2, 134), SOME_DUDE(10, 13);

    private SomeEnum(int value, int luckyNumber) {
        this.value = value;
        this.luckyNumber = luckyNumber;
    }

    private final int value;
    private final int luckyNumber;
    public int getValue() {         return value;     }
    public int getLuckyNumber() {         return luckyNumber;     } }


By implementing a Map support class, we can very easily implement lookup methods (or "finders" as they sometimes are called). Here is the support class:

public class IntEnumArrayMap<E extends Enum<?>> extends IntArrayMap<E> {

    private static final long serialVersionUID = -2304239764179128L;

    public static <E extends Enum<?>> IntEnumArrayMap<E> fromEnums(E[] enums, ToIntFunction<E> function) {
        final int min = Stream.of(enums).mapToInt(function).min().getAsInt();
        final int max = Stream.of(enums).mapToInt(function).max().getAsInt();
        final IntEnumArrayMap<E> result = new IntEnumArrayMap<>(min, max);
        Stream.of(enums).forEach((e) -> result.put(function.applyAsInt(e), e));
        return result;
    }

    public IntEnumArrayMap(int minBound, int maxBound) {
        super(minBound, maxBound);
    }
}

Now we can implement our finders like this:

public enum SomeEnum {

    ADAM(0, 4), BERT(1, 42), CHARLIE(2, 134), SOME_DUDE(10, 13);

    private SomeEnum(int value, int luckyNumber) {
        this.value = value;
        this.luckyNumber = luckyNumber;
    }

    private final int value;
    private final int luckyNumber;

    private final static IntEnumArrayMap<SomeEnum> valueMap =
             IntEnumArrayMap.fromEnums(values(), SomeEnum::getValue);
    private final static IntEnumArrayMap<SomeEnum> luckyNumberMap =
             IntEnumArrayMap.fromEnums(values(), SomeEnum::getLuckyNumber);

    public static SomeEnum findByValue(int value) {
        return valueMap.get(value);
    }

    public static SomeEnum findByLuckyNumber(int value) {
        return luckyNumberMap.get(value);
    }

    public int getValue() {
        return value;
    }

    public int getLuckyNumber() {
        return luckyNumber;
    }

}

Very convenient and efficient! We know the key set of the Map we are creating so the NumberArrayMap seams like a perfect fit. Note how nice we just provide the method we want to use for mapping (e.g. SomeEnum::getValue) using Java 8's new function interface.


Future work

The implementation above relies on the inherited basic Spliterator from AbstractMap. It would be advantages to write a better Spliterator that can parallelize the entrySet(). Any one up to the challenge?

Perhaps it would be possible to create other type of Map implementations that can handle other types of key sets (i.e other than Number) that can be mapped to int. Enum is one candidate (using the ordinal() as key) but there is already an EnumMap.

Grab the source code using "git clone https://github.com/minborg/javapot.git" and expand the code and also see how I made the performance tests.

Concusion

If you know your key space, you can create much more efficient Map implementations than the built-in Java ones. Enums are a perfect place where these Map implementations can live. Static maps and small maps that are created dynamically are also a perfect match.

Let's Map the World!

Wednesday, December 10, 2014

Java 8, Initializing Maps in the Smartest Way

Background

Create maps
Illustration: Elis Minborg
When I was a kid, I was taught that, in the Swedish language, one should write out numbers using their text representation in the range from zero to twelve, otherwise one should use their number representation. For example, one should write "There are two birds and 21 flowers" (but in Swedish then of course).

In Java, we are likely to use Maps to perform such translations. The question in this post is: How does one initialize Maps in the best way? What are the alternatives and what are their pros and cons?


Objective

The objective in this post is to write a method that returns a Map with a translation from an Integer to a String. The Map shall be Unmodifiable, because we might want to reuse the Map in several places in our code and we want to be sure that is has not been tampered with. The Map shall contain the mapping pairs (or Entries as they are called in Java): 0->"zero", 1->"one", 2->"two", ... , 12->"twelve".

The Imperative Way

The straight forward solution is to declare a Map and then just put() entries into the Map. After that is done, we return an Unmodifiable view of the newly created map like this:
protected static Map<Integer, String> imperative() {
        final Map<Integer, String> numMap = new HashMap<>();
        numMap.put(0, "zero");
        numMap.put(1, "one");
        numMap.put(2, "two");
        numMap.put(3, "three");
        numMap.put(4, "four");
        numMap.put(5, "five");
        numMap.put(6, "six");
        numMap.put(7, "seven");
        numMap.put(8, "eight");
        numMap.put(9, "nine");
        numMap.put(10, "ten");
        numMap.put(11, "eleven");
        numMap.put(12, "twelve");
        return Collections.unmodifiableMap(numMap);
    }
In this solution, as opposed to the other solutions that are shown later in this post, we have to declare an intermediate result variable (numMap). We then have to reference this result variable over and over again for each put() operation , which is disturbing. There is a risk that this result variable can "leak", effectively rendering the Unmodifiable map modifiable, because the Collections.unmodifiableMap() method just provides a view of the provided Map. So if we retain a reference to the provided Map, we can still change it.

Double Brace Initialization

The Double Brace Initialization Idiom firsts appears as very appealing. In the beginning, I liked it and started to use it frequently in my code. This is how it works:
    @SuppressWarnings("serial")
    protected static Map<Integer, String> doubleBracket() {

        return Collections.unmodifiableMap(new HashMap<Integer, String>() {
            {
                put(0, "zero");
                put(1, "one");
                put(2, "two");
                put(3, "three");
                put(4, "four");
                put(5, "five");
                put(6, "six");
                put(7, "seven");
                put(8, "eight");
                put(9, "nine");
                put(10, "ten");
                put(11, "eleven");
                put(12, "twelve");
            }
        });
    }
There is actually no magic with it at all. The first pair of braces will create an anonymous class and the second pair of braces will create an instance initializer block that is run when the anonymous inner class is instantiated. In any class, you can have such brackets containing code that will be run when your create instances of your class (or when the class is used the first time, if you precede the brackets with the keyword static). This looks much better because now you do not have to create an intermediate result and you do not have to reference a variable each time you call put().

However, there are a number of snags with this scheme that is not immediately apparent. As previously stated, when you declare a class with double braces, an anonymous class will be created. Because the anonymous class is not static, it will also hold a reference (this$0) to its containing class (if defined within another class, which is the most normal case). This means that the containing instance (this$0) can not be garbage-collected as long as your Map is alive. A big concern according to my view.

Another disadvantage is that you must provide the types of the Map explicitly, because the compiler is not able to infer the types using the diamond (<>) operator. Also, the new anonymous class does not define a serialVersionUID variable, so we must suppress the resulting warning using the @SuppressWarnings("serial") annotation if you want it to compile nicely. You should really think twice before you use the Double Brace Idiom.

The Builder Pattern

This is one of my favorites and you can read more about this pattern in my previous posts "Creating Objects Using The Builder Pattern" and "The Interface Builder Pattern". The idea here is to create a Builder that has methods that returns the Builder itself again and again (like the StringBuilder does). This way the Builder can be called several time until the final build() method is called and the result is returned. I have created builders that can be used to create instance of Map and ConcurrentMap and placed them in a utility class called Maps:
public class Maps {

    private Maps() {
    }

    public static <K, V> MapBuilder<K, V> builder() {
        return builder(HashMap::new);
    }

    public static <K, V> MapBuilder<K, V> builder(Supplier<Map<K, V>> mapSupplier) {
        return new MapBuilder<>(mapSupplier.get());
    }

    public static <K, V> ConcurrentMapBuilder<K, V> concurrentBuilder() {
        return concurrentBuilder(ConcurrentHashMap::new);
    }

    public static <K, V> ConcurrentMapBuilder<K, V> concurrentBuilder(Supplier<ConcurrentMap<K, V>> mapSupplier) {
        return new ConcurrentMapBuilder<>(mapSupplier.get());
    }

    private static class BaseBuilder<M extends Map<K, V>, K, V> {

        protected final M map;

        public BaseBuilder(M map) {
            this.map = map;
        }

        public BaseBuilder<M, K, V> put(K key, V value) {
            map.put(key, value);
            return this;
        }

        public M build() {
            return map;
        }

    }

    public static class MapBuilder<K, V> extends BaseBuilder<Map<K, V>, K, V> {

        private boolean unmodifiable;

        public MapBuilder(Map<K, V> map) {
            super(map);
        }

        @Override
        public MapBuilder<K, V> put(K key, V value) {
            super.put(key, value);
            return this;
        }

        public MapBuilder<K, V> unmodifiable(boolean unmodifiable) {
            this.unmodifiable = unmodifiable;
            return this;
        }

        @Override
        public Map<K, V> build() {
            if (unmodifiable) {
                return Collections.unmodifiableMap(super.build());
            } else {
                return super.build();
            }
        }

    }

    public static class ConcurrentMapBuilder<K, V> extends BaseBuilder<ConcurrentMap<K, V>, K, V> {

        public ConcurrentMapBuilder(ConcurrentMap<K, V> map) {
            super(map);
        }

        @Override
        public ConcurrentMapBuilder<K, V> put(K key, V value) {
            super.put(key, value);
            return this;
        }

    }

}
For the sake of completeness, I have also included methods to create concurrent maps and also two builder()  methods that takes a map Provider, allowing any type of Map to be created using the Builder. Using the support methods, we can now create maps easily like this:

    protected static Map<Integer, String> builderPattern() {
        return Maps.<Integer, String>builder().
                put(0, "zero").
                put(1, "one").
                put(2, "two").
                put(3, "three").
                put(4, "four").
                put(5, "five").
                put(6, "six").
                put(7, "seven").
                put(8, "eight").
                put(9, "nine").
                put(10, "ten").
                put(11, "eleven").
                put(12, "twelve").
                unmodifiable(true).
                build();
    }

Although we must enter the generic types of the Map (i.e. <Integer, String>) it looks much better. We can avoid all the other disadvantages that the Double Brace Idiom had. Note the Builder method unmodifiable() that sets a flag, controlling if the build() method shall return a normal Map or an unmodifiable Map. Very convenient! Another advantage is that this pattern works with older Java versions and that no extra objects are created during map creation.

The Java 8 Way

Java 8 has a number of features that can be used to create and initialize maps. Take a look at this method:      

    protected static Map<Integer, String> stdJava8() {

        return Collections.unmodifiableMap(Stream.of(
                new SimpleEntry<>(0, "zero"),
                new SimpleEntry<>(1, "one"),
                new SimpleEntry<>(2, "two"),
                new SimpleEntry<>(3, "three"),
                new SimpleEntry<>(4, "four"),
                new SimpleEntry<>(5, "five"),
                new SimpleEntry<>(6, "six"),
                new SimpleEntry<>(7, "seven"),
                new SimpleEntry<>(8, "eight"),
                new SimpleEntry<>(9, "nine"),
                new SimpleEntry<>(10, "ten"),
                new SimpleEntry<>(11, "eleven"),
                new SimpleEntry<>(12, "twelve"))
                .collect(Collectors.toMap((e) -> e.getKey(), (e) -> e.getValue())));
    }

Here we create a Stream of map entries. At least two implementations of Entry already exists in the standard Java libraries and here I have used SimpleEntry. After the Stream is constructed, we collect all the entries and creates a Map by splitting up each Entry in a key and a value. It is important to include the diamond operator for each SimpleEntry or else the toMap() method will not be able to infer the types of the Entry.

As can be seen, many intermediate objects need to be created before the final Map can be constructed. This can be a disadvantage if many instances are created rapidly. One advantage with this method is that it is using a standard Java 8 stream pattern, so it is very easy to start out with this pattern and then modify it to do something else.

The Java 8 Way Simplified  

We can further simplify the process of creating maps the Java 8 way, by adding a small number of support methods to our Maps class like this:      

    public static <K, V> Map.Entry<K, V> entry(K key, V value) {
        return new AbstractMap.SimpleEntry<>(key, value);
    }

    public static <K, U> Collector<Map.Entry<K, U>, ?, Map<K, U>> entriesToMap() {
        return Collectors.toMap((e) -> e.getKey(), (e) -> e.getValue());
    }

    public static <K, U> Collector<Map.Entry<K, U>, ?, ConcurrentMap<K, U>> entriesToConcurrentMap() {
        return Collectors.toConcurrentMap((e) -> e.getKey(), (e) -> e.getValue());
    }



 Now we can create the desired Map using this method:  

    protected static Map<Integer, String> extJava8() {
        return Collections.unmodifiableMap(Stream.of(
                entry(0, "zero"),
                entry(1, "one"),
                entry(2, "two"),
                entry(3, "three"),
                entry(4, "four"),
                entry(5, "five"),
                entry(6, "six"),
                entry(7, "seven"),
                entry(8, "eight"),
                entry(9, "nine"),
                entry(10, "ten"),
                entry(11, "eleven"),
                entry(12, "twelve")).
                collect(entriesToMap()));
    }

Do not forget to import the support methods statically. Now, this looks much nicer than the previous attempt because is is much shorter and does not contain so much boiler plate code.

Conclusion

There are many ways to create and initialize a Map. The choice is really up to you. Personally, I like the Builder Pattern best because it is very efficient, flexible and straight forward to use. The Java 8 pattern is also nice. A final warning on using the Double Brace Idiom should also be made.

How do we do the actual translation of text using the Map we have created using any of the various methods in this post? One nice way of doing it is to use Java 8's Map method getOrDefault() like this:

     public static String toText(Map<Integer, String> map, int val) {
         return map.getOrDefault(val, Integer.toString(val));
     }
    
     final Map<Integer, String> map = imperative();
     System.out.println("There are " + toText(map, 2) + " birds and " + toText(map, 21) + " flowers.");


   "There are two birds and 21 flowers."

UPDATE: Learn how you can implement a type safe dynamic Map builder in this newer post.

Friday, December 5, 2014

Java 8, Implementing a ConcurrentHashSet

Background

In the package java.util.concurrent there are numerous classes that enables concurrent access to various objects and data structures. However, there is a lack of a concurrent Set in the standard libraries. In this post I will show how to fix this problem.

The easy way out

There is a very simple way of getting a kind of concurrent Set with elements of type K in Java:
Map<K, Boolean> concurrentMap = new ConcurrentHashMap();
Set<K> concurrentSet = Collections.newSetFromMap(concurrentMap);

For example, one can get a concurrent Set of strings like this
Set<String> concurrentSet = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());

The concurrentSet will exhibit the same concurrency properties as the underlying ConcurrentMap does (i.e. it will provide concurrent lock free access in this case) which is good. It also inherits all the other Map properties such as null key capability etc.

Of course you can provide any map to the newSetFromMap() including the non-concurrent HashMap (keys are in any order), LinkedHashMap  (preserves insertion order) or TreeMap (keeps the keys in their natural order). The resulting Set will inherit those underlying properties. For example, if you provide LinkedHashMap, you will get a non-concurrent Set where the keys will be retrieve in insertion order.

Limitations and Drawbacks

When you are using the Collections.newSetFromMap() method, the Map you provide must be empty from the beginning. You must also take care not to keep an additional reference to the backing map, because newSetFromMap() does not perform any defensive copy of the map. If you keep such a reference, you can alter the Set using the Map reference too, which is unsafe. The value type Boolean used in the underlying Map also strikes me as odd. Why was that particular type selected one might ask oneself? Object would be more general, one might argue.

The most important drawback in my opinion, is that the returned Set really is just a Set that just happens to be concurrent (again, if you provide a ConcurrentMap). For example, it does not implement the method that corresponds to the features ConcurrentMap brings over Map, like putIfAbsent() and numerous other new Java 8 methods like computeIfAbsent(). There is no way to really guarantee that the Set is concurrent.

The Interface Proposal

So what do we want to accomplish here? Well, wouldn't it be nice if we could define an interface ConcurrentSet and use it just like we are using the interface ConcurrentMap. Let us take a look at the latter interface (as defined in Java 8):

public interface ConcurrentMap<K, V> extends Map<K, V> {

    V getOrDefault(Object key, V defaultValue);

    void forEach(BiConsumer<? super K, ? super V> action);

    V putIfAbsent(K key, V value);

    boolean remove(Object key, Object value);

    boolean replace(K key, V oldValue, V newValue);

    void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)

    V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction);

    V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction);

    V compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction);

    V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction);

}

As can be seen, most of the methods are dealing with values rather than keys. Thus, most of the methods can not be applied to a ConcurrentSet. So, we can discard most methods and perhaps redefine others so that they only deal with keys. First I thought that we should skip all methods except the putIfAbsent() method, but I was wrong since it is equivalent to add() (thanks for pointing that out Louis Wasserman). So, we drop all methods and end up with just a Marker Interface with no extra methods over Set. Still, it is useful because we can show our intent with the new interface.

public interface ConcurrentSet<E> extends Set<E> {

}

Additional concurrent methods can be added later if desired. Please leave a comment below if you can think of new methods that would be nice to add to a ConcurrentSet.

What's Alredy There?

If we take a closer look at the Collections.newSetFromMap() method, we see that it basically delegates the methods from a backing map (and the backing map's keySet). Below, I have shown a shortened version of the SetFromMap class, so you will get the basic idea. The same concept is also used by Java's ConcurrentSkipListSet, so this certainly seams to be common practice.

 private static class SetFromMap<E> extends AbstractSet<E>
        implements Set<E>, Serializable
    {
        private final Map<E, Boolean> m;  // The backing map
        private transient Set<E> s;       // Its keySet

        SetFromMap(Map<E, Boolean> map) {
            if (!map.isEmpty())
                throw new IllegalArgumentException("Map is non-empty");
            m = map;
            s = map.keySet();
        }

        public void clear()               {        m.clear(); }
        public int size()                 { return m.size(); }
        public boolean isEmpty()          { return m.isEmpty(); }
        public boolean contains(Object o) { return m.containsKey(o); }
        public boolean remove(Object o)   { return m.remove(o) != null; }
        public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
        public Iterator<E> iterator()     { return s.iterator(); }
        public Object[] toArray()         { return s.toArray(); }
        public <T> T[] toArray(T[] a)     { return s.toArray(a); }
        public String toString()          { return s.toString(); }
        public int hashCode()             { return s.hashCode(); }
        public boolean equals(Object o)   { return o == this || s.equals(o); }
        public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
        public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
        public boolean retainAll(Collection<?> c)   {return s.retainAll(c);

       // The rest comes here...
}

An Implementation Proposal

Using the Delegation Pattern, we can easily come up with a similar implementation of the new ConcurrentSet interface as depicted here under:

/**
 * A hash set supporting full concurrency of retrievals and
 * high expected concurrency for updates.
 *
 * @param <E> the type of elements maintained by this set
 * @author pemi
 *
public class ConcurrentHashSet<E> implements ConcurrentSet<E>, Serializable {

    private final ConcurrentMap<E, Object> m;
    private transient Set<E> s;

    public ConcurrentHashSet() {
        this.m = new ConcurrentHashMap<>();
        init();
    }

    public ConcurrentHashSet(int initialCapacity) {
        this.m = new ConcurrentHashMap<>(initialCapacity);
        init();
    }

    public ConcurrentHashSet(int initialCapacity, float loadFactor) {
        this.m = new ConcurrentHashMap<>(initialCapacity, loadFactor);
        init();
    }

    public ConcurrentHashSet(int initialCapacity, float loadFactor, int concurrencyLevel) {
        this.m = new ConcurrentHashMap<>(initialCapacity, loadFactor, concurrencyLevel);
        init();
    }

    public ConcurrentHashSet(Set<? extends E> s) {
        this(Math.max(Objects.requireNonNull(s).size(), 16));
        addAll(s);
    }

    // New type of constructor
    public ConcurrentHashSet(Supplier<? extends ConcurrentMap<E, Object>> concurrentMapSupplier) {
        final ConcurrentMap<E, Object> newMap = concurrentMapSupplier.get();
        if (!(newMap instanceof ConcurrentMap)) {
            throw new IllegalArgumentException("The supplied map does not implement "+ConcurrentMap.class.getSimpleName());
        }
        this.m = newMap;
        init();
    }
   
    private void init() {
        this.s = m.keySet();
    }
   
    @Override public void clear()               {        m.clear(); }
    @Override public int size()                 { return m.size(); }
    @Override public boolean isEmpty()          { return m.isEmpty(); }
    @Override public boolean contains(Object o) { return m.containsKey(o); }
    @Override public boolean remove(Object o)   { return m.remove(o) != null; }
    @Override public boolean add(E e)           { return m.put(e, Boolean.TRUE) == null; }
    @Override public Iterator<E> iterator()     { return s.iterator(); }
    @Override public Object[] toArray()         { return s.toArray(); }
    @Override public <T> T[] toArray(T[] a)     { return s.toArray(a); }
    @Override public String toString()          { return s.toString(); }
    @Override public int hashCode()             { return s.hashCode(); }
    @Override public boolean equals(Object o)   { return s.equals(o); }
    @Override public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
    @Override public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
    @Override public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}

    @Override
    public boolean addAll(Collection<? extends E> c) {
        // Use Java 8 Stream 
        return Objects.requireNonNull(c).stream().map((e) -> add(e)).filter((b)->b).count() > 0;
    }


    // Override default methods in Collection
    @Override public void forEach(Consumer<? super E> action) { s.forEach(action);}
    @Override public boolean removeIf(Predicate<? super E> filter) { return s.removeIf(filter);}
    @Override public Spliterator<E> spliterator()     {return s.spliterator();}
    @Override public Stream<E> stream()               {return s.stream();}
    @Override public Stream<E> parallelStream()       {return s.parallelStream();}

    private static final long serialVersionUID = -913526372691027123L;

    private void readObject(java.io.ObjectInputStream stream)
       throws IOException, ClassNotFoundException
    {
        stream.defaultReadObject();
        init();
    }

}
Note the new constructor ConcurrentHashSet(Supplier<ConcurrentMap<E, Object>> concurrentMapSupplier) that allows us to provide any ConcurrentMap as the underlying map at creation time. By providing a Supplier rather than a concrete Map instance, we avoid the double reference problem and the "map must be empty" problem associated with the Collections.newSetFromMap() method. For example, we can create a ConcurrentSet with the keys in their natural order by calling new ConcurrentHashSet(ConcurrentSkipListMap::new).

Worth noticing is also the addAll() method that uses Java 8's stream library to iteratively add new elements to the Set. We the filter out all add() calls that returned true and if there were more than zero such additions, we return true (i.e. there was a modification of the set).

Game, Set and match...


Wednesday, November 5, 2014

Compute factorials using Java 8 streams


Background

N factorial (also denoted N!) means computing 1*2*3*...*N and is a classical problem used in computer science to illustrate different programming patterns. In this post I will show how one can use Java 8's Streams to calculate factorials. But first, I will show two other ways that were previously used before Java 8 appeared.

Recursion

From our computer science classes, we all remember the classical way of computing factorial(). The following method illustrates the concept:
    public long factorial(int n) {
        if (n > 20) throw new IllegalArgumentException(n + " is out of range");
        return (1 > n) ? 1 : n * factorial(n - 1);
    }
Because long overflows for n > 20, we need to throw an exception to avoid faulty return values. If we are within the valid input range, we check for the basic case where n is 1 or less for which factorial is 1, otherwise we recurse by returning n multiplied with factorial(n-1). Eventually, we will reach factorial(1) and the recursion stops.

Imperative 

You can also use the standard imperative way of doing it using an intermediate value that is used in a loop, like this:
    public long factorial(int n) {
        if (n > 20) throw new IllegalArgumentException(n + " is out of range");
        long product = 1;
        for (int i = 2; i < n; i++) {
            product *= i;
        }
        return product;
    }

Look at the loop and you might be surprised to see that we start from 2. We could as well have started from 1, but then again, multiplying with 1 always gives back the same result, doesn't it? So we optimize away that case.

Streams

Using Java 8's stream methods we can implement factorial() in another way as depicted here:
    public long factorial(int n) {
        if (n > 20) throw new IllegalArgumentException(n + " is out of range");
        return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
    }
Using the LongStream.rangeClosed(2, n) method we create a Stream of longs with the content 2, 3, ... , n. Then we take this Stream and successively applies the reduction (a, b) -> a * b meaning that for each pair a and b we multiply them and return the result. The result then carries over to a for the next round. The value "1" used in the reduced method is the identity value, i.e. the value that is used as a starting value for a for the first iteration.

This way, we abstract away the implementation and instead focus on what to do. For example, the Stream could be made parallel and that way we could calculate the value using several threads.  Perhaps not so useful in this particular example where n < 20, but certainly for other applications with longer iteration chains.

Consider using Streams when iterating over values!

Tuesday, October 21, 2014

Protect Your Immutable Object Invariants in More Complex Java Objects

Background

Duke and Spire Locking in Objects
By using Immutable Objects, which are objects that can not be observed to change once they are created, you gain a number of advantages including inherent thread safety, improved run time efficiency and code robustness. But how do you protect your object's invariants? This post shows some of the fundamental schemes that can be used to ensure that your objects remain immutable. The examples in this post requires Java 8 but it is relatively easy to rewrite them in Java 7 or lower.

Immutable objects are used extensively in the open-source project Speedment that I am contributing to. With Speedment we can view database tables as standard Java 8 streams. Check out Speedment on GitHub.

Simple Immutable Objects

In my Previous post, I talked a lot about how one can create immutable objects using the Builder Pattern. In this post I will use a more simple approach to create the objects, because I want to focus on another aspect of the immutable objects.

Consider the following Object:

public class Author {

    private final String name;
    private final int bornYear;

    public Author(final String name, final int bornYear) {
        this.name = name;
        this.bornYear = bornYear;
    }

    public String getName() {
        return name;
    }

    public int getBornYear() {
        return bornYear;
    }

}

The object's invariants are protected by the final declarations (that make it impossible to write code in the class that directly changes the properties of the Object), by the private declarations (that make sure that no other class can gain access to the fields) and by the fact that there are no setters for the object's properties (it would in fact, not be possible to write setters because the fields are declared final). Now is a good time to mention that your objects can, in theory, be modified anyhow, for example using Java Reflection. However, this is considered "cheating" ...


Now if we run the following test program we get exactly what one would expect.

public class Main {

    public static void main(String[] args) {
        final Author author = new Author("William Shakespeare", 1564);

        System.out.println(author.getName() + " was born in " + author.getBornYear());

    }

}

William Shakespeare was born in 1564

N.B. Even though author is declared final, this does not affect how methods can be called on the object itself. It only says that the object reference variable author can be assigned only once.

Complex Immutable Objects

Some objects contain more complex properties such a Maps, Sets, Lists, Collections and the likes. Consider the following Author object with an added property consisting of a List of the author's works.

import java.util.List;

public class Author {

    private final String name;
    private final int bornYear;
    private final List<String> works;

    public Author(final String name, final int bornYear, final List<String> works) {
        this.name = name;
        this.bornYear = bornYear;
        this.works = works;
    }

    public String getName() {
        return name;
    }

    public int getBornYear() {
        return bornYear;
    }

    public List<String> getWorks() {
        return works;
    }

}

If we run the following test program, we expose a problem with the "immutable" object that really makes it mutable.

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {

    public static void main(String[] args) {
        final List<String> works = Stream.of("Hamlet", "Othello", "Macbeth")
              .collect(Collectors.toList());
        final Author author = new Author("William Shakespeare", 1564, works);
        println(author);

        // NOT GOOD! We can add things to the list after the object is created!
        author.getWorks().add("Harry Potter");
        println(author);
    }

    private static void println(final Author author) {
        System.out.println(author.getName() + " was born in " + author.getBornYear()
                + " and wrote " + author.getWorks().stream().collect(Collectors.joining(", ")));
    }

}

William Shakespeare was born in 1564 and wrote Hamlet, Othello, Macbeth
William Shakespeare was born in 1564 and wrote Hamlet, Othello, Macbeth, Harry Potter

The getWorks() method returns a reference to the same List that we used to construct the Author. Because the original list used during construction was writable, we can now change this List, for example we can add "Harry Potter" to William Shakespeare's list of works! Not good! Back to the drawing board!

UnmodifiableList

By using a static method from the Collections class, we can create a view of an existing List that prevents the underlying List from being modified. This is nice and thus we make a new attempt to fix the problem:

import java.util.Collections;
import java.util.List;

public class Author {

    private final String name;
    private final int bornYear;
    private final List<String> works;

    public Author(final String name, final int bornYear, final List<String> works) {
        this.name = name;
        this.bornYear = bornYear;
        this.works = Collections.unmodifiableList(works);
    }

    public String getName() {
        return name;
    }

    public int getBornYear() {
        return bornYear;
    }

    public List<String> getWorks() {
        return works;
    }

}

And here is the corresponding test program:
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {

    public static void main(String[] args) {
        final List<String> works = Stream.of("Hamlet", "Othello", "Macbeth").collect(Collectors.toList());
        final Author author = new Author("William Shakespeare", 1564, works);
        println(author);

        // We failed again because we can modify the works List 
        // and it reflects in the Author after creation
        works.add("Harry Potter");
        println(author);
        
        // This works though!
        author.getWorks().add("Harry Potter 2");
        
    }

    private static void println(final Author author) {
        System.out.println(author.getName() + " was born in " + author.getBornYear()
                + " and wrote " + author.getWorks().stream().collect(Collectors.joining(", ")));
    }

}

William Shakespeare was born in 1564 and wrote Hamlet, Othello, Macbeth
William Shakespeare was born in 1564 and wrote Hamlet, Othello, Macbeth, Harry Potter
Exception in thread "main" java.lang.UnsupportedOperationException
 at java.util.Collections$UnmodifiableCollection.add(Collections.java:1115)
 at com.blogspot.minborgsjavapot.immutables._4unmod2.Main.main(Main.java:20)

Again we fail, because even though we now cannot change the List by the reference returned by the getWorks() method, we can still use the original List, used during construction of the Author object, to change the works list after the immutable is created. This is a clear violation against the definition of an immutable object (remeber, no observable change shall be detected after an immutable object is created).

Defensive Copying

By employing Defensive Copying we can protect the immutable object's more complex invariants as shown in the example below:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Author {

    private final String name;
    private final int bornYear;
    private final List<String> works;

    public Author(final String name, final int bornYear, final List<String> works) {
        this.name = name;
        this.bornYear = bornYear;
        // Now we make a new List that is a copy of the provided works list
        this.works = Collections.unmodifiableList(new ArrayList<>(works));
    }

    public String getName() {
        return name;
    }

    public int getBornYear() {
        return bornYear;
    }

    public List<String> getWorks() {
        return works;
    }

}

Finally, we can not change the List of works after object creation. The price is that we need to make a new internal copy of the list that is provided during object creation. This can sometimes be a good thing, since we can select the implementation of the internal List in a way that it can be more efficient than the original List. For example, if the List only consists of one element, one can create a defensive copy using the Collections.singletonList() that creates a specialized implementation of a List with exactly one element, potentially much more efficient than a general List. If the List is empty, one can use the Collections.emptyList() that is even more efficient.

The Collections class

There are several useful methods in the Collections class with respect to protecting immutable objects including unmodifiableCollection(), unmodifiableList(), unmodifiableMap() and unmodifiableSet() and more. Use them in your immutable classes!

A Final Warning

In the examples above, we had a list of Strings and we draw to our mind that the class String, for good reasons, is immutable. But suppose that we had a List of some mutable objects such as StringBuilders or other Lists. Then we would have to make defensive copies of them too, recursively until we finally arrive at an immutable object...

Tip: If you only work with immutable objects within your immutable objects then you are better off...

Try it!

Take the code for a spin using "git clone https://github.com/minborg/javapot.git"

Remember "To Protect and to Serve"






Wednesday, October 15, 2014

New Java 8 "Object Support Mixin Pattern" for overriding Object.equals(), hashCode(), toString() and compareTo()

Preface

You have, with a probability infinitely close to 1, made one or several errors when overriding basic Object methods like equals() and hashCode()! When I discovered a new class off error in one of my client's classes, I started to look in the entire module and discovered that not a single class was correct. Then I checked the entire project and discovered that every class had the same type of error. Panic! Things went from bad to worse when I checked my own Java code written over the last decade. Just one single class was correct in a strict sense. The errors did not surface, but still, they were there, lurking to appear in the future. So far I have seen 49513 faulty classes and one correct making 99.998% of the classes faulty... Read this post to see how you can avoid these errors!

Overview

In this post, I will disclose a new pattern that I have called the "Object Support Mixin Pattern" and that can be used for automatically overriding the Object methods equals(), hashCode() and toString() in a correct way. I will also show how the related Comparable.compareTo() can be implemented in a similar way.

Using this pattern, that relies on Java 8's new default interface methods, it is possible to automatically mix in support methods without scarifying the ability to inherit from another super class. I will show several variants of the pattern that, depending on the circumstances, can be used directly in your own code. This is a long and sometimes complicated post but please read it thoroughly and you will end up being a better programmer!

When you have read this post to the very end, you will understand why the following class will automatically have correct equals(), hashCode() and toString() methods that will consider the bean properties name, email and born:

public class Person extends ReflectionObjectSupport<Person> {

    private final String name;
    private final String email;
    private final int born;

    public Person(String name, String email, int born) {
        this.name = name;
        this.email = email;
        this.born = born;
    }

    public String getName() {
        return name;
    }

    public String getEmail() {
        return email;
    }

    public int getBorn() {
        return born;
    }

 }
The superclass ReflectionObjectSupport will override the equals(), hashCode(), toString() and compareTo() methods and, based on reflection, provide fully automatic methods.

If you have classes that already have inherited from another super class (as you probably know, Java can, for good reasons, only inherit from one super class) you can use the Object Support Mixin Pattern. Below, the same Person class is depicted using the Object Support Mixin Pattern. This class also implements the Comparable.compareTo() method.
public class Person implements Comparable<Person>, ReflectionObjectMixin<Person> {

    private final String name;
    private final String email;
    private final int born;

    public Person(String name, String email, int born) {
        this.name = name;
        this.email = email;
        this.born = born;
    }

    public String getName() {
        return name;
    }

    public String getEmail() {
        return email;
    }

    public int getBorn() {
        return born;
    }

    @Override
    public Comparable[] compareToMembers() {
        return mkComparableArray(getName());
    }

    @Override
    public int hashCode() {
        return _hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return _equals(obj);
    }

    @Override
    public String toString() {
        return _toString();
    }

    @Override
    public int compareTo(Person o) {
        return _compareTo(o);
    }

}
It is difficult to imagine shorter override methods for the Object methods and no support methods are needed in the class except for compareTo() where we need to make a human decision on how we shall order the object. Note that the class is free to inherit from another class, since it is only implementing interfaces and does not extend any class right now.

The problem

While working for some clients, I have often noticed how here are errors in the fundamental Object methods equals() and hashCode(). More suprisingly on my own part, I have also discovered major errors related to the same methods in code that I have written myself. This seams to be a ubiquitous problem and I have not seen a really good pattern to eliminate this plague. Most solution relies on hand coded methods.

There are several articles on the net describing how to write the equals() and hashCode() methods and both methods are related to each other. In short, it is imperative that these methods fulfill their contract or else the class will fail! Failures can occur, for example, when a faulty object is put into a Map or in other types of Collections that are so commonly used in Java code.

The equals() contract

Let us start with the equals() method. The contract requires the following properties for any non-null object "a":

A) It is reflexive, meaning that a.equals(a)
B) It is symmetric, meaning that if a.equals(b) then b.equals(a)
C) It is transient, meaning that if a.equals(b) and b.equals(c) then a.equals(c)
D) It is consistent, meaning that if a.equals(b) this must always be true unless a and/or b change.
E) a.equals(null) shall always be false

What does this mean in pure English? Let me use an analogy with a "dime" that is a ten-cent coin, one tenth of a United States dollar.

A) unsurprisingly says "a dime is equal to a dime". It is an axiomatic definition that seams reasonable. Otherwise equals() would really not make much sense, would it?

B) says "if a dime is 10 cent, then 10 cent is a dime" which seams reasonable. If a thing is equal to something else, the latter thing must also be equal to the first thing.

C) says "if a dime is 10 cent and 10 cent is 0.1 buck, then a dime is 0.1 buck". This rule allows us to infer equality between several objects. It really says that if there are bunch of equal objects and another object is equal to one of these objects, then that object is also equal to all objects in the bunch.

D) says "if a dime is 10 cent now, it must always remain so (unless we change a dime to say 8 cent or so)". Perhaps politicians can navigate around this rule, but we programmers must not!

E) says that "a dime is never equal to nothing". Let us hope that even politicians will adhere to this rule!

The hashCode() contract

If we look at the contract of the hashCode() we conclude that it must:

  A) be consistent, meaning that a.hashCode() should always return the same integer unless a is changed. This is similar to item D for equals().
  B) if a.equals(b) then a.hashCode() and b.hashCode() must return the same integer value.

A is easy to understand but B is a somewhat confusing statement: if a.equals(b) is false, then a.hashCode() and b.hashCode() may or may not return the same integer. If this was not the case, then the number of integers would quickly run out. So, new Point(100,234).hashCode() might produce the same result as new Color(240, 240, 240).hashCode() for example, even though they certainly are not equal.

The default equals() method inherited from the Object class relies on comparing the references to the objects. If they refer to the same object, then the objects are considered to be equal, otherwise they are not equal. This is how it looks:

public boolean equals(Object obj) {
    return (this == obj);
}

The simplest imaginable hashCode() method would be:
 // Legal but do not use this method!!
public int hashCode() {
    return 0;
}
Albeit legal, this method would lead to very poor hash performance. For a Map, all keys would hash to the same bucket, effectively turning the Map into a List. 0 fulfills A because it is consistently 0 and it also fulfills B because all objects would have the hashCode of 0, regardless if they are equal or not. So those objects that are in fact equal, would undoubtedly have the same hashCode.

The hashCode() inherited from the Object class is better than this and will compute an integer based on the numerical value of the object's reference. This is actually a good starting point. It fulfills the contract of the methods (check this for youself!) and for classes that are generally not comparable, such as Thread and Random, they work like a charm. For a typical beans however, where we want to compare the bean properties to asses equality, the situation is not so good.

Common error types

I have notices four distinct errors commonly made in this area:

i) One common mistake is that a programmer overrides one of the methods and not the other. This will, in almost any situation, break the contract of rule B for the hashCode() method! If the programmer overrides equals() and not hashCode() then a.equals(b) will behave differently than before but hashCode() will behave the same. If the programmer on the other hand overrides hashCode() and not equals() then a.equals(b) will behave differently but the hashCode() will remain the same. Always override hashCode() and equals() at the same time!

ii) Another common error is that you overide both methods but regard different bean properties in the methods. Suppose that, if you have a class similar to the Person class above, you use all the properties: getName(), getEmail() and getAge() but in the hashCode() you only use getName() and getEmail() because you added age later and forgot to add it in the hashCode().

iii) A third more subtile error is that you create a (perhaps anonymous) class that overrides one of the getters. In your equals() and hashCode() you use the member variables directly to compare classes and not the corresponding getters. Now your bean will expose the overridden property for the getter but equals() and hashCode() will use the member variable that is not exposed any more.

iv) Class types are compared using instanceof instead of comparing class objects directly, resulting in an asymmetry for overridden classes visa vi their parent class. This will break B and/or C. For example, consider two classes Person and FemalePerson where the latter extends the former. If Person is using (female instanceof Person) and FemalePerson is using (person instanceof FemalePerson) in their equals() methods, (female instanceof Person) is true while (person instanceof FemalePerson) certainly is false.

although strictly not an error but more of an inconvenience, I would like to add another problem commonly appearing in classes:

v) In an attempt to avoid iv) errors, class types are compared using the getClass() method effectively prohibiting derived classes (such as anonymous or inherited classes) to be equal to their base classes.

Asymmetry

I will elaborate more on type iv) errors because they are a bit more difficult to explain. Suppose that we have a bean class named "A" with a bean property named "value" like this:

public class A {

    private final int val;

    public A(int val) {
        this.val = val;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 13 * hash + this.getVal();
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (!(obj instanceof A)) {
            return false;
        }
        final A other = (A) obj;
        if (this.getVal() != other.getVal()) {
            return false;
        }
        return true;
    }

    public int getVal() {
        return val;
    }

}

Then we extend class A with another class with the somewhat expected name "B", where B introduces an additional bean property named "anotherValue" like this:
public class B extends A {

    private final int anotherValue;

    public B(int val, int anotherValue) {
        super(val);
        this.anotherValue = anotherValue;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 67 * hash + this.getValue();
        hash = 67 * hash + this.getAnotherValue();
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (!(obj instanceof B)) {
            return false;
        }
        final B other = (B) obj;
        if (this.getAnotherValue() != other.getAnotherValue()) {
            return false;
        }
        if (this.getValue() != other.getValue()) {
            return false;
        }
        return true;
    }

    public int getAnotherValue() {
        return anotherValue;
    }

}

We also create a test class to test the A and B classes:

public class Main {

    public static void main(String[] args) {
        A a = new A(1);
        B b = new B(1, 2);

        System.out.println("a.equals(b) is " + a.equals(b));  // true
        System.out.println("b.equals(a) is " + b.equals(a));  // false
    }

}

As can be seen, we get the disappointing result that "a.equals(b) is true" whereas "b.equals(a) is false". A clear violation of the symmetry rule B!


Preface and Overall Solution Strategy

Before we start with the solution, I want to draw to the attention that equals() and hashCode() basically has the same skeleton. They should both iterate over the (same) bean properties and produce a result. equals() shall return a boolean value if all the bean properties are equal whereas hashCode() shall return an integer that depends on all the bean properties. It would appear rational if both methods got their input properties from the same source using their getters. This way, we avoid mistake i), ii) and iii).

So, imagine that we have an interface with the method Object[] members() that the class has to implement and that it is used both in the equals() and hashCode() method.

Before we lay out a solution, we start with looking at what most IDE:s will generate if you request that they shall generate equals() and hashCode() methods. This allows us to understand the problem a bit more.


The IDE Bean Pattern

Most IDEs have built-in functions for generating the equals() and hashCode(). My IDE makes mistake iii) but otherwise it looks reasonable. After fixing this and some other minor flaws it looks something like this:

public class Person implements Comparable&ltPerson&gt {

    private final String name;
    private final String email;
    private final int born;

    public Person(String name, String email, int born) {
        this.name = Objects.requireNonNull(name);
        this.email = email;
        this.born = born;
    }

    public String getName() {
        return name;
    }

    public String getEmail() {
        return email;
    }

    public int getBorn() {
        return born;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 61 * hash + Objects.hashCode(getName());
        hash = 61 * hash + Objects.hashCode(getEmail());
        hash = 61 * hash + getBorn();
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Person other = (Person) obj;
        if (!Objects.equals(this.getName(), other.getName())) {
            return false;
        }
        if (!Objects.equals(this.getEmail(), other.getEmail())) {
            return false;
        }
        if (this.getBorn() != other.getBorn()) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
        return "Person{" + "Name=" + getName() + ", Email=" + getEmail() + ", Born=" + getBorn() + '}';
    }

    @Override
    public int compareTo(Person that) {
        int nameCompareTo = this.getName().compareTo(that.getName());
        if (nameCompareTo != 0) {
            return nameCompareTo;
        }
        return Integer.valueOf(this.getBorn()).compareTo(that.getBorn());
    }

}

The science field for computing hash codes is quit broad and falls outside the scope of this post. I will perhaps come back on this subject in a later post. Here, one apparently starts with a prime number (7) and then iteratively multiplies the interim result with another prime (61) and adds the hash of the bean property. This progresses until all bean properties has been used.

The equals() is similar in the way that it iterates over the properties, but it progressively checks if they are equal. As soon as one property is determined to be un-equal, the method aborts and returns false. If all bean properties are equal, then the beans are also equal which seams reasonable. Again, note the mistake of using if (!(obj instanceof Person)) instead of if (getClass() != obj.getClass()). Can you see why this will lead to problems when Person is overriden? If we override the Person class with FemalePerson and we let FemalePerson do if (!(obj instanceof FemalePerson)) while the Person still will retain its if (!(obj instanceof Person)) then we will violate contract items B and C! Why is that? A FemalePerson is an instance of both Person and FemalePerson while a Person is an instance of only Person and not FemalePerson. So female.equals(person) might be true while person.equals(female) is false at the same time! The symmetry becomes broken.
The solution depicted above further has the disadvantage that the getClass():es must return exactly the same class which is not good when we, for instance, create anonymous classes. We will see how to fix this problem later on in this post.

I have also shown the toString() method here. It also iterates over the bean values and produces a string which contains all the bean properties.

At the end, there is also a compareTo() method that is similar to the equals() method. However, It iterates over a subset of the bean properties and compares them. If two properties are not equal, the compareTo value of them are returned, otherwise the method progresses over the properties until the last properties and the compareTo of them are returned.

The observant reader is now seeing a pattern here. We only need two "picker" methods that will select the bean properties for equals(), hashCode(), toString() on one hand and for compareTo() on the other hand. If we want to implement the toString() method, we also need a supplementary third picker method that returns the name of each bean property.

Before we continue, I would like to show one way of extending the Person class:

public class FemalePerson extends Person {

    private final String handbagBrand;

    public FemalePerson(String handbagBrand, String name, String email, int born) {
        super(name, email, born);
        this.handbagBrand = handbagBrand;
    }

    public String getHandbagBrand() {
        return handbagBrand;
    }

    @Override
    public int hashCode() {
        return 61 * super.hashCode() + Objects.hashCode(getHandbagBrand());
    }

    @Override
    public boolean equals(Object obj) {
        if (!super.equals(obj)) {
            return false;
        }
        final FemalePerson other = (FemalePerson) obj;
        if (!Objects.equals(this.getHandbagBrand(), other.getHandbagBrand())) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
        return "FemalePerson{" + "Name=" + getName() + ", Email=" + getEmail() + ", Born=" + getBorn() + ", HandbagBrand=" + getHandbagBrand() + '}';
    }

}
We have added an important property of females, namely the "handbagBrand". Both the hashCode() and the equals() method calls their respective super methods after which the new bean property is added. The toString() method is rewritten from scratch.

Testing the Beans

Now we can test our new bean. We will use the same test for all the implementation variants of Person and FemalePerson throughout this post. Here it is:

public class Test {

    public static void main(String[] args) {
        final Person adam = new Person("Adam", "adam@mail.com", 1966);
        final Person adam2 = new Person("Adam", "adam@mail.com", 1966);
        final Person adamYoung = new Person("Adam", "adam_88@mail.com", 1988);
        final Person bert = new Person("Bert", "bert@mail.com", 1979);
        final Person bert2 = new Person("Bert", "bert@mail.com", 1979) {

            @Override
            public String toString() {
                return "Strange:" + super.toString();
            }

        };
        final Person cecelia = new FemalePerson("Guchi", "Cecelia", "cecelia@mail.com", 1981);
        final Person ceceliaPro = new FemalePerson("Guchi Pro", "Cecelia", "cecelia@mail.com", 1981);
        final Person cecelia2 = new Person("Cecelia", "cecelia@mail.com", 1981);

        printEquals(adam, adam2);
        printEquals(adam2, adam);
        printEquals(bert, bert2);
        printEquals(bert2, bert);
        printEquals(cecelia, cecelia2);
        printEquals(cecelia2, cecelia);

        final List l = Arrays.asList(cecelia, adamYoung, ceceliaPro, cecelia2, adam, bert, adam2, bert2);

        System.out.println("*** Initial order");
        l.forEach(System.out::println);
        System.out.println("*** Sorted order");
        Collections.sort(l);
        l.forEach(System.out::println);

    }

    private static void printEquals(Person p1, Person p2) {
        System.out.println("It is " + p1.equals(p2) + " that " + p1 + " equals " + p2
                + ". hashCode()s are " + ((p1.hashCode() == p2.hashCode()) ? "equals" : "are different"));
    }

}

We first create two adams with identical bean properties (adam and adam2) followed by a younger version of adam called youngAdam. Then we create two berts with the same bean properties but with different toString() methods, just to illustrated what happens with anonymous class overrides. Then we have three incarnations of cecilias: two FemalePersons with different HandbagBrands, then a cecilia that is just a Person. The objects are rigged to demonstrate different behavior of the implementations depicted in this post.

The test program then prints out how some of the objects that are related in terms of equality and then a list with the person in a mixed order is created. This list is printed, then the list is sorted (to test the compareTo() method) and is then printed again.

When run, the following result will show:

It is true that Person{Name=Adam, Email=adam@mail.com, Born=1966} equals Person{Name=Adam, Email=adam@mail.com, Born=1966}. hashCode()s are equals
It is true that Person{Name=Adam, Email=adam@mail.com, Born=1966} equals Person{Name=Adam, Email=adam@mail.com, Born=1966}. hashCode()s are equals
It is false that Person{Name=Bert, Email=bert@mail.com, Born=1979} equals Strange:Person{Name=Bert, Email=bert@mail.com, Born=1979}. hashCode()s are equals
It is false that Strange:Person{Name=Bert, Email=bert@mail.com, Born=1979} equals Person{Name=Bert, Email=bert@mail.com, Born=1979}. hashCode()s are equals
It is false that FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, HandbagBrand=Guchi} equals Person{Name=Cecelia, Email=cecelia@mail.com, Born=1981}. hashCode()s are are different
It is false that Person{Name=Cecelia, Email=cecelia@mail.com, Born=1981} equals FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, HandbagBrand=Guchi}. hashCode()s are are different
*** Initial order
FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, HandbagBrand=Guchi}
Person{Name=Adam, Email=adam_88@mail.com, Born=1988}
FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, HandbagBrand=Guchi Pro}
Person{Name=Cecelia, Email=cecelia@mail.com, Born=1981}
Person{Name=Adam, Email=adam@mail.com, Born=1966}
Person{Name=Bert, Email=bert@mail.com, Born=1979}
Person{Name=Adam, Email=adam@mail.com, Born=1966}
Strange:Person{Name=Bert, Email=bert@mail.com, Born=1979}
*** Sorted order
Person{Name=Adam, Email=adam@mail.com, Born=1966}
Person{Name=Adam, Email=adam@mail.com, Born=1966}
Person{Name=Adam, Email=adam_88@mail.com, Born=1988}
Person{Name=Bert, Email=bert@mail.com, Born=1979}
Strange:Person{Name=Bert, Email=bert@mail.com, Born=1979}
FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, HandbagBrand=Guchi}
FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, HandbagBrand=Guchi Pro}
Person{Name=Cecelia, Email=cecelia@mail.com, Born=1981}  


As can be seen, it works as expected. As we allredy are aware of, bert2 will not equal bert even though their bean properties are the same because they are not of the same class. There are no occurrences of two objects being equal but at the same time having different hashCodes. The mixed list is sorted in correct order.

Abstract Object Support Class

Consider the following abstract object support class:
public abstract class AbstractObjectSupport<T extends AbstractObjectSupport<T>> implements Comparable<T> {
    protected abstract Object[] members();
    protected abstract Object[] names();
    protected abstract Comparable<?>[] compareToMembers();
    protected Object[] mkArray(final Object... members) {
        return members;
    }

    protected Comparable<?>[] mkComparableArray(final Comparable<?>... members) {
        return members;
    }

    protected Object[] exArray(final Object[] originalMembers, final Object... newMembers) {
        final Object[] result = Arrays.copyOf(originalMembers, originalMembers.length + newMembers.length);
        for (int i = originalMembers.length, n = 0; i < result.length; i++, n++) {
            result[i] = newMembers[n];
        }
        return result;
    }

    protected Comparable<?>[] exComparableArray(final Comparable<?>[] originalMembers, final Comparable<?>... newMembers) {
        final Comparable<?>[] result = (Comparable<?>[]) exArray(originalMembers, (Object[]) newMembers);
        return result;
    }

    @Override
    public int hashCode() {
        return Objects.hash(members());

    }
    @Override
    public boolean equals(final Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        @SuppressWarnings("rawtypes")
        // Must be an AbstractObjectSupport since the class is the same as this class
        final AbstractObjectSupport thatAbstractObjectSupport = (AbstractObjectSupport) obj; 
        return Arrays.equals(members(), thatAbstractObjectSupport.members());
    }

    @Override
    public String toString() {
        final String className = getClass().getSimpleName().isEmpty() ? getClass().getName() : getClass().getSimpleName();
        final StringJoiner sj = new StringJoiner(", ", className + "{", "}");
        final Object[] members = members();
        final Object[] names = names();
        final int n = Math.min(members.length, names.length);
        for (int i = 0; i < n; i++) {
            final StringJoiner msj = new StringJoiner("=");
            msj.add(Objects.toString(names[i]));
            msj.add(Objects.toString(members[i]));
            sj.merge(msj);
        }
        return sj.toString();
    }

    @Override
    public int compareTo(T that) {
        @SuppressWarnings("rawtypes")
        final Comparable[] thisComparables = this.compareToMembers();
        @SuppressWarnings("rawtypes")
        final Comparable[] thatComparables = that.compareToMembers();

        final int n = Math.min(thisComparables.length, thatComparables.length);
        for (int i = 0; i < n; i++) {
            @SuppressWarnings("unchecked")
            final int result = thisComparables[i].compareTo(thatComparables[i]);
            if (result != 0) {
                return result;
            }
        }
        return 0; // They are equal
    }

}

When subclassing from this class, a new concrete class must implement the three support methods:

- members() that will return an ordered array with all the bean properties.
- names() that will return an ordered array of the corresponding bean propoerty names. These names are used in the toString() function only.
- compareToMembers() that will return an ordered array with all the (Comparable) bean properties that shall be used in the compareTo() method.

Then the class implements the equals(), hashCode(), toString() and compareTo() methods by first using the corresponding support methods and then performing some logic on the results. Note how simple equals() and hashCode() are implemented using the Objects and Arrays classes. Note also the use of StringJoiner in the toString() method.

Now we can create our Person and FemalePerson classes very easily like this:
public class Person extends AbstractObjectSupport<Person> {

    private final String name;
    private final String email;
    private final int born;

    public Person(String name, String email, int born) {
        this.name = name;
        this.email = email;
        this.born = born;
    }

    public String getName() {
        return name;
    }

    public String getEmail() {
        return email;
    }

    public int getBorn() {
        return born;
    }

    @Override
    public Object[] members() {
        return mkArray(getName(), getEmail(), getBorn());
    }

    @Override
    public Object[] names() {
        return mkArray("Name", "Email", "Born");
    }

    @Override
    public Comparable<?>[] compareToMembers() {
        return mkComparableArray(getName());
    }

}


and

public class FemalePerson extends Person {

    private final String handbagBrand;

    public FemalePerson(String handbagBrand, String name, String email, int born) {
        super(name, email, born);
        this.handbagBrand = handbagBrand;
    }

    @Override
    public Object[] members() {
        return exArray(super.members(), getHandbagBrand());
    }

    @Override
    public Object[] names() {
        return exArray(super.names(), "handbagBrand");
    }

    public String getHandbagBrand() {
        return handbagBrand;
    }

}

We are now certain that the equals() and hashCode() methods are using the same bean properties and thus we know that they will fulfill their contracts. If we run out test program, we will get the same result as before which is encouraging.

This pattern can be used if you have not inherited from a super class before, but since Java objects can only have one super class, you can not use this pattern when you want to inherit from another class. In the next chapters, we will learn how we can mix in these methods while still being able to inherit from another class.

The Object Support Mixin Pattern

Java 8 provides default methods in interfaces. This functionality was needed to extend existing classes (such as the Collection classes) while retaining compatibility with old code. New methods can be added to interface without the need to implement these methods in the implementing classes. This feature can also be used for other purposes. Now is a good time to mention that some people are against the use of interfaces as carrying any form of logic. According to them, interfaces shall only describe what can be done, not how! I will not engage in this philosophic discussion now. As a marker that this is not just any interface, I have chosen to name the interface to ObjectMixin where the suffix "Mixin" is intended to indicate that it is more than just an interface: methods will be mixed in (not inherited) from the interface. The ObjectMixin looks very similar to the AbstractObjectSupport class:

public interface ObjectMixin<T extends ObjectMixin<T>> {

    Object[] members();

    Object[] names();

    Comparable<?>[] compareToMembers();

    default Object[] mkArray(final Object... members) {
        return members;
    }

    default Comparable<?>[] mkComparableArray(final Comparable<?>... members) {
        return members;
    }

    default Object[] exArray(final Object[] originalMembers, final Object... newMembers) {
        final Object[] result = Arrays.copyOf(originalMembers, originalMembers.length + newMembers.length);
        for (int i = originalMembers.length, n = 0; i < result.length; i++, n++) {
            result[i] = newMembers[n];
        }
        return result;
    }

    default Comparable<?>[] exComparableArray(final Comparable<?>[] originalMembers, final Comparable<?>... newMembers) {
     
        final Comparable<?>[] result = (Comparable<?>[])exArray(originalMembers, (Object[])newMembers);
        return result;
    }

    default int _hashCode() {
        return Objects.hash(members());
    }

    default boolean _equals(final Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        @SuppressWarnings("rawtypes")
        // Must be an AbstractObjectSupport since the class is the same as this class
        final AbstractObjectSupport thatAbstractObjectSupport = (AbstractObjectSupport) obj; 
        return Arrays.equals(members(), thatAbstractObjectSupport.members());
    }

    default String _toString() {
        final String className = getClass().getSimpleName().isEmpty() ? getClass().getName() : getClass().getSimpleName();
        final StringJoiner sj = new StringJoiner(", ", className + "{", "}");
        final Object[] members = members();
        final Object[] names = names();
        final int n = Math.min(members.length, names.length);
        for (int i = 0; i < n; i++) {
            final StringJoiner msj = new StringJoiner("=");
            msj.add(Objects.toString(names[i]));
            msj.add(Objects.toString(members[i]));
            sj.merge(msj);
        }
        return sj.toString();
    }

    default int _compareTo(T obj) {
        @SuppressWarnings("rawtypes")
        final Comparable[] thisComparables = compareToMembers();
        @SuppressWarnings("rawtypes")
        final Comparable[] thatComparables = obj.compareToMembers();

        final int n = Math.min(thisComparables.length, thatComparables.length);
        for (int i = 0; i < n; i++) {
            @SuppressWarnings("unchecked")
            final int result = thisComparables[i].compareTo(thatComparables[i]);
            if (result != 0) {
                return result;
            }
        }
        return 0; // They are equal
    }

}


If we let our Person class implement this interface, it can look like this:

public class Person implements Comparable<Person>, ObjectMixin<Person> {

    private final String name;
    private final String email;
    private final int born;

    public Person(String name, String email, int born) {
        this.name = name;
        this.email = email;
        this.born = born;
    }

    public String getName() {
        return name;
    }

    public String getEmail() {
        return email;
    }

    public int getBorn() {
        return born;
    }

    @Override
    public Object[] members() {
        return mkArray(getName(), getEmail(), getBorn());
    }

    @Override
    public Object[] names() {
        return mkArray("Name", "Email", "Born");
    }

    @Override
    public Comparable<?>[] compareToMembers() {
        return mkComparableArray(getName());
    }

    @Override
    public int hashCode() {
        return _hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return _equals(obj);
    }

    @Override
    public String toString() {
        return _toString();
    }

    @Override
    public int compareTo(Person o) {
        return _compareTo(o);
    }

}

This way, we do not need to scarify the inheritance and but can still gain all the benefits that the AbstractObjectSupport gave us. The only disadvantage is that we need to explicitly override the equals(), hashCode(), toString() and compareTo() methods and delegate to the ObjectMixin methods. As you might be aware of, an interface can neither introduce new bean properties nor can it override existing methods. When we run the test program, we still get the same output as before.

Classes can easily be extended just as in the previous chapter where we saw FemalePerson being declared.

The Standard Object Support Mixin

We still have the nuisance that overridden classes like anonymous classes are not equal to seemingly equal classes. For example, bert and bert2 are not equal even though they have the same bean properties. Remember that only the toString() differs and this should not make them different. By introducing a new method called compareClass() we can use this class instead of the getClass() and compare them. Now we are in charge what class we elect to return and can set a new "watermark" whenever we think that an inherited class shall never be equal to its super class. The neat thing with the solution below is that we will also have a default compareClass() that automatically will determine the highest class that also is an ObjectMixin. So, you get the initial base class compareClass() for free. Note how the defaultBaseCompareObjectMixinClass() is hid in the inner class MethodUtil so it will not be exposed to the implementing class. The  defaultBaseCompareObjectMixinClass() recursively inspects super classes and when a super class does not implement ObjectMixin, it returns.

public interface ObjectMixin<T extends ObjectMixin<T>> {

    Object[] members();

    Object[] names();

    Comparable<?>[] compareToMembers();

    default Class<? extends ObjectMixin<T>> compareClass() {
        return MethodUtil.defaultBaseCompareObjectMixinClass((Class<T>) getClass());
    }

    default Object[] mkArray(final Object... members) {
        return members;
    }

    default Comparable<?>[] mkComparableArray(final Comparable<?>... members) {
        return members;
    }

    default Object[] exArray(final Object[] originalMembers, final Object... newMembers) {
        final Object[] result = Arrays.copyOf(originalMembers, originalMembers.length + newMembers.length);
        for (int i = originalMembers.length, n = 0; i < result.length; i++, n++) {
            result[i] = newMembers[n];
        }
        return result;
    }

    default Comparable<?>[] exComparableArray(final Comparable<?>[] originalMembers, final Comparable<?>... newMembers) {

        final Comparable<?>[] result = (Comparable<?>[]) exArray(originalMembers, (Object[]) newMembers);
        return result;
    }

    default int _hashCode() {
        return Objects.hash(members());
    }

    default boolean _equals(final Object obj) {
        if (!(obj instanceof ObjectMixin)) {
            return false;
        }
        @SuppressWarnings("rawtypes")
        final ObjectMixin thatObjectMixin = (ObjectMixin) obj;
        if (this.compareClass() != thatObjectMixin.compareClass()) {
            return false;
        }
        return Arrays.equals(members(), thatObjectMixin.members());
    }

    default String _toString() {
        final String className = getClass().getSimpleName().isEmpty() ? getClass().getName() : getClass().getSimpleName();
        final StringJoiner sj = new StringJoiner(", ", className + "{", "}");
        final Object[] members = members();
        final Object[] names = names();
        final int n = Math.min(members.length, names.length);
        for (int i = 0; i < n; i++) {
            final StringJoiner msj = new StringJoiner("=");
            msj.add(Objects.toString(names[i]));
            msj.add(Objects.toString(members[i]));
            sj.merge(msj);
        }
        return sj.toString();
    }

    default int _compareTo(T obj) {
        @SuppressWarnings("rawtypes")
        final Comparable[] thisComparables = compareToMembers();
        @SuppressWarnings("rawtypes")
        final Comparable[] thatComparables = obj.compareToMembers();

        final int n = Math.min(thisComparables.length, thatComparables.length);
        for (int i = 0; i < n; i++) {
            @SuppressWarnings("unchecked")
            final int result = thisComparables[i].compareTo(thatComparables[i]);
            if (result != 0) {
                return result;
            }
        }
        return 0; // They are equal
    }

    static abstract class MethodUtil {

        public static <T extends ObjectMixin> Class<T> defaultBaseCompareObjectMixinClass(Class<T> clazz) {
            final Class<? super T> superClazz = clazz.getSuperclass();
            if (!ObjectMixin.class.isAssignableFrom(superClazz)) {
                return clazz;
            }
            @SuppressWarnings("unchecked")
            final Class<T> objectMixinSuperClazz = (Class<T>) superClazz;
            return defaultBaseCompareObjectMixinClass(objectMixinSuperClazz);
        }

    }

}

Please note that the equals() method now considers the compareClass() instead of just the getClass() and that we have full control of the compareClass() method as opposed to the getClass() method.

When we now run the test program we get the following result (shortened listing):

It is true that Person{Name=Adam, Email=adam@mail.com, Born=1966} equals Person{Name=Adam, Email=adam@mail.com, Born=1966}. hashCode()s are equals

It is true that Person{Name=Adam, Email=adam@mail.com, Born=1966} equals Person{Name=Adam, Email=adam@mail.com, Born=1966}. hashCode()s are equals

It is true that Person{Name=Bert, Email=bert@mail.com, Born=1979} equals Strange:com.blogspot.minborgsjavapot.objectmixin._4interface_class.Test$1{Name=Bert, Email=bert@mail.com, Born=1979}. hashCode()s are equals

It is true that Strange:com.blogspot.minborgsjavapot.objectmixin._4interface_class.Test$1{Name=Bert, Email=bert@mail.com, Born=1979} equals Person{Name=Bert, Email=bert@mail.com, Born=1979}. hashCode()s are equals

It is false that FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, handbagBrand=Guchi} equals Person{Name=Cecelia, Email=cecelia@mail.com, Born=1981}. hashCode()s are are different

It is false that Person{Name=Cecelia, Email=cecelia@mail.com, Born=1981} equals FemalePerson{Name=Cecelia, Email=cecelia@mail.com, Born=1981, handbagBrand=Guchi}. hashCode()s are are different


Now, bert and bert2 are equal just as we would expect! Great progress!

When FemalePerson inherit from Person, we also set a new watermark to ensure that FemalePerson are never equal to Person() as shown in this class:

public class FemalePerson extends Person {

    private final String handbagBrand;

    public FemalePerson(String handbagBrand, String name, String email, int born) {
        super(name, email, born);
        this.handbagBrand = handbagBrand;
    }

    @Override
    public Object[] members() {
        return exArray(super.members(), getHandbagBrand());
    }

    @Override
    public Object[] names() {
        return exArray(super.names(), "handbagBrand");
    }

    public String getHandbagBrand() {
        return handbagBrand;
    }

    @Override
    public Class<FemalePerson> compareClass() {
        return FemalePerson.class;
    }

}

The Reflection Object Support Mixin

The pattern can be simplified even more for the implementing classes. It is possible for the interface to provide default support methods for the menbers() and names() methods, eliminating the need for implementing these method by hand. This can be done by extending the previous ObjectMixin inteface as shown hereunder:

public interface ReflectionObjectMixin<T extends ReflectionObjectMixin<T>> extends ObjectMixin<T> {

    @Override
    default Object[] members() {
        return new MethodUtil(getClass()) {

            @Override
            protected Object onMethod(final Method method) {
                try {
                    return method.invoke(ReflectionObjectMixin.this, (Object[]) null);
                } catch (IllegalAccessException | IllegalArgumentException | InvocationTargetException e) {
                    throw new IllegalStateException("Unexpected invocation error", e);
                }
            }
        }.toObjects();

    }

    @Override
    default Object[] names() {

        return new MethodUtil(getClass()) {

            @Override
            protected Object onMethod(final Method method) {
                return method.getName().substring(MethodUtil.INGRESS.length());
            }
        }.toObjects();

    }

    static abstract class MethodUtil {

        public static final String INGRESS = "get";
        public static final Set<String> EXCLUDED_METHODS = new HashSet<>(Arrays.asList("getClass"));
        private final Class<?> clazz;

        private MethodUtil(Class<?> clazz) {
            this.clazz = clazz;
        }

        private static List<Method> obtainGetMethods(Class<?> clazz) {
            final List<Method> result = new ArrayList<>();
            final Method[] methods = clazz.getMethods();
            for (final Method method : methods) {
                final String methodName = method.getName();
                if (methodName.startsWith(INGRESS) && method.getParameterCount() == 0 && !EXCLUDED_METHODS.contains(methodName)) {
                    result.add(method);
                }
            }
            Collections.sort(result, METHOD_COMPARATOR);
            return result;
        }

        protected abstract Object onMethod(Method method);

        public Object[] toObjects() {
            final List<Object> result = new ArrayList<>();
            for (final Method method : MethodUtil.obtainGetMethods(clazz)) {
                result.add(onMethod(method));
            }
            return result.toArray();
        }

        private final static MethodComparator METHOD_COMPARATOR = new MethodComparator();

        private static class MethodComparator implements Comparator<Method> {

            @Override
            public int compare(Method o1, Method o2) {
                int classCompare = o1.getDeclaringClass().getName().compareTo(o2.getDeclaringClass().getName());
                if (classCompare != 0) {
                    return classCompare;
                }
                return o1.getName().compareTo(o2.getName());
            }
        }
    }
}

Both the new default methods members() and names() will iterate over all methods that starts with "get" (except the getClass()) and that does not take any parameters. These are all assumed to be bean properties as dictated by the Bean Pattern. For the names() method, we will just cut out the name of the bean property as the name of the getter excluding the "get" prefix (e.g. "getName" becomes "Name"). For the members() method, we will iterate over the same methods but instead we will invoke the method for the bean and save the resulting result in the result array. The clazz.getMethods() will return the classes methods in any order, so we will sort the methods in class declaration order (name of the class it is declared in) and then in alphabetic order of the method name.

The implementing class is now shorter since we got rid of the members() and names() method declaration:

public class Person implements Comparable<Person>, ReflectionObjectMixin<Person> {

    private final String name;
    private final String email;
    private final int born;

    public Person(String name, String email, int born) {
        this.name = name;
        this.email = email;
        this.born = born;
    }

    public String getName() {
        return name;
    }

    public String getEmail() {
        return email;
    }

    public int getBorn() {
        return born;
    }

    @Override
    public Comparable<?>[] compareToMembers() {
        return mkComparableArray(getName());
    }

    @Override
    public int hashCode() {
        return _hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return _equals(obj);
    }

    @Override
    public String toString() {
        return _toString();
    }

    @Override
    public int compareTo(Person o) {
        return _compareTo(o);
    }

}

When we run the test program we get the following output:

It is true that Person{Born=1966, Email=adam@mail.com, Name=Adam} equals Person{Born=1966, Email=adam@mail.com, Name=Adam}. hashCode()s are equals
It is true that Person{Born=1966, Email=adam@mail.com, Name=Adam} equals Person{Born=1966, Email=adam@mail.com, Name=Adam}. hashCode()s are equals
It is true that Person{Born=1979, Email=bert@mail.com, Name=Bert} equals Strange:javapot.objectmixin._5interface_reflection.Test$1{Born=1979, Email=bert@mail.com, Name=Bert}. hashCode()s are equals
It is true that Strange:javapot.objectmixin._5interface_reflection.Test$1{Born=1979, Email=bert@mail.com, Name=Bert} equals Person{Born=1979, Email=bert@mail.com, Name=Bert}. hashCode()s are equals
It is false that FemalePerson{HandbagBrand=Guchi, Born=1981, Email=cecelia@mail.com, Name=Cecelia} equals Person{Born=1981, Email=cecelia@mail.com, Name=Cecelia}. hashCode()s are are different
It is false that Person{Born=1981, Email=cecelia@mail.com, Name=Cecelia} equals FemalePerson{HandbagBrand=Guchi, Born=1981, Email=cecelia@mail.com, Name=Cecelia}. hashCode()s are are different
*** Initial order
FemalePerson{HandbagBrand=Guchi, Born=1981, Email=cecelia@mail.com, Name=Cecelia}
Person{Born=1988, Email=adam_88@mail.com, Name=Adam}
FemalePerson{HandbagBrand=Guchi Pro, Born=1981, Email=cecelia@mail.com, Name=Cecelia}
Person{Born=1981, Email=cecelia@mail.com, Name=Cecelia}
Person{Born=1966, Email=adam@mail.com, Name=Adam}
Person{Born=1979, Email=bert@mail.com, Name=Bert}
Person{Born=1966, Email=adam@mail.com, Name=Adam}
Strange:javapot.objectmixin._5interface_reflection.Test$1{Born=1979, Email=bert@mail.com, Name=Bert}
*** Sorted order
Person{Born=1988, Email=adam_88@mail.com, Name=Adam}
Person{Born=1966, Email=adam@mail.com, Name=Adam}
Person{Born=1966, Email=adam@mail.com, Name=Adam}
Person{Born=1979, Email=bert@mail.com, Name=Bert}
Strange:javapot.objectmixin._5interface_reflection.Test$1{Born=1979, Email=bert@mail.com, Name=Bert}
FemalePerson{HandbagBrand=Guchi, Born=1981, Email=cecelia@mail.com, Name=Cecelia}
FemalePerson{HandbagBrand=Guchi Pro, Born=1981, Email=cecelia@mail.com, Name=Cecelia}
Person{Born=1981, Email=cecelia@mail.com, Name=Cecelia}

Nice! The only thing that differs is the order of the bean properties in the toString() method.

It becomes even better when we are considering the class FemalePerson, which now looks like this:

public class FemalePerson extends Person {

    private final String handbagBrand;

    public FemalePerson(String handbagBrand, String name, String email, int born) {
        super(name, email, born);
        this.handbagBrand = handbagBrand;
    }

    public String getHandbagBrand() {
        return handbagBrand;
    }

}

It is almost magical, you now get everything for free! The equals(), compareTo() and toString() automatically adjusts to the newly introduced bean property.


The Annotated Object Support Mixin

We can also decide what methods shall be used in the members() and names() method by using annotations. We start by creating our own annotation class named EqualsAndHashCode:

@Retention(value = RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface EqualsAndHashCode {

}

The intention now is that we should simply be able to annotate our methods that we want to "mark" as being in the members() and names() function using this annotation. To allow this we create yet another variant of the ObjectMixin as follows:

public interface AnnotationObjectMixin<T extends AnnotationObjectMixin<T>> extends ObjectMixin<T> {

    @Override
    default Object[] members() {
        return new MethodUtil(getClass(), EqualsAndHashCode.class) {

            @Override
            protected Object onMethod(final Method method) {
                try {
                    return method.invoke(AnnotationObjectMixin.this, (Object[]) null);
                } catch (IllegalAccessException | IllegalArgumentException | InvocationTargetException e) {
                    throw new IllegalStateException("Unexpected invocation error", e);
                }
            }
        }.toObjects();

    }

    @Override
    default Object[] names() {

        return new MethodUtil(getClass(), EqualsAndHashCode.class) {

            @Override
            protected Object onMethod(final Method method) {
                final String methodName = method.getName();
                if (methodName.startsWith(INGRESS)) {
                    return methodName.substring(ReflectionObjectMixin.MethodUtil.INGRESS.length());
                } else {
                    return methodName;
                }
            }
        }.toObjects();

    }

    static abstract class MethodUtil {

        public static final String INGRESS = "get";
        private final Class<?> clazz;
        private final Class annotationClass;

        private MethodUtil(Class<?> clazz, Class annotationClass) {
            this.clazz = clazz;
            this.annotationClass = annotationClass;
        }

        private static List<Method> obtainGetMethods(Class<?> clazz, Class annotationClass) {
            final List<Method> result = new ArrayList<>();
            final Method[] methods = clazz.getMethods();
            for (final Method method : methods) {
                if (method.getParameterCount() == 0 && (method.getAnnotation(annotationClass) != null)) {
                    result.add(method);
                }
            }
            Collections.sort(result, METHOD_COMPARATOR);
            return result;
        }

        protected abstract Object onMethod(Method method);

        public Object[] toObjects() {
            final List<Object> result = new ArrayList<>();
            for (final Method method : MethodUtil.obtainGetMethods(clazz, annotationClass)) {
                result.add(onMethod(method));
            }
            return result.toArray();
        }

        private final static MethodComparator METHOD_COMPARATOR = new MethodComparator();

        private static class MethodComparator implements Comparator<Method> {

            @Override
            public int compare(Method o1, Method o2) {
                int classCompare = o1.getDeclaringClass().getName().compareTo(o2.getDeclaringClass().getName());
                if (classCompare != 0) {
                    return classCompare;
                }
                return o1.getName().compareTo(o2.getName());
            }
        }
    }
}

Now we are able just to "mark" our implementing class methods with @EqualsAndHashCode as shown here:

public class Person implements Comparable<Person>, AnnotationObjectMixin<Person> {

    private final String name;
    private final String email;
    private final int born;

    public Person(String name, String email, int born) {
        this.name = name;
        this.email = email;
        this.born = born;
    }

    @EqualsAndHashCode
    public String getName() {
        return name;
    }

    @EqualsAndHashCode
    public String getEmail() {
        return email;
    }

    @EqualsAndHashCode
    public int getBorn() {
        return born;
    }

    @Override
    public Comparable<?>[] compareToMembers() {
        return mkComparableArray(getName());
    }

    @Override
    public int hashCode() {
        return _hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return _equals(obj);
    }

    @Override
    public String toString() {
        return _toString();
    }

    @Override
    public int compareTo(Person o) {
        return _compareTo(o);
    }

}

The extending FemalePerson class can now look like this:

public class FemalePerson extends Person {

    private final String handbagBrand;

    public FemalePerson(String handbagBrand, String name, String email, int born) {
        super(name, email, born);
        this.handbagBrand = handbagBrand;
    }

    @EqualsAndHashCode
    public String getHandbagBrand() {
        return handbagBrand;
    }

}

Performance

The equals() and hashCode() methods call the members() method which converts any primitive bean properties (such as int) to their corresponding wrapper classes (e.g. Integer) by means of auto-boxing. This leads to unnecisary creation of short lived objecs compare to hand coded equals() and hashCode() methods where the primitives can be used directly for comparison.

The performance of reflection is relatively poor, so if you use the ReflectionObjectMixin or the AnnotationObjectMixin you will notice reduced performance. A large part of this performance drop can be regained by caching the reflection calls using a ConcurrentHashMap as shown in the following snippet, form a performance optimized ReflectionObjectMixin class:

        private static final Map<Class<?>, List<Method>> methodCache = new ConcurrentHashMap<>();

        private static List<Method> obtainGetMethods(Class<?> clazz) {

            List<Method> cacheResult = methodCache.get(clazz);
            if (cacheResult != null) {
                return cacheResult;
            } else {
                final List<Method> result = new ArrayList<>();
                final Method[] methods = clazz.getMethods();
                for (final Method method : methods) {
                    final String methodName = method.getName();
                    if (methodName.startsWith(INGRESS) && method.getParameterCount() == 0 && !EXCLUDED_METHODS.contains(methodName)) {
                        result.add(method);
                    }
                }
                Collections.sort(result, METHOD_COMPARATOR);
                methodCache.put(clazz, result);
                return result;
            }
        }
The performance of the compareClass() can also be improved in the same way using a static lookup Map.


Interface Wrapper Class

If you can use inheritance, you can create a small interface wrapper class that you can inherit from to save the work of overriding the Object methods like this:

public class ReflectionObjectSupport<T extends ReflectionObjectMixin<T>> implements ReflectionObjectMixin<T>, Comparable<T> {

    @Override
    public Comparable<?>[] compareToMembers() {
        throw new UnsupportedOperationException("Override this method in your class to implement comapreTo() support.");
    }

    @Override
    public boolean equals(Object obj) {
        return _equals(obj);
    }

    @Override
    public int hashCode() {
        return _hashCode();
    }

    @Override
    public String toString() {
        return _toString();
    }

    @Override
    public int compareTo(T o) {
        return _compareTo(o);
    }

}


Now your Person class can look just as promised at the top of this post!

Conclusions

You should develop a strategy on how to override the equals() and hashCode() methods that ensures that you will use the same bean properties for them both. You should also make sure that, when you override classes, their equals() and hashCode() should work as expected.

The Object Support Mixin Pattern ensures that the contract of the equals() and hashCode() are fulfilled. Furthermore, it makes coding of these method much easier and less error prone. The Object Support Mixin Pattern allows you to extend a different super class and just mix in the functionality you need without scarifying the single class inheritance. The Object Support Mixin Pattern also allows easy subclassing, both with normal classes and anonymous classes. One drawback with the pattern is that its performance is less than their hand coded counter parts.

Future Improvements

All the mixin methods and support methods are exposed as public methods. Perhaps it is possible to move the methods to an inner class so that they are not seen directly in the implementing class.

Bean properties stored using primitive classes (such as ints and longs) can perhaps be handled by separate member() methods to eliminate auto-boxing overhead. Perhaps, these primitive bean properties shall be compared before the wrapper class bean properties since, presumably, they are faster to compare.

Good luck with improving your basic Object methods!