Is there an IdentityHashMap implementation that maintains insert order?

Question

I need a HashMap that (1) matches keys by Object reference, and (2) maintains insertion order when iterating

These functionalities are implemented in IdentityHashMap and LinkedHashMap separately.

Is there any way to get a data structure that suits my need? Either one that is present in Java standard OR 3rd party libraries (like Guava), OR by using some trick on LinkedHashMap maybe, so that it uses object reference for matching keys?

Answer 1

You can use Guava's Equivalence for this:

Equivalence<Object> equivalence = Equivalence.identity();
Map<Equivalence.Wrapper<Object>, Object> map = new LinkedHashMap<>();
map.put(equivalence.wrap(a), b);

Answer 2

It interested me, so I wrote an implementation.

public class IdentityLinkedHashMap<K, T>  extends AbstractMap<K,T> {

    static Equivalence<Object> equivalence = Equivalence.identity();

    private IdentityLinkedHashSet set = new IdentityLinkedHashSet();

    @Override
    public Set<Entry<K, T>> entrySet() {
        return set;
    }

    @Override
    public T put(K k, T t) {
        return set.innerMap.put( equivalence.wrap(k), t);
    }

    @Override
    public boolean containsKey(Object arg0) {
        return set.contains(arg0);
    }

    @Override
    public T remove(Object arg0) {
        return set.innerMap.remove(equivalence.wrap(arg0));
    }


    @Override
    public T get(Object arg0) {
        return set.innerMap.get(equivalence.wrap(arg0));
    }


    public class MyEntry implements Entry<K, T> {

        final Entry<Equivalence.Wrapper<K>, T> entry;

        public MyEntry(Entry<Wrapper<K>, T> entry) {
            this.entry = entry;
        }

        @Override
        public K getKey() {
            return entry.getKey().get();
        }

        @Override
        public T getValue() {
            return entry.getValue();
        }

        @Override
        public T setValue(T value) {
            return entry.setValue(value);
        }

    }


    public class IdentityLinkedHashSet extends AbstractSet<Entry<K,T>> {

        Map<Equivalence.Wrapper<K>, T> innerMap = new LinkedHashMap<>();

        @Override
        public Iterator<Entry<K, T>> iterator() {
            return Iterators.transform(innerMap.entrySet().iterator(), entry -> new MyEntry(entry));
        }

        @Override
        public boolean add(Entry<K, T> entry) {
            Wrapper<K> wrap = equivalence.wrap(entry.getKey());
            innerMap.put(wrap, entry.getValue());
            return true;
        }

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

        @Override
        public boolean contains(Object arg0) {
            return innerMap.containsKey(equivalence.wrap(arg0));
        }
    }