我有一个包含多个整数列表的HashSet-即HashSet<List<int>>
为了保持唯一性，我目前必须做两件事：1.手动循环现有列表，并使用SequenceEquals查找重复项。2.对各个列表进行排序，以使SequenceEquals当前有效。
有更好的方法吗？我可以为HashSet提供一个现有的IEqualityComparer，以便HashSet.Add()可以自动处理唯一性吗？
var hashSet = new HashSet<List<int>>();
for(/* some condition */)
{
List<int> list = new List<int>();
...
/* for eliminating duplicate lists */
list.Sort();
foreach(var set in hashSet)
{
if (list.SequenceEqual(set))
{
validPartition = false;
break;
}
}
if (validPartition)
newHashSet.Add(list);
}
IEnumerable<T>。添加之前，您仍然需要手动排序。可以将排序建立到比较器中，但是我认为这不是一个明智的选择。添加列表的规范形式似乎更明智。
此代码仅在.net 4中有效，因为它利用了通用差异。如果需要早期版本，则需要用IEnumerable替换List，或为集合类型添加第二个通用参数。
class SequenceComparer<T>:IEqualityComparer<IEnumerable<T>>
{
public bool Equals(IEnumerable<T> seq1,IEnumerable<T> seq2)
{
return seq1.SequenceEqual(seq2);
}
public int GetHashCode(IEnumerable<T> seq)
{
int hash=1234567;
foreach(T elem in seq)
hash=hash*37+elem.GetHashCode();
return hash;
}
}
void Main()
{
var hashSet = new HashSet<List<int>>(new SequenceComparer<int>());
List<int> test=new int[]{1,3,2}.ToList();
test.Sort();
hashSet.Add(test);
List<int> test2=new int[]{3,2,1}.ToList();
test2.Sort();
hashSet.Contains(test2).Dump();
}
HashSet<ReadOnlyCollection<>>，因为您不能允许列表更改并使设置谓词无效。然后，当您将集合添加到集合中时，就可以使用O（n）计算哈希码。然后进行O（n）测试以检查它是否已经存在于集合中，这是非常不常见的O（n ^ 2）最坏情况（如果所有散列都相等）。将计算出的哈希与集合一起存储。int[]将表现更好。另外，我假设列表包含重复项，否则您将只使用集合而不会有问题。 似乎将它们的内容添加到HashSet后不会改变很多。最终，您将不得不使用一个依靠SequenceEqual的比较器。但是您不必每次都这样做。取而代之或进行指数级的序列比较（例如，随着哈希集的增长，对每个现有成员执行SequenceEqual）-如果您预先创建了良好的哈希码，则可能只需进行很少的比较。尽管生成良好的哈希码的开销可能与执行SequenceEqual大约相同，但对于每个列表，它只执行一次。
因此，第一次使用特定的List<int>时，应基于数字的有序序列生成哈希并将其缓存。然后，下次比较列表时，可以使用缓存的值。我不确定如何使用比较器（可能是静态词典？）来实现此目的，但是您可以实现List包装器来轻松实现此目的。
这是一个基本概念。您需要小心以确保它不易碎（例如，确保在成员更改时使任何缓存的哈希码无效），但看起来这不是您使用方式的典型情况这个。
public class FasterComparingList<T>: IList<T>, IList, ...
/// whatever you need to implement
{
// Implement your interfaces against InnerList
// Any methods that change members of the list need to
// set _LongHash=null to force it to be regenerated
public List<T> InnerList { ... lazy load a List }
public int GetHashCode()
{
if (_LongHash==null) {
_LongHash=GetLongHash();
}
return (int)_LongHash;
}
private int? _LongHash=null;
public bool Equals(FasterComparingList<T> list)
{
if (InnerList.Count==list.Count) {
return true;
}
// you could also cache the sorted state and skip this if a list hasn't
// changed since the last sort
// not sure if native `List` does
list.Sort();
InnerList.Sort();
return InnerList.SequenceEqual(list);
}
protected int GetLongHash()
{
return .....
// something to create a reasonably good hash code -- which depends on the
// data. Adding all the numbers is probably fine, even if it fails a couple
// percent of the time you're still orders of magnitude ahead of sequence
// compare each time
}
}
如果添加后列表不会更改，则应该很快。即使在列表可能经常更改的情况下，创建新的哈希码的时间也可能与进行序列比较的时间相差无几（如果甚至更大）。