关于.net：比较两个集合的相等性，而不管它们中的项目顺序如何

Comparing two collections for equality irrespective of the order of items in them

我想比较两个集合(在C中)，但我不确定如何有效地实现这一点。

我已经读过另一个关于Enumerable.SequenceEqual的文章，但这并不是我想要的。

在我的例子中，如果两个集合都包含相同的项(无论顺序如何)，那么它们将相等。

例子：

1
2
3
4

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

collection1 == collection2; // true

我通常要做的是遍历一个集合中的每个项，并查看它是否存在于另一个集合中，然后遍历另一个集合中的每个项，并查看它是否存在于第一个集合中。(我从比较长度开始)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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

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

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

这与我的实现是一样的。我应该只计算每个项目被发现的次数，并确保两个集合中的计数相等吗？

这些例子是用某种C(我们称之为伪C)，但是用你想要的任何语言给出你的答案，这并不重要。

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

事实证明，微软已经在其测试框架中涵盖了这一点：collectionassert.areequivalent

Remarks

Two collections are equivalent if they
have the same elements in the same
quantity, but in any order. Elements
are equal if their values are equal,
not if they refer to the same object.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

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.OrderBy(x => x))
hash = hash * 23 + (val?.GetHashCode() ?? 42);

return hash;
}
}

样品使用情况：

1
2
3

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

1
2
3
4

var comp = new MultiSetComparer<string>();
Console.WriteLine(comp.Equals(new[] {"a","b","c
<div class="suo-content">[collapse title=""]<ul><li>谢谢你的回答，我不知道微软已经把它覆盖了。实际上，我在顶部使用了答案的变体，它允许我定义如何比较元素的相等性和检查空值。</li><li>没问题。为了支持getElementCounts()中t-的自定义相等定义，也可以很容易地将ieQualityComparer<t>参数添加到上述实现中，只需使用接受ieQualityComparer<t>的字典ctor即可。</li><li>nunit还具有collectionassert.areequivalent()方法。我很好奇哪一个先来，是女士还是女士。</li><li>MS似乎可以追溯到Visual Studio 2005…不知道努尼特的事</li><li>@波特曼-对不起，我忘了你的问题了！最直接的用法是自己比较两个集合：<wyn>new CollectionComparer<int>().Equals(intList1, intList2)</wyn>。还有许多集合将<wyn>IEqualityComparer</wyn>作为ctor参数，用于定义集合范围内的相等含义。例如，请参见：msdn.microsoft.com/en-us/library/ms132072.aspx</li><li>这很好，因为它适用于IEnumerable。使用collectionassert.areequal和collectionassert.areequivalent，可能需要将IEnumerable转换为ICollection。例如，collectionassert.areequivalent(new hashset<int>(new[]1，2，3)，new hashset<int>(new[]1，2，3))不会编译，但collectionassert.areequalent(new hashset<int>(new[]1，2，3).tolist()，new hashset<int>(new[]1，2，3).tolist())将编译。</li><li>我不是百分之百确定，但我认为你的回答违反了微软对逆向工程的使用条款。</li><li>这不是正确的解决方案。此解决方案比较对象的哈希代码，但请注意，在实现对象哈希代码重写方法时，您的哈希仅基于非更改字段(如ID)，而不是基于所有字段，因为您拥有相等的字段。因此，对于集合中包含具有多个字段的对象的位置，此方法不适用。</li><li>@Jamesroeiter请阅读Eric Lippert的gethashcode指南和规则：blogs.msdn.com/b/ericlippet/archive/2011/02/28/&hellip；-特别是"rule:equal items have equal hashes"</li><li>您好，Ohad，请阅读主题stackoverflow.com/questions/371328/&hellip；中的以下长时间辩论。如果您更改对象哈希代码，而它在哈希集中，它将中断哈希集的正确操作，并可能导致异常。规则如下：如果两个对象相等-它们必须具有相同的哈希代码。如果两个对象具有相同的哈希代码，则它们不必相等。哈希代码必须在整个对象的生命周期内保持不变！这就是为什么你的激励是可以接受的和不平等的。</li><li>而且，在埃里克的文章中，他也和我持有相同的观点："如果两个对象相等，那么它们必须具有相同的哈希代码；或者，等价地说，如果两个对象具有不同的哈希代码，那么它们必须不相等。"但这并不是说，如果它们具有相同的哈希代码，那么它们必须相等，equalisty是相对的，它可能是相同的实体bu。状态不同。在所有对象状态都是最终状态的情况下，测试框架会使用您的答案，这对于运行时来说不是一个好的解决方案。你好，詹姆斯</li><li>@也许我的评论有误导性。当字典遇到它已经包含的哈希代码时，它会检查与<wyn>EqualityComparer</wyn>的实际相等性(无论是您提供的还是<wyn>EqualityComparer.Default</wyn>，您可以检查reflector或引用源来验证这一点)。如果在该方法运行时对象发生更改(尤其是哈希代码更改)，则结果是意外的，但这意味着该方法在此上下文中不是线程安全的。</li><li>我不同意，我认为，这意味着要使该方法工作，您必须以错误的方式实现get hashcode——基于所有对象的字段，因为该方法的目的是检查两个序列是否在深度上相等。因此，如果使用此方法，则必须以一种会导致系统失败的方式来强制GetHashCode。而实现gethashcode的正确方法仅基于不可更改对象的字段，如实体ID，在比较两个序列的深度相等性时，这些字段将不起作用。</li><li>@jamesroeiter假设x和y是我们要比较的两个对象。如果它们有不同的哈希代码，我们知道它们是不同的(因为相等的项有相同的哈希代码)，并且上述实现是正确的。如果它们具有相同的hashcode，字典实现将使用指定的<wyn>EqualityComparer</wyn>(如果没有指定，则使用<wyn>EqualityComparer.Default</wyn>)检查实际的相等性，并再次检查实现是否正确。</li><li>如果集合包含相同的值，但顺序不同，则它们不相等-它们是等效的-如果方法名是<wyn>public bool AreEquivalent(IEnumerable<T> first, IEnumerable<T> second)</wyn>，则没有争论。</li><li>@cadbloke由于<wyn>IEqualityComparer<T></wyn>接口的原因，该方法必须命名为<wyn>Equals</wyn>。您应该看到的是比较器本身的名称。在这种情况下，这是有意义的<wyn>MultiSetComparer</wyn>。</li><li>啊，是的，对不起。我忽略了需要您调用它<wyn>Equals</wyn>的接口实现。谢谢。</li><li>微软的<wyn>GetHashCode</wyn>在这里针对碰撞率而不是<wyn>GetHashCode</wyn>调用本身的性能进行了优化(通过在<wyn>GetHashCode</wyn>方法中对可枚举的进行排序，它必然处于较慢的一边)。你应该时刻考虑你的数据，自己做决定。如果排序逻辑变慢，那么只需<wyn>list.Sum(x => x.GetHashCode())</wyn>就可以了(尽管由于求和不是一个好的哈希代码，所以会导致更高的冲突)。我说测试一下你的数据。</li><li><wyn>GetHashCode</wyn>实现包含一个bug：如果<wyn>val</wyn>是<wyn>null</wyn>(即如果集合包含<wyn>null</wyn>元素)，它将失败。</li><li>@virtlink良好捕获，已修复</li><li>正如用户nawfal所指出的，您可以简单地求和哈希代码，因为加法是可互换的。似乎您希望由自己的哈希方法提供额外的哈希冲突保护，但也可能希望在哈希计算中包含空值。例如，<wyn>hash = hash * 23 + (val != null ? val.GetHashCode() : 42)</wyn>。</li><li>@virtlink足够公平-再次更新</li><li>@Ohadschneider感谢你的回答。但我如何实际使用您的答案来比较两个自定义对象列表(忽略顺序)。我已经为这两个对象创建了IEqualityComparer。(在我的例子中，它们是具有x、y和z值的3dpoints)。非常感谢澄清。</li><li>@我在答案中加了几个样本，希望能澄清你的问题。我还添加了一个构造函数，它允许您传入您的<wyn>IEqualityComparer<T></wyn>(参见最后一个示例)。或者，您可以让您的类实现<wyn>IEquatable<T></wyn>(或者更不优选<wyn>Equals</wyn>和<wyn>GetHashCode</wyn>，这样当内部字典(msdn.microsoft.com/en-us/library/x525za90(v=vs.110).aspx)使用默认的通用相等比较器时，将使用您的实现(msdn.microsoft.com/en-us/library/ms224763(v=vs.110)ASPX。</li></ul>[/collapse]</div><hr><P>一个简单且相当有效的解决方案是对两个集合进行排序，然后比较它们是否相等：</P>[cc]bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));

这个算法是O(n*logn)，而上面的解是O(n^2)。

如果集合具有某些属性，则可以实现更快的解决方案。例如，如果两个集合都是哈希集，则它们不能包含重复项。此外，检查哈希集是否包含某些元素的速度非常快。在这种情况下，类似于您的算法可能是最快的。

创建字典"dict"，然后为第一个集合中的每个成员执行dict[member]++；

然后，以相同的方式循环第二个集合，但对于每个成员，请执行dict[member]--。

最后，循环字典中的所有成员：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

private bool SetEqual (List<int> left, List<int> right) {

if (left.Count != right.Count)
return false;

Dictionary<int, int> dict = new Dictionary<int, int>();

foreach (int member in left) {
if (dict.ContainsKey(member) == false)
dict[member] = 1;
else
dict[member]++;
}

foreach (int member in right) {
if (dict.ContainsKey(member) == false)
return false;
else
dict[member]--;
}

foreach (KeyValuePair<int, int> kvp in dict) {
if (kvp.Value != 0)
return false;
}

return true;

}

编辑：据我所知，这与最有效的算法的顺序相同。该算法是O(n)，假设字典使用O(1)查找。

这是我的(受到d.jennings的严重影响)比较方法的一般实现(在c中)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
/// <summary>
/// Compares the content of two collections for equality.
/// </summary>
/// <param name="foo">The first collection.</param>
/// <param name="bar">The second collection.</param>
/// <returns>True if both collections have the same content, false otherwise.</returns>
public bool Execute(ICollection<T> foo, ICollection<T> bar)
{
// Declare a dictionary to count the occurence of the items in the collection
Dictionary<T, int> itemCounts = new Dictionary<T,int>();

// Increase the count for each occurence of the item in the first collection
foreach (T item in foo)
{
if (itemCounts.ContainsKey(item))
{
itemCounts[item]++;
}
else
{
itemCounts[item] = 1;
}
}

// Wrap the keys in a searchable list
List<T> keys = new List<T>(itemCounts.Keys);

// Decrease the count for each occurence of the item in the second collection
foreach (T item in bar)
{
// Try to find a key for the item
// The keys of a dictionary are compared by reference, so we have to
// find the original key that is equivalent to the"item"
// You may want to override".Equals" to define what it means for
// two"T" objects to be equal
T key = keys.Find(
delegate(T listKey)
{
return listKey.Equals(item);
});

// Check if a key was found
if(key != null)
{
itemCounts[key]--;
}
else
{
// There was no occurence of this item in the first collection, thus the collections are not equal
return false;
}
}

// The count of each item should be 0 if the contents of the collections are equal
foreach (int value in itemCounts.Values)
{
if (value != 0)
{
return false;
}
}

// The collections are equal
return true;
}
}

您可以使用哈希集。看看setEquals方法。

编辑：我一提出这只适用于集合就意识到了——它不能正确处理具有重复项的集合。例如1、1、2和2、2、1从该算法的角度来看是相等的。但是，如果您的集合是集合(或者可以用这种方式测量它们的相等性)，我希望您发现下面的内容有用。

我使用的解决方案是：

1	return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;

Linq在封面下做字典的事情，所以这也是O(N)。(注意，如果集合大小不同，则为O(1)。

我使用丹尼尔建议的"setequal"方法、igor建议的orderby/sequenceequals方法和我的建议进行了一次健全性检查。结果如下，显示igor为O(n*logn)，Mine和Daniel为O(n)。

我认为Linq Intersect代码的简单性使它成为首选的解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

__Test Latency(ms)__
N, SetEquals, OrderBy, Intersect
1024, 0, 0, 0
2048, 0, 0, 0
4096, 31.2468, 0, 0
8192, 62.4936, 0, 0
16384, 156.234, 15.6234, 0
32768, 312.468, 15.6234, 46.8702
65536, 640.5594, 46.8702, 31.2468
131072, 1312.3656, 93.7404, 203.1042
262144, 3765.2394, 187.4808, 187.4808
524288, 5718.1644, 374.9616, 406.2084
1048576, 11420.7054, 734.2998, 718.6764
2097152, 35090.1564, 1515.4698, 1484.223

在没有重复和顺序的情况下，可以使用以下EqualityComparer将集合作为字典键：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class SetComparer<T> : IEqualityComparer<IEnumerable<T>>
where T:IComparable<T>
{
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == second)
return true;
if ((first == null) || (second == null))
return false;
return first.ToHashSet().SetEquals(second);
}

public int GetHashCode(IEnumerable<T> enumerable)
{
int hash = 17;

foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();

return hash;
}
}

这里是我使用的tohashset()实现。哈希代码算法来自于有效的Java(通过乔恩SKET)。

1
2
3
4
5

static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
var setXOR = new HashSet<T>(set1);
setXOR.SymmetricExceptWith(set2);
return (setXOR.Count == 0);
}

解决方案需要.NET 3.5和System.Collections.Generic命名空间。根据微软的说法，SymmetricExceptWith是一个O(n+m)操作，n代表第一组元素的数量，m代表第二组元素的数量。如果需要的话，可以向该函数添加一个相等比较器。

Why not use .Except()

1
2
3
4
5
6
7
8
9

// Create the IEnumerable data sources.
string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");
// Create the query. Note that method syntax must be used here.
IEnumerable<string> differenceQuery = names1.Except(names2);
// Execute the query.
Console.WriteLine("The following lines are in names1.txt but not names2.txt");
foreach (string s in differenceQuery)
Console.WriteLine(s);

http://msdn.microsoft.com/en-us/library/bb397894.aspx

如果你应该使用，你可以使用shouldallbe和contains。

1
2
3
4

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

collection1.ShouldAllBe(item=>collection2.Contains(item)); // true

最后，您可以编写一个扩展。

1
2
3
4
5
6
7

public static class ShouldlyIEnumerableExtensions
{
public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}

更新

shouldbe方法上存在可选参数。

1	collection1.ShouldBe(collection2, ignoreOrder: true); // true

一个重复的排序帖子，但请查看我的收集比较解决方案。很简单：

这将执行相等比较，而不考虑顺序：

1
2
3

var list1 = new[] {"Bill","Bob","Sally" };
var list2 = new[] {"Bob","Bill","Sally" };
bool isequal = list1.Compare(list2).IsSame;

这将检查是否添加/删除了项目：

1
2
3
4
5
6

var list1 = new[] {"Billy","Bob" };
var list2 = new[] {"Bob","Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added; //Sally
var inbothlists = diff.Equal; //Bob

这将看到字典中的哪些项发生了更改：

1
2
3
4
5
6

此处为原始邮件。

这是我对ohadsc答案的扩展方法变体，以防对某人有用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

static public class EnumerableExtensions
{
static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second)
{
if ((first == null) != (second == null))
return false;

if (!object.ReferenceEquals(first, second) && (first != null))
{
if (first.Count() != second.Count())
return false;

if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second))
return false;
}

return true;
}

private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second)
{
int firstCount;
int secondCount;

var firstElementCounts = GetElementCounts<T>(first, out firstCount);
var secondElementCounts = GetElementCounts<T>(second, out secondCount);

if (firstCount != secondCount)
return true;

foreach (var kvp in firstElementCounts)
{
firstCount = kvp.Value;
secondElementCounts.TryGetValue(kvp.Key, out secondCount);

if (firstCount != secondCount)
return true;
}

return false;
}

private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount)
{
var dictionary = new Dictionary<T, int>();
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;
}

static private int GetHashCode<T>(IEnumerable<T> enumerable)
{
int hash = 17;

foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();

return hash;
}
}

这里有一个比这个更好的解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static bool HasSameElementsAs<T>(
this IEnumerable<T> first,
IEnumerable<T> second,
IEqualityComparer<T> comparer = null)
{
var firstMap = first
.GroupBy(x => x, comparer)
.ToDictionary(x => x.Key, x => x.Count(), comparer);

var secondMap = second
.GroupBy(x => x, comparer)
.ToDictionary(x => x.Key, x => x.Count(), comparer);

if (firstMap.Keys.Count != secondMap.Keys.Count)
return false;

if (firstMap.Keys.Any(k1 => !secondMap.ContainsKey(k1)))
return false;

return firstMap.Keys.All(x => firstMap[x] == secondMap[x]);
}

埃里克森几乎是对的：既然你想在重复次数上匹配，你就需要一个袋子。在爪哇，这看起来像：

1	(new HashBag(collection1)).equals(new HashBag(collection2))

我相信C有一个内置的集合实现。我将首先使用它；如果性能有问题，您可以始终使用不同的集合实现，但使用相同的集合接口。

这个简单的解决方案强制IEnumerable的泛型类型实现IComparable。因为OrderBy的定义。

如果您不想做这样的假设，但仍然想使用这个解决方案，您可以使用下面的代码：

1 2	bool equal = collection1.OrderBy(i => i?.GetHashCode()) .SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));

在许多情况下，唯一合适的答案是igor ostrovsky中的一个，其他答案是基于对象散列代码的。但是，当您为一个对象生成哈希代码时，您这样做只是基于对象的不可变字段(例如对象ID字段(对于数据库实体))。为什么在重写Equals方法时重写GetHashCode很重要？

这意味着，如果比较两个集合，即使不同项的字段不相等，比较方法的结果也可能为真。要深入比较集合，需要使用igor方法并实现IEquality。

请阅读我和施奈德先生在他投票最多的帖子上的评论。

詹姆斯

这个问题有很多解决办法。如果你不在乎复制品，你就不必两者都排序。首先，确保它们具有相同数量的项目。在那之后是一个集合。然后，binsearch排序集合中第二个集合中的每个项。如果找不到给定的项目，请停止并返回false。这一点的复杂性：-排序第一个集合：nlog(n)-从第二个搜索到第一个：nlog(n)所以你最终得到2*n*log(n)，假设它们是匹配的，你可以查找所有东西。这类似于对两者进行排序的复杂性。如果有差异，这也能让你提前停止。但是，请记住，如果在进行比较之前对两者都进行了排序，并且尝试使用类似qsort的方法进行排序，那么排序将更加昂贵。对此有一些优化。另一种选择是，对于您知道元素范围的小集合来说，使用位掩码索引是很好的选择。这将给你一个O(N)的表现。另一种选择是使用哈希并查找它。对于小的集合，进行排序或位掩码索引通常要好得多。hashtable的缺点是位置更差，所以请记住这一点。再说一遍，只有当你不在乎重复的时候。如果您想说明重复项，请对两者进行排序。

考虑到IEnumerable中的重复(如果集合不可取或不可能)和"忽略顺序"，您应该能够使用.GroupBy()。

我不是复杂性度量方面的专家，但我的基本理解是这应该是O(N)。我理解O(n^2)是在另一个O(n)操作中执行O(n)操作，如ListA.Where(a => ListB.Contains(a)).ToList()。对列表B中的每个项进行相等性评估。

如我所说，我对复杂性的理解是有限的，所以如果我错了，请纠正我的看法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public static bool IsSameAs<T, TKey>(this IEnumerable<T> source, IEnumerable<T> target, Expression<Func<T, TKey>> keySelectorExpression)
{
// check the object
if (source == null && target == null) return true;
if (source == null || target == null) return false;

var sourceList = source.ToList();
var targetList = target.ToList();

// check the list count :: { 1,1,1 } != { 1,1,1,1 }
if (sourceList.Count != targetList.Count) return false;

var keySelector = keySelectorExpression.Compile();
var groupedSourceList = sourceList.GroupBy(keySelector).ToList();
var groupedTargetList = targetList.GroupBy(keySelector).ToList();

// check that the number of grouptings match :: { 1,1,2,3,4 } != { 1,1,2,3,4,5 }
var groupCountIsSame = groupedSourceList.Count == groupedTargetList.Count;
if (!groupCountIsSame) return false;

// check that the count of each group in source has the same count in target :: for values { 1,1,2,3,4 } & { 1,1,1,2,3,4 }
// key:count
// { 1:2, 2:1, 3:1, 4:1 } != { 1:3, 2:1, 3:1, 4:1 }
var countsMissmatch = groupedSourceList.Any(sourceGroup =>
{
var targetGroup = groupedTargetList.Single(y => y.Key.Equals(sourceGroup.Key));
return sourceGroup.Count() != targetGroup.Count();
});
return !countsMissmatch;
}