Dictionary.ContainsKey() - How does it work?

Question

I've read the MSDN documentation on how Dictionary.ContainsKey() works, but I was wondering how it actually makes the equality comparison? Basically, I have a dictionary keyed to a reference type* and I want the ContainsKey() method to check a certain property of that reference type as its basis for determining if the key exists or not. For example, if I had a Dictionary(MyObject, int) and MyObject has a public property (of int) called "TypeID", could I get ContainsKey(MyObject myObject) to check to see if one of the keys has a TypeID that is equal to myObject? Could I just overload the == operator?

• The reference type is an object called "Duration" which holds a value (double Length); "Duration" is a base type used in my music program to denote how long a particular sound lasts. I derive classes from it which incorporate more sophisticated timing concepts, like Western musical time signatures, but want all of them to be comparable in terms of their length.

EDIT: As suggested, I implemented IEquitable on my object like so:

 public class Duration : IEquatable<Duration>
 {
    protected double _length;

    /// <summary>
    /// Gets or Sets the duration in Miliseconds.
    /// </summary>
    public virtual double Length
{
        get
        {
            return _length;
        }
        set
        {
            _length = value;
        }
    }

// removed all the other code that as it was irrelevant

    public override bool Equals(object obj)
    {
        Duration otherDuration = (Duration)obj;
        if (otherDuration._length == _length)
        {
            return true;
        }
        else
        {
            return false
        }
    }

}

Is this all I need to do?

Worry

You must overload GetHashCode and Equals as appropriate. == is not used at all. See other related questions - e.g. "tag:c# dictionary equals hashcode". – Gard

You must also ensure that your GetHashCode function always returns the same value for the entire lifetime of each object instance. You are then advised to make your reference objects immutable if you base the hash code on the property values. – Weaks

@Richard, I have edited my answer to include a commented code sample for your updated example. – Palais

Answer 1

EDIT: here is code for your updated example. Note: I find it a little odd that you expose the field as protected, and also have a virtual property that exposes the member. Under this scheme something could override Length resulting in equality that looks at _lenght to not behave as expected.

public class Duration : IEquatable<Duration>
{
    protected double _length;

    /// <summary>
    /// Gets or Sets the duration in Miliseconds.
    /// </summary>
    public virtual double Length
    {
        get { return _length; }
        set { _length = value; }
    }

    // removed all the other code that as it was irrelevant

    public bool Equals(Duration other)
    {
        // First two lines are just optimizations
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;

        return _length.Equals(other._length);
    }

    public override bool Equals(object obj)
    {
        // Again just optimization
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;

        // Actually check the type, should not throw exception from Equals override
        if (obj.GetType() != this.GetType()) return false;

        // Call the implementation from IEquatable
        return Equals((Duration) obj);
    }

    public override int GetHashCode()
    {
        // Constant because equals tests mutable member.
        // This will give poor hash performance, but will prevent bugs.
        return 0;
    }
}

---

See EqualityComparer.Default for information on the default IEqualityComparer used by the Dictionary class.

If you do not want to generally override GetHashCode and Equals on the class, or if you are unable to. There is an overload of the Dictionary constructor in which you can provide the specific IEqualityComparer to use.

It is a simple interface to implement, but you do need to be careful that you respect the contract for GetHashCode or you can end up with unexpected behavior.

public class MyObjectEqualityComparer : IEqualityComparer<MyObject>
{
    public bool Equals(MyObject x, MyObject y)
    {
        return x.TypeID == y.TypeID;
    }

    public int GetHashCode(MyObject obj)
    {
        return obj.TypeID; //Already an int
    }
}

to use it just go

new Dictionary<MyObject, int>(new MyObjectEqualityComparer());   

If you want to use the default IEqualityComparer you need to provide roughly the same methods on MyObjectEqualityComparer. You can avoid overriding object.Equals() if you implement IEquatable. However I would strongly discourage it because doing so can create some surprising behavior. You are better of overriding Equals so that you have consistent behavior for all calls to Equals and have hashing that properly matches Equals. I have had to fix a bug in inherited code caused by a past developer only implementing IEquatable.

Palais

You'd better return TypeID.GetHashCode() – Birdseed

@2Kay. TypeID is an int. What value do I get by calling GetHashCode() an int? – Palais

I had just arrived at something like this myself, although your version of it is much much better. A couple questions though: why not just return the hash code of the double length instead of zero? What kind of bugs can appear? Also, are you having an object do a null reference check against itself with "if (ReferenceEquals(this, other)) return true"? If so, and it is null (is that possible?), why do you want to return true instead of false? – Worry

@Richard. I do not quite understand your second question. Are you asking if this can be null? The simple answer is no. – Palais

@Worry As to the first question here is an possibility, I am using HashMap rather than Dictionary for brevity (both are implemented using hashing). var d = new Duration { Length = 5 }; var map = new HashMap<Duration>(); map.Add(d); map.Contains(d)/*returns true (expected)*/; d.Length = 7; map.Contains(d)/*returns false (unexpected)*/; You never removed d from map so you would expect it to still be there, but you changed the hash code so when it looks for the hash code of the modified d in map it does not find it. You may want to lookup hashing or hash table. – Palais

Never mind my second question, I realize now that I misread the code. I thought it said "ReferenceEquals(this, null)". What you wrote makes sense now: you're checking to see if they are the exact same object before investing more time seeing if they are the same by checking the length property. – Worry

+1 for: "There is an overload of the Dictionary constructor in which you can provide the specific IEqualityComparer to use." – Rodriques

Answer 2

Internally Dictionary uses EqualityComparer. Firstly it will check whether key implements IEquatable. If key doesn't implement this interface, it will call Equals method.

Mirabelle

It doesn't check this. And it always call GetHashCode (to navigate to the chain of buckets) and then Equals (to directly compare) methods of EqualityComparer which can be specified or default. – Birdseed

@2kay, I meant that EqualityComparer checks whether key implements IEquatable. – Mirabelle

I've got it. But seems like it doesn't really check that. Whatever says msdn, searching for IEquatable in decompiled Dictionary (and all of default EqualityComparers too) did not take any results. – Birdseed

@2kay, Check EqualityComparer<T>.CreateComparer() method. It contains line if (typeof (IEquatable<T>).IsAssignableFrom((Type) genericParameter1)). – Mirabelle

Hm, really. Just to choose comparer. My apologies then :) – Birdseed