如何创建一个拥有不同元素的HashSet<List<Int>>？

Question

我有一个包含多个整数列表的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);
}

- Preets

---

请查看Jon Skeet在此处的答案：https://dev59.com/i3NA5IYBdhLWcg3wS7sm#1023475 - Forgotten Semicolon

你能提供更多关于你实际要解决的问题的信息吗？HashSet<List<int>>似乎不是一个常用的工具。 - marcind

@marcind，我正在使用它来维护一个数字的所有因数分解列表...所以对于24，你可以有例如{4, 2, 3}，{2, 2, 6}等...目前我使用的算法会创建重复的集合，我希望我知道如何解决那个问题，但可惜我不知道 :-/ - Preets

你可能想将其作为一个单独的问题提出。应该有比你目前尝试的更优雅的解决方案。 - CodesInChaos

@CodeInChaos，是的，我肯定认为我应该这样做！任何解决方案都比我目前混乱的情况更优雅;-) - Preets

Answer 1

这里提供了一个可能的比较器，可以通过其元素比较 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 = unchecked(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();
}

- CodesInChaos

---

@downvoter，您能解释一下这个解决方案存在什么问题吗？这样我就可以修复/改进它了。 - CodesInChaos

相当接近，但是在 add 之前或在 Equals 中缺少 sort。 - Rune FS

@CodeInChaose 我同意你所概述的设计选择。对于已排序的列表进行排序似乎是一种浪费。这是针对你（现在已更新）的Main()的评论。（而对我来说，一开始并不值得被踩） - Rune FS

@CodeInChaose，这个排序的最坏情况是O(n2)，Equals的最坏情况是O(n)，而GetHashCode总是O(n)，这真的是最好的方法吗？ - Magnus

哈希集合/字典的契约明确规定，当对象在集合中时，等式和哈希码都不能更改。通常只有在不可变对象上覆盖equals/hashcode。即使哈希集合不存储哈希，由于哈希确定桶，因此更改哈希会破坏它，导致查找错误的桶。 - CodesInChaos

Answer 2

这里开始就不对了，必须使用HashSet<ReadOnlyCollection<>>，因为不能允许列表更改并使设置谓词无效。这样你就可以在将集合添加到集合中时以O(n)的时间计算哈希码。使用O(n)的测试检查它是否已经存在于集合中，如果所有哈希值都相等，则最坏情况下为O(n^2)。请将计算出的哈希值与集合一起存储。

- Hans Passant

---

它并不像ReadOnlyCollection那样保证不可变性。如果这个集合没有在公共API中暴露出来，可变性就不重要了。存储计算的哈希值也不是特别重要，因为我认为HashSet<T>已经存储了它已经包含的元素的哈希值。 - CodesInChaos

一个 ReadOnlyCollection<int> 只是读取操作。是否将其存储或创建派生类来覆盖 Equals+GetHashCode 取决于 OP。 - Hans Passant

我的意思是，如果您不自己创建ReadOnlyCollection，则外部人仍然具有对基础IList的引用，并且可以更改该列表，这将反映在ReadOnlyCollection中。如果您控制ReadOnlyCollection的创建，则可以保证（浅层）不可变性。（并且在int深度不可变性上） - CodesInChaos

Answer 3

你为什么不使用数组呢？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
   } 
}

如果列表一旦添加就不会改变，那么这应该非常快。即使在列表可能经常更改的情况下，创建新哈希码所需的时间也不太可能与执行序列比较相差很大（如果有的话）。

- Jamie Treworgy

---

没有特别的原因使用List<>，我不知道int[]表现更好。谢谢！你的假设是正确的，这些列表包括重复项，这就是为什么我不使用集合的原因。 - Preets

通常，一个更简单的结构可能比一个更复杂的结构更快，除非你正在做一些依赖于该复杂结构某个方面的事情（例如，链表将比非链表更快地插入项目）。我冗长回答的要点是，你应该使用一个可以缓存哈希码的结构。由于比较列表或创建能够唯一标识一个对象的东西很昂贵，并且你在同一个对象上进行了很多次操作，所以只需设置一个可以记住该唯一ID的东西即可。 - Jamie Treworgy

Answer 4

比较列表的哈希集时，您可以选择的一种选项是，而不是比较每个元素，对列表进行排序并使用逗号连接它们，然后比较生成的字符串。

因此，在这种情况下，当您创建自定义比较器而不是迭代元素并计算自定义哈希函数时，您可以应用此逻辑。

- Jack Sparrow

Answer 5

如果您没有指定IEQualityComparer，则将使用类型默认值，因此我认为您需要创建自己的IEQualityComparer实现，并将其传递给HashSet的构造函数。这里有一个很好的例子。该例子可以帮助您更好地理解如何实现IEQualityComparer接口。

- BrandonZeider