c# - 在 C# 列表中查找重复项的最快方法

Question

我知道在 SO 上有很多关于这个主题的类似问题，但我找不到我正在寻找的答案。这是我的要求。

我有一长串字符串(很容易超过 50,000 甚至 100,000 个项目)，我需要在其中找到重复的项目。但是仅仅找到重复项是不行的；我真正想做的是遍历列表并在每个项目的末尾添加一个增量索引以指示项目重复的次数。为了更好地说明，让我举个例子。我的列表实际上包含路径，因此示例大致与此类似。

我的原始列表:

AAA\BBB
AAA\CCC
AAA\CCC
BBB\XXX
BBB
BBB\XXX
BBB\XXX

我添加了索引的调整列表:

AAA\BBB[1]
AAA\CCC[1]
AAA\CCC[2]
BBB\XXX[1]
BBB[1]
BBB\XXX[2]
BBB\XXX[3]

首先，我使用 Linq 尝试了以下方法:

List<string> originalList = new List<string>();
List<string> duplicateItems = new List<string>();

// pathList is a simple List<string> that contains my paths.
foreach (string item in pathList)
{
    // Do some stuff here and pick 'item' only if it fits some criteria.
    if (IsValid(item))
    {
        originalList.Add(item);
        int occurences = originalList.Where(x => x.Equals(item)).Count();
        duplicateItems.Add(item + "[" + occurences + "]");
    }
}

这工作得很好，给了我想要的结果。问题是考虑到我的列表可以包含 100K 项，它的速度非常慢。所以我环顾四周，了解到 HashSet 可能是一种可能更高效的替代方案。但我不太清楚如何使用它获得我想要的确切结果。

我想我可以尝试这样的事情:

HashSet<string> originalList = new HashSet<string>();
List<string> duplicateItems = new List<string>();

foreach (string item in pathList)
{
    // Do some stuff here and pick 'item' only if it fits some criteria.
    if (IsValid(item))
    {
        if (!originalList.Add(item))
        {
            duplicateItems.Add(item + "[" + ??? + "]");
        }
    }
}

稍后我可以将“[1]”添加到 HashSet 中的所有项目，但是在将项目添加到我的重复列表时，我如何获得正确的索引(由上面的通用混淆符号 ??? 标记) ？我无法保留可以传递给我的方法的引用 int，因为可能有数百个不同的重复项目，每个项目重复不同的次数，如我的示例中所示。

我还能使用 HashSet 吗，或者是否有更好的方法来实现我的目标？即使是正确方向的轻微指示也会有很大帮助。

Answer 1

既然你要求最快，最好的 IMO 是使用 foreach循环和计数 Dictionary<string, int> .它的时间复杂度与 HashSet 相同并且使用比 LINQ 少得多的内存 GroupBy :

var counts = new Dictionary<string, int>(pathList.Count); // specify max capacity to avoid rehashing
foreach (string item in pathList)
{
    // Do some stuff here and pick 'item' only if it fits some criteria.
    if (IsValid(item))
    {
        int count;
        counts.TryGetValue(item, out count);
        counts[item] = ++count;
        duplicateItems.Add(item + "[" + count + "]");
    }
}