What is the best way to derive a unique dictionary key for an object?

Question

PROBLEM

I need a method for generating keys for a dictionary of objects. However, I have a few requirements that are making this a bit difficult. Here is the scenario:

1. The Dictionary is a list of reference type objects.
2. The Dictionary is private, within a static class.
3. External code needs to obtain a key to specific objects within the dictionary, but MUST NOT have access to the objects within the dictionary, or the dictionary itself.
4. Given a specific object within the dictionary, the key must be consistently re-calculable/derivable. If properties on the object change, the key MUST NOT CHANGE.
5. Conversely, if a new object is created that can evaluate to being equal to another object within the dictionary, the key must be different since they are two, separate objects.
6. This implementation must be thread safe.

NON-SOLUTIONS

Solution #1
All .Net objects contain a method called .GetHashCode(), which returns an integer value. You can use this as a key.

Problem
Not possible. MSDN States:

Two objects that are equal return hash codes that are equal.

This breaks req #5 and I assume (but not tested) req. #4. I would love to have an option like this, if it could meet these rules.

Solution #2
Convert the pointer to the object to an int and use that as a key.

Problem
This breaks the essence of req. #3. Passing pointers, and using them as keys doesn't feel safe.

Solution #3
Convert the pointer to the object to an integer hash the value and use the hash as a key.

Problem
Although this doesn't break any rules, I'd prefer to avoid accessing pointers since this would involve using unsafe code. I'm not opposed to using unsafe code if I have to, but I'd prefer to avoid it if at all possible.

CONCLUSION

Maybe my requirements are a bit picky. There has to be some reasonable way of deriving a key from a unique object. Has anyone ever experienced such a scenario and solved this dilemma?

Answer 1

1 The Dictionary is a list of ByRef objects.

Objects are always 'by reference' in .NET. This may be the beginning of the misunderstanding. Reference equality is what you need/want.

3 External code needs to obtain a key to specific objects within the dictionary, but MUST NOT have access to the objects within the dictionary, or the dictionary itself.

This is the real problem. Without it, a reference to the object itself would have worked. But the framework still provides all of your functionality, right off-the-shelf:

private Dictionary<object, MyClass> _myStore;

// add an item and return a key    
public object Add(MyClass item)
{
    object key = new object();
    _myStore.Add(key, item);
    return key;
}

And to satisfy req #4:

private Dictionary<object, MyClass> _itemForKey;    // was _myStore
private Dictionary<MyClass, object> _keyForItem;


// add an item and return a key    
public object Add(MyClass item)
{
    object key = new object();
    _itemForKey.Add(key, item);
    _keyForItem.Add(item, key);
    return key;
}

protected object DeriveKeyFromItem(MyClass item)
{
   return _keyForItem[item];
}

Note: these samples are not thread-safe (req 6), but that's a standard feature to resolve.

Answer 2

I think that your requirement boils down to that you want to compare and hash by reference equality. Using this as the IEqualityComparer<T> in your dictionary will do that, using RuntimeHelpers.GetHashCode and object.ReferenceEquals.

public class ReferenceEqualityComparer<T> : IEqualityComparer<T>
{
    public bool Equals(T x, T y)
    {
        return object.ReferenceEquals(x, y);
    }
    public int GetHashCode(T obj)
    {
        return System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj);
    }
}

Note that since pointers and references aren't the same, your reference shouldn't be usable as a pointer, reducing the risk of unsafe code using this inappropriately.

Answer 3

How about defining a structure something like:

public struct BlindIdentityToken : IEquatable<BlindIdentityToken>
{
    Object o;
    public BlindIdentityToken(Object obj)
    {
        o = obj;
    }
    public override int GetHashCode()
    {
        return System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(o);
    }
    public override bool Equals(object obj)
    {
        if (obj == null || obj.GetType() != typeof(BlindIdentityToken))
            return false;
        return ((BlindIdentityToken)obj).o == o;
    }
    public bool Equals(BlindIdentityToken other)
    {
        return o == other.o;
    }
}

Given a reference to an object, one may construct a BlindIdentityToken which will compare equal to any other BlindIdentityToken constructed for the same object, but will compare unequal to anything else. Because it is a structure type and implements IEquatable<BlindIdentityToken>, constructing a token and looking it up in a dictionary will not require a heap allocation. Because it uses RuntimeHelpers.GetHashCode() it should ignore any override of GetHashCode by the object whose reference is encapsulated, and because o is a private field, it is somewhat protected from outside code sneaking a reference to it.