Implementing an IdentityLinkedHashSet by Wrapping a LinkedHashSet

Question

In the Java standard library, a LinkedHashSet is the same as HashSet but with predictable iteration order (insertion-order). I need an IdentityHashSet (which uses object-identity or reference-equality, instead of object-equality) with predictable iteration order (insertion-order).

While there is no IdentityHashSet in Java's standard library, you can easily create one using the available IdentityHashMap with the following statement:

Set<T> identitySet = java.util.Collections.newSetFromMap(new IdentityHashMap<>());

This is almost the same implementation used in Guava's Sets.newIdentityHashSet(); but this has the unspecified, generally chaotic ordering of HashMap keys (and HashSet elements).

My searches for an implementation of an IdentityLinkedHashSet had no results, so I decided to implement it myself. One useful result which I found was this answer, which suggests to use an identity-wrapper class in composition with LinkedHashSet.

I tried to implement this idea. Below is some key snippet of my implementation. Access the full Gist here.

public class IdentityLinkedHashSet<E> implements Set<E> {

    private LinkedHashSet<IdentityWrapper> set;

    /* ... constructors ... */

    @Override
    public boolean add(E e) {
        return set.add(new IdentityWrapper(e));
    }

    @Override
    public boolean contains(Object obj) {
        return set.contains(new IdentityWrapper((E) obj));
    }

    /* ... rest of Set methods ... */

    private class IdentityWrapper {

        public final E ELEM;

        IdentityWrapper(E elem) {
            this.ELEM = elem;
        }

        @Override
        public boolean equals(Object obj) {
            return obj != null && ELEM == obj;
        }

        @Override
        public int hashCode() {
            return System.identityHashCode(ELEM);
        }
    }
}

Then I wrote a few unit-tests to verify my implementation. Unfortunately some of the assertions fail! Here are my tests:

String str1 = new String("test-1");
String str2 = new String("test-2");
String str3 = new String("test-2");

Set<String> identitySet = new IdentityLinkedHashSet<>();

assertTrue(idSet.add(str1));
assertFalse(idSet.add(str1));       //  <-- fails!
assertTrue(idSet.contains(str1));   //  <-- fails!
//
assertTrue(idSet.add(str2));
assertFalse(idSet.add(str2));       //  <-- fails!
assertTrue(idSet.contains(str2));   //  <-- fails!
assertFalse(idSet.contains(str3));
//
assertTrue(idSet.add(str3));
assertFalse(idSet.add(str3));       //  <-- fails!
assertTrue(idSet.contains(str3));   //  <-- fails!
assertEquals(3, idSet.size());      //  <-- fails!

What have I done wrong in this implementation?

Side note: `IdentityWrapper` doesn't need to know the element type so instead of using `E` I'd just use `Object` to avoid confusion as well as that `(E) obj` cast which will generate a warning. — Thomas, Jan 18 '19 at 12:52
You should further note that `equals()` will get passed another `IdentityWrapper` by the inner set. That's why your test fails - the object and the wrapper are not the same instance. You'd need to cast to `IdentityWrapper` and compare its `ELEM` instead (step through your code with a debugger to see for yourself). — Thomas, Jan 18 '19 at 12:54
@Thomas As you and Lino mentioned, that was exactly the issue. Thank you. — Seyed Mohammad, Jan 19 '19 at 08:02

Lino · Accepted Answer · 2019-01-18T13:01:36.307

When calling the IdentityWrapper.equals() method. The LinkedHashSet will not pass the ELEM but rather an IdentityWrapper object.

You have to introduce an additional check (instanceOf) and then unwrap the passed object to compare the elements:

public boolean equals(Object obj) {
    return (obj instanceof IdentityLinkedHashSet<?>.IdentityWrapper) && 
        ELEM == ((IdentityLinkedHashSet<?>.IdentityWrapper) obj).ELEM;
}

Some notes:

instanceof will check for null, so you can remove that check entirely.

You have to reference IdentityWrapper like this: IdentityLinkedHashSet<?>.IdentityWrapper because it is not a static class. As noted in the comments. It can be made static, and the type of the ELEM can be changed from E to Object. Which would you leave also with a nicer equals method:

private static class IdentityWrapper {

    public final Object ELEM;

    IdentityWrapper(Object elem) {
        this.ELEM = elem;
    }

    @Override
    public boolean equals(Object obj) {
        return (obj instanceof IdentityWrapper) && ELEM == ((IdentityWrapper) obj).ELEM;
    }

    @Override
    public int hashCode() {
        return System.identityHashCode(ELEM);
    }
}

This tiny mistake was exactly the issue and now all the tests pass. One question: other than shorter referencing, is there any other benefit to making `IdentityWrapper` static? — Seyed Mohammad, Jan 20 '19 at 10:15
@SeyedMohammad I figured out the answer: "if the inner-class has no need to access members of the outer class, it's preferred to be static." [Ref-1](https://docs.oracle.com/javase/tutorial/java/javaOO/nested.html) + [Ref-2](https://stackoverflow.com/q/16147405/1609705) — Seyed Mohammad, Jan 20 '19 at 10:35

Implementing an IdentityLinkedHashSet by Wrapping a LinkedHashSet

1 Answers1