Лучший способ сравнить два словаря <T>на равенство - PullRequest
Новая
       51

Лучший способ сравнить два словаря <T>на равенство

5 голосов
/ 24 марта 2011

Это лучший способ создать компаратор для равенства двух словарей? Это должно быть точно. Обратите внимание, что Entity.Columns - это словарь KeyValuePair (строка, объект): 

public class EntityColumnCompare : IEqualityComparer<Entity>
{
    public bool Equals(Entity a, Entity b)
    {
        var aCol = a.Columns.OrderBy(KeyValuePair => KeyValuePair.Key);
        var bCol = b.Columns.OrderBy(KeyValuePAir => KeyValuePAir.Key); 

        if (aCol.SequenceEqual(bCol))
            return true;
        else
            return false;           
    }

    public int GetHashCode(Entity obj)
    {
        return obj.Columns.GetHashCode(); 
    }
}

Также не слишком уверен в реализации GetHashCode.

Спасибо!

Ответы [ 3 ]

8 голосов
/ 24 марта 2011

Вот что я бы сделал: 

    public bool Equals(Entity a, Entity b)
    {
        if (a.Columns.Count != b.Columns.Count)
            return false; // Different number of items

        foreach(var kvp in a.Columns)
        {
            object bValue;
            if (!b.Columns.TryGetValue(kvp.Key, out bValue))
                return false; // key missing in b
            if (!Equals(kvp.Value, bValue))
                return false; // value is different
        }
        return true;
    }

Таким образом, вам не нужно упорядочивать записи (это операция O (n log n) ): вы тольконужно перечислить записи в первом словаре ( O (n) ) и попытаться извлечь значения по ключу во втором словаре ( O (1) ), поэтому общая сложность O (n) .

Также обратите внимание, что ваш метод GetHashCode неверен: в большинстве случаев он будет возвращать разные значения для разных экземпляров словаря, даже если они имеют одинаковое содержимое.И если хеш-код отличается, Equals никогда не будет вызван ... У вас есть несколько вариантов для его правильной реализации, ни один из которых не идеален:

  • построить хеш-код из содержимого словаря:будет лучшим вариантом, но он медленный, и GetHashCode должен быть быстрым
  • всегда возвращать одно и то же значение, поэтому всегда будет вызываться Equals: очень плохо, если выЯ хочу использовать этот компаратор в хеш-таблице / словаре / хэш-наборе, потому что все экземпляры попадут в один и тот же сегмент, что приведет к доступу O (n) вместо O (1)
  • возвращает Count словаря (как предложено digEmAll): он не даст большого распределения, но все же лучше, чем всегда возвращать одно и то же значение, и он удовлетворяет ограничению для GetHashCode (т.е. объектовкоторые считаются равными, должны иметь одинаковый хеш-код; два «равных» словаря имеют одинаковое количество элементов, поэтому он работает)
2 голосов
/ 24 марта 2011

Нечто подобное приходит на ум, но может быть что-то более эффективное: 

public static bool Equals<TKey, TValue>(IDictionary<TKey, TValue> x, 
    IDictionary<TKey, TValue> y)
{
    return x.Keys.Intersect(y.Keys).Count == x.Keys.Count &&
        x.Keys.All(key => Object.Equals(x[key], y[key]));
}
1 голос
/ 24 марта 2011

Мне кажется, это хорошо, возможно, не самый быстрый, но работающий.

Вам просто нужно изменить неправильную реализацию GetHashCode.

Например, вы можете вернуть obj.Columns.Count.GetHashCode()

...