-1
\$\begingroup\$

I am implementing an IEqualityComparer for Dictionary objects and am looking for input on a couple of different approaches. I define equality in this case to be that both dictionaries contain the same set of KeyValuePair's as defined by equality of the hash value for the respective keys and values.

The first generates a hash value by XORing all of the keys and value in both dictionaries and comparing them. The other uses the HashSet collection and its SymetricExceptWith method. Are these functionally equivalent and are the pros/cons to either approach or better ways to accomplish this. Both approaches are working for my test cases.

GetHashCode approach:

class DictionaryComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
{
    public DictionaryComparer()
    {
    }

    public bool Equals(IDictionary<TKey, TValue> x, IDictionary<TKey, TValue> y)
    {
        // fail fast if count are not equal
        if (x.Count != y.Count)
            return false;
        return GetHashCode(x) == GetHashCode(y);
    }

    public int GetHashCode(IDictionary<TKey, TValue> obj)
    {
        int hash = 0;

        foreach (KeyValuePair<TKey, TValue> pair in obj)
        {
            int key = pair.Key.GetHashCode(); // key cannot be null
            int value = pair.Value != null ? pair.Value.GetHashCode() : 0;
            hash ^= ShiftAndWrap(key, 2) ^ value;
        }

        return hash;
    }

    private int ShiftAndWrap(int value, int positions)
    {
        positions = positions & 0x1F;

        // Save the existing bit pattern, but interpret it as an unsigned integer. 
        uint number = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0);
        // Preserve the bits to be discarded. 
        uint wrapped = number >> (32 - positions);
        // Shift and wrap the discarded bits. 
        return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) | wrapped), 0);
    }
}

HashSet approach:

class DictionaryComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
{
    public DictionaryComparer()
    {
    }

    public bool Equals(IDictionary<TKey, TValue> x, IDictionary<TKey, TValue> y)
    {
        if (x.Count != y.Count)
            return false;

        HashSet<KeyValuePair<TKey, TValue>> set = new HashSet<KeyValuePair<TKey, TValue>>(x);
        set.SymmetricExceptWith(y);
        return set.Count == 0;
    }
}
\$\endgroup\$

closed as off-topic by Jeff Vanzella, Jamal, Nikita B, Aseem Bansal, mheinzerling Aug 28 '13 at 13:02

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ I think Programmers would be a better fit for this question. \$\endgroup\$ – Jeff Vanzella Aug 27 '13 at 21:35
  • 4
    \$\begingroup\$ “as defined by equality of the hash value” No, no, no! You can't compare values just based on their hash codes. You need to compare them based on Equals() not on GetHashCode(). GetHashCode() is for use in hash tables, nothing else. \$\endgroup\$ – svick Aug 27 '13 at 21:56
5
\$\begingroup\$

A 32-bit hash returned by GetHashCode has 2^32 possible values, with a probability distribution dependent on the hashing function. If there are more than 2^32 possible input values then you will get collisions (see here). And while we like to think collisions are rare, they turn up a lot more frequently than we like to think. It gets worse when people are actively attacking you through your hashing function.

@svick is correct that you can't use a hash code to compare objects for equality. All you can be certain of (assuming a consistent hash implementation) is that two objects with different hashes are not equal. No other guarantee is given.

Depending on the cost of generating the hashes, you might actually be better off not using them in them in this instance.

The only really guaranteed equality test for a pair of Dictionary instances is to examine their contents.

The simple shortcuts you can implement:

  • Check if either instance is null (it happens)
  • Check if both input Dictionary instances are the same instance
  • Check if the counts differ

The other slight speed improvement is to check the keys first. Often checking the keys is a faster operation than checking the values.

Something like:

public bool Equals<TKey, TValue>(IDictionary<TKey, TValue> x, IDictionary<TKey, TValue> y)
{
    // early-exit checks
    if (null == y)
        return null == x;
    if (null == x)
        return false;
    if (object.ReferenceEquals(x, y))
        return true;
    if (x.Count != y.Count)
        return false;

    // check keys are the same
    foreach (TKey k in x.Keys)
        if (!y.ContainsKey(k))
            return false;

    // check values are the same
    foreach (TKey k in x.Keys)
        if (!x[k].Equals(y[k])
            return false;

    return true;
}

Adding a loop to check for hash inequality might improve the speed. Try it and see.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.