最近在工作中遇到了一個小的功能，就是需要向一個服務發送請求命令，需要判斷請求是否發生變化，如果發生變化了，則重新請求。該問題實際上就是判斷兩個集合是否相等，只需要記錄最後一次請求的元素的集合，然後將其和最新一次進行比較是否相等。需要說明的是這裡定義的集合相等是指：兩個集合如果元素值一樣並且出現的次數也一樣，即使順序不一樣也認為是相等，比如集合A={1,2,3,4,4,5} 集合B={1,4,4,2,3,5} 這兩個集合也認為是相等的。後面討論的集合相等都是基於這一假設的。
就這麼個簡單的問題，也有不同種解決方法，這裡和大家分享一下。
方法一 使用Dictionary計數來實現
這種方法思路很簡單，創建一個Dictionary對象，將第一個集合中的元素作為key添加到Dictionary中，value即為出現的次數。然後遍歷第二個集合，如果包含相同的key，則value減1，如果不好含，則直接返回false，表示兩個集合不同。最後，如果Dictionary中所有key對應的value都為0即表示兩個集合相等，否則不相等。
/// <summary>/// 判斷兩個集合是否相等，相等 表示元素值及出現的次數一樣即可，順序可以不一樣。/// </summary>/// <typeparam name="T"></typeparam>/// <param name="list1"></param>/// <param name="list2"></param>/// <returns></returns>public static bool ScrambledEquals<T>(IEnumerable<T> list1, IEnumerable<T> list2)
{//如果集合個數不相等，則集合不同 if (list1.Count() != list2.Count()) return false;var cnt = new Dictionary<T, int>();foreach (T s in list1)
{if (cnt.ContainsKey(s))
{
cnt[s]++;
}else {
cnt.Add(s, 1);
}
}foreach (T s in list2)
{if (cnt.ContainsKey(s))
{
cnt[s]--;
}else //如果第二個集合中有第一個集合中未包含的元素，表示兩個集合不同 {return false;
}
}return cnt.Values.All(c => c == 0);
}
算法需要對象實現IEquatable接口，而該接口一般對象均默認實現。
以上算法的效率是很高的，時間復雜度為O(N)，因為對Dictionary的查找時間復雜度為O(1)，所以主要時間都花在遍歷集合上。
以上方法對.NET不同的版本都兼容，如果是.NET 2.0版本也非常容易改造，只需要把最後一句代碼改為遍歷即可。由於項目原因，本人開發環境為2.0所以才用的是該方法。
方法二 使用IEnumerable的SequenceEqual 擴展方法
在.NET 3.5 中，比較集合元素的相等性有了新的方法，IEnumerable接口提供了名為SequenceEqual的方法，該方法用於判斷兩個序列是否順序相等，即兩個源序列的長度相等，且其相應元素相等。
我們可以先對兩個集合進行排序，然後直接調用Enumerable.SequenceEqual 方法即可，這大概是最簡單的實現方法了。
public static bool ScrambledEqualsUsingSequenceEqual<T>(IEnumerable<T> list1, IEnumerable<T> list2)
{return Enumerable.SequenceEqual(list1.OrderBy(t => t), list2.OrderBy(t => t));
}
需要注意的是，如果要自定義相等特性，需要實現IEquatable<T>接口，並提供自定義的Equal和GetHashCode實現。
方法三 使用CollectionAssert.AreEquivalent方法
在Visual Studio的單元測試框架中，位於Microsoft.VisualStudio.TestTools.UnitTesting命名空間下，以及在NUnit中都存在有CollectionAssert.AreEquivalent方法，該方法的解釋是：
“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.”
從定義可以看出 這正是我們定義的集合相等性。所以可以直接使用該方法。需要注意的是該命名空間位於Microsoft.VisualStudio.QualityTools.UnitTestFramework.dll這個dll中。
本欄目
使用Reflector工具，可以查看其具體實現，對其代碼進行簡單修改可以看到其原理如下：
public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{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;var firstCollection = first as ICollection<T>;var secondCollection = second as ICollection<T>;if (firstCollection != null && secondCollection != null)
{if (firstCollection.Count != secondCollection.Count)return false;if (firstCollection.Count == 0)return true;
}return !HaveMismatchedElement(first, second);
}private static bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
{int firstCount;int secondCount;var firstElementCounts = GetElementCounts(first, out firstCount);var secondElementCounts = GetElementCounts(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(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;
}public int GetHashCode(IEnumerable<T> enumerable)
{int hash = 17;foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();return hash;
}
}
其實現方法原理和第一個方法類似，首先是進行了一系列條件判斷，是否為空，元素個數是否相等等等。然後也是創建一個Dictionary進行元素個數計算，並比較。
作者： yangecnu（yangecnu's Blog on 博客園）
出處：http://www.cnblogs.com/yangecnu/
