如何从值类型为T的List<List<T>>中删除重复项？

Question

这是一个非常简单的问题，肯定已经被问过并且回答了...但我找不到。

我想使用LINQ从值类型的列表的列表中删除重复项。 我已经尝试了以下方法:

List<List<int>> a = new List<List<int>>() { new List<int>() { 1, 2, 3 }, new List<int>() { 1, 2, 3 }, new List<int>() { 2, 3, 4 } };
// remove duplicates from a
List<List<int>> b = a.Distinct().ToList(); // this doesn't do it
List<List<int>> c = a.Distinct(new ListKeyComparer<int>()).ToList(); // nor does this

internal class ListKeyComparer<TKey> : IEqualityComparer<List<TKey>>
{
  public bool Equals(List<TKey> key1, List<TKey> key2)
  {
    return String.Join("_", key1).Equals(String.Join("_", key2));
  }

  public int GetHashCode(List<TKey> key)
  {
    return key.GetHashCode();
  }
}

欢迎提出所有解决方案！

- Ed Graham

---

你能描述一下你想得到的确切算法吗？例如，当发现重复项时，哪个列表具有优先权，是第一个吗？[[1,2,3],[1,4,5]] 应该返回 [[2,3],[1,4,5]] 还是 [[1,2,3],[4,5]]？ - samy

或者您想要删除完全相同的项目的列表？顺序重要吗？正如您所看到的，我们需要更多信息 :) - samy

我认为你对于从集合中移除重复项的理解是错误的。你正在考虑这样一种情况：你有一个 List<int> {1,2,2,3,3}，使用 a.Distinct() 会给你返回一个不同的列表。但实际上，你有的是一个列表的列表，每个列表可能包含数字1，但由于列表中的每个列表并不完全相同，它们实际上在开始时就是不同的！ - The Muffin Man

也许可以看一下Intersect和Except扩展。 - user3411327

感谢大家抽出时间 -- 下面的答案解决了问题。 - Ed Graham

Answer 1

你需要的是一个序列的IEqualityComparer。这并不特别困难。（注意，您可以轻松地将示例广义化为通用形式，而不是具体针对int，并且使用IEnumerable而不是List，因为您不需要列表特定的功能。）

public class SequenceComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    private IEqualityComparer<T> comparer;
    public SequenceComparer(IEqualityComparer<T> comparer = null)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
    }
    public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
    {
        return x.SequenceEqual(y, comparer);
    }

    public int GetHashCode(IEnumerable<T> sequence)
    {
        unchecked
        {
            int hash = 19;
            foreach (var item in sequence)
                hash = hash * 79 + comparer.GetHashCode(item);
            return hash;
        }
    }
}

Equals 方法通过 SequenceEqual 免费提供给您使用。唯一有趣的事情是基于序列中的值创建一个有意义的哈希，而不是使用序列本身提供的 GetHashCode 方法，因为它通常不会这样做（包括 List 在内的大多数 IEnumerable 将基于类的引用而不是其中的值来生成哈希码）。

在这种情况下，不需要为项目类型（在本例中为 int）提供此 SequenceComparer 的内部比较器，因为默认的相等性应该正是您所需要的。如果您有一个 List<List<string>> 并且您想要比较列表的相等性并对字符串进行不区分大小写的比较，则可以使用 new SequenceComparer<string>(StringComparer.InvariantCultureIgnoreCase)。

请注意，连接项目的字符串值不是比较两个序列的特别安全的方法。对象可能没有有意义的 ToString 方法。（任何未覆盖 ToString 的类型都将只打印出类型名称，这意味着所有内容都相等于其他所有内容。）您还需要处理碰撞的情况。例如，如果您有一个生成字符串值为 "1_2" 的项目，那么它将被认为等于生成 "1" 和 "2" 的两个不同项目。

- Servy

---

很棒的东西，Servy：非常感谢你对哈希码和冲突的解释。我将另一个答案标记为官方答案，但我很欣赏你的答案同样有效。 - Ed Graham

Answer 2

你的实现存在问题，它使用了键列表的直接 GetHashCode 方法。你可以通过替换为一个由下划线连接数字构成的“键字符串”的哈希码，或者动态计算哈希码来解决这个问题：

// Here is a fix to your method. It would work if TKey values
// cannot have underscores. In any event, it will be very slow.
internal class ListKeyComparer<TKey> : IEqualityComparer<List<TKey>>
{
  // Make a method that produces the key to avoid repeating yourself:
  private string MakeKey(List<TKey> key) {
    return String.Join("_", key);
  }
  public bool Equals(List<TKey> key1, List<TKey> key2)
  {
    return MakeKey(key1).Equals(MakeKey(key2));
  }

  public int GetHashCode(List<TKey> key)
  {
    return MakeKey(key).GetHashCode();
  }
}

这里是一个更好的实现：

internal class ListKeyComparer<TKey> : IEqualityComparer<List<TKey>>
{
  public bool Equals(List<TKey> key1, List<TKey> key2)
  {
    return key1.SequenceEqual(key2);
  }

  public int GetHashCode(List<TKey> key)
  {
    return key.Aggregate((p, v) => 31*p + v.GetHashCode());
  }
}

这个实现方式有三个优点：

• 更易读 - 每个方法都是单行的，更加自解释（假设您熟悉多部分键的计算哈希码）
• 更高效 - 这段代码避免了在哈希键的过程中重复构造字符串
• 提高正确性 - 即使 TKey 字符串包含下划线，此实现也能正常工作。

该实现使用 LINQ 方法 SequenceEqual 和 Aggregate 来缩短 Equals 和 GetHashCode 的代码。

- Sergey Kalinichenko

---

太好了 - 非常感谢您。事实上，我使用了一个更简单的GetHashCode()函数，即 return String.Join("_", key).GetHashCode(); 因为我没有完全理解您的函数；但它似乎也能工作。 - Ed Graham

@EdGraham 那是一个相当糟糕的想法。我强烈反对您使用那种解决方案，因为它在正确性和性能方面都有相当多的深刻负面影响。 - Servy

@Servy -- 能否详细说明一下？ - Ed Graham

@EdGraham 我在我的回答中详细阐述了，描述了多种解决方案可能导致不正确的结果。 - Servy

@EdGraham 请看一下修改后的内容：我详细阐述了我在对第一个实现进行评论时所写的内容。 - Sergey Kalinichenko