比较两个集合的相等性，而不考虑其中项目的顺序

小编典典

比较两个集合的相等性，而不考虑其中项目的顺序

all

我想比较两个集合（在 C# 中），但我不确定有效实现这一点的最佳方法。

就我而言，如果两个集合都包含相同的项目（无论顺序如何），它们将是相等的。

例子：

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1 == collection2; // true

我通常做的是遍历一个集合的每个项目，看看它是否存在于另一个集合中，然后循环遍历另一个集合的每个项目，看看它是否存在于第一个集合中。（我首先比较长度）。

if (collection1.Count != collection2.Count)
    return false; // the collections are not equal

foreach (Item item in collection1)
{
    if (!collection2.Contains(item))
        return false; // the collections are not equal
}

foreach (Item item in collection2)
{
    if (!collection1.Contains(item))
        return false; // the collections are not equal
}

return true; // the collections are equal

然而，这并不完全正确，而且它可能不是比较两个集合是否相等的最有效方法。

我能想到的一个错误的例子是：

collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}

这与我的实现相同。我应该只计算找到每个项目的次数并确保两个集合中的计数相等吗？

这些示例使用某种 C#（我们称其为伪 C#），但可以用任何您希望的语言给出答案，没关系。

注意： 为简单起见，我在示例中使用了整数，但我也希望能够使用引用类型的对象（它们不能正确地作为键，因为只比较对象的引用，而不是内容）。

阅读 63

2022-08-16

共1个答案

小编典典

事实证明，微软已经在其测试框架中包含了这一点：CollectionAssert.AreEquivalent

评论

如果两个集合具有相同数量的相同元素，但顺序不限，则它们是等价的。如果它们的值相等，则元素相等，而不是如果它们引用同一个对象。

使用反射器，我修改了 AreEquivalent() 背后的代码以创建相应的相等比较器。它比现有答案更完整，因为它考虑了空值，实现了
IEqualityComparer 并具有一些效率和边缘情况检查。另外，它是微软 :)

public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    private readonly IEqualityComparer<T> m_comparer;
    public MultiSetComparer(IEqualityComparer<T> comparer = null)
    {
        m_comparer = comparer ?? EqualityComparer<T>.Default;
    }

    public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
    {
        if (first == null)
            return second == null;

        if (second == null)
            return false;

        if (ReferenceEquals(first, second))
            return true;

        if (first is ICollection<T> firstCollection && second is ICollection<T> secondCollection)
        {
            if (firstCollection.Count != secondCollection.Count)
                return false;

            if (firstCollection.Count == 0)
                return true;
        }

        return !HaveMismatchedElement(first, second);
    }

    private bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
    {
        int firstNullCount;
        int secondNullCount;

        var firstElementCounts = GetElementCounts(first, out firstNullCount);
        var secondElementCounts = GetElementCounts(second, out secondNullCount);

        if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            var firstElementCount = kvp.Value;
            int secondElementCount;
            secondElementCounts.TryGetValue(kvp.Key, out secondElementCount);

            if (firstElementCount != secondElementCount)
                return true;
        }

        return false;
    }

    private Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount)
    {
        var dictionary = new Dictionary<T, int>(m_comparer);
        nullCount = 0;

        foreach (T element in enumerable)
        {
            if (element == null)
            {
                nullCount++;
            }
            else
            {
                int num;
                dictionary.TryGetValue(element, out num);
                num++;
                dictionary[element] = num;
            }
        }

        return dictionary;
    }

    public int GetHashCode(IEnumerable<T> enumerable)
    {
        if (enumerable == null) throw new 
            ArgumentNullException(nameof(enumerable));

        int hash = 17;

        foreach (T val in enumerable)
            hash ^= (val == null ? 42 : m_comparer.GetHashCode(val));

        return hash;
    }
}

示例用法：

var set = new HashSet<IEnumerable<int>>(new[] {new[]{1,2,3}}, new MultiSetComparer<int>());
Console.WriteLine(set.Contains(new [] {3,2,1})); //true
Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false

或者，如果您只想直接比较两个集合：

var comp = new MultiSetComparer<string>();
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","c","b"})); //true
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","b"})); //false

最后，您可以使用您选择的相等比较器：

var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true

2022-08-16