Fun with Collections and Reflection

I saw an interesting post on JavaBlogs about a HashSet puzzler. The problem posed was to find the original instance in a HashSet given a new instance that’s equal to the original but not the same instance, without iterating through the collection.

I’m not sure if mine is the most optimal solution, but I don’t see how to do it without reflection. HashSet is backed by a HashMap, which is inverted and uses the Set‘s entries as keys. So it’s simple to reflect in and get the Map, then reflect into that and get the corresponding Map.Entry (this is the approach used internally for the contains() check, but it’s not public), and the key of this entry is the original instance (I wrote it in JUnit style to take advantage of assertions):

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertSame;
import static org.junit.Assert.assertTrue;

import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

import org.junit.Test;

public class HashSetThing {

  @Test
  public void findOriginalInstance() throws NoSuchMethodException,
        NoSuchFieldException, IllegalAccessException, InvocationTargetException {

    HashSet<Thing> set = new HashSet<Thing>();
    set.add(new Thing(1));
    Thing thing2 = new Thing(2);
    set.add(thing2);
    set.add(new Thing(3));

    int instanceId = thing2._instanceId;

    HashMap<Thing, Object> map = reflectMap(set);

    Thing thingKey = new Thing(2);
    assertTrue("Contains should be true for not-same but equal instance",
        set.contains(thingKey));
    int thingKeyInstanceId = thingKey._instanceId;

    // why isn't there an assertNotEqual()?
    assertFalse("A new instance should have a unique instance id",
        instanceId == thingKeyInstanceId);

    Map.Entry<Thing, Object> entry = reflectEntry(map, thingKey);

    assertSame("The reflected instance should be the original",
        thing2, entry.getKey());
    assertTrue("The reflected instance should be the original",
        instanceId == entry.getKey()._instanceId);
  }

  @SuppressWarnings("unchecked")
  private Map.Entry<Thing, Object> reflectEntry(
      final HashMap<Thing, Object> map, final Thing thingKey)
      throws IllegalAccessException, InvocationTargetException,
                NoSuchMethodException {

    Method getEntryMethod = HashMap.class.getDeclaredMethod(
        "getEntry", Object.class);
    getEntryMethod.setAccessible(true);
    return (Map.Entry<Thing, Object>)getEntryMethod.invoke(map, thingKey);
  }

  @SuppressWarnings("unchecked")
  private HashMap<Thing, Object> reflectMap(HashSet<Thing> set)
      throws NoSuchFieldException, IllegalAccessException {

    Field mapField = HashSet.class.getDeclaredField("map");
    mapField.setAccessible(true);
    return (HashMap<Thing, Object>)mapField.get(set);
  }

  private static class Thing {

    private static int _counter;

    private int _i;
    private int _instanceId = _counter++;

    Thing(int i) {
      _i = i;
    }

    @Override
    public boolean equals(final Object other) {
      return ((Thing)other)._i == _i;
    }

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

I saw an interesting post on JavaBlogs about a HashSet puzzler. The problem posed was to find the original instance in a HashSet given a new instance that’s equal to...