当使用大型列表和多个线程时，HashSet<T>.Contains()方法是否高效？

Question

我正在编写一个多线程程序，用于爬取某个网站并收集ID。它将这些ID存储在一个共享的静态List<string>对象中。

当任何项目被添加到List<string>中时，它首先会与包含已收集ID的黑名单HashSet<string>进行检查。

我是这样做的:

private static HashSet<string> Blacklist = new HashSet<string>();
private static List<string> IDList = new List<string>();

public static void AddIDToIDList(string ID)
{
    lock (IDList)
    {
        if (IsIDBlacklisted(ID))
            return;
        IDList.Add(ID);
    }
}
public static bool IsIDBlacklisted(string ID)
{
    lock (Blacklist)
    {
        if (Blacklist.Contains(ID))
            return true;
    }
    return false;
 }

黑名单在完成后保存到文件中，并在每次程序启动时加载，因此随着时间的推移会变得非常大（高达50k条记录）。是否有更有效的方式来存储和检查每个ID是否在黑名单中？

谢谢！

- blizz

---

通过创建一个大型的虚假黑名单并使用System.Diagnostics.Stopwatch类来计时操作，测试这个应该相当容易。 - Greg

谢谢，但我不确定有更好的替代方案来进行测试，因此才提出这个问题。 - blizz

可能是重复的问题：什么.NET集合提供最快的搜索。 - Greg

“黑名单”什么时候被修改？ - Brian Gideon

我差点搞混了 - 直到所有操作停止后，这个黑名单才会被修改。然后它会保存到一个文本文件中，在下一次运行时被加载。 - blizz

Answer 1

为了提高性能，尝试使用ConcurrentBag<T>集合。此外，由于BlackList未被修改，因此无需锁定它，例如：

private static HashSet<string> Blacklist = new HashSet<string>();
private static ConcurrentBag<string> IDList = new ConcurrentBag<string>();

public static void AddIDToIDList(string ID)
{
    if (Blacklist.Contains(ID))
    {
        return;
    }

    IDList.Add(ID);
}

- Kirill Polishchuk

---

这非常有趣。这比HashSet<T>提供更好的性能吗？另外，使用ConcurrentBag<T>是否可能不允许重复项？ - blizz

据我理解，我必须使用集合来实现“无重复”规则，或者编写自己的集合。如果是这样的话，这并不能达到我的目的。 - blizz

@blizz，这段代码与你的完全相同，但性能更好。 - Kirill Polishchuk

@blizz，你当前的代码也没有强制执行“无重复项”的规则。List<T>不是一个集合。 - CodesInChaos

@CodesInChaos 是的，它可以。它会检查黑名单并且如果它在里面就不会添加到列表中。如果它确实将 ID 添加到列表中，它也会将其添加到黑名单中（这里没有显示）。黑名单使用 HashSet<T>，它不允许重复项。 - blizz

@blizz "它还将其添加到黑名单中" 这使得你的问题有很大的改变，并实际上使得这个答案的一部分无效。在提出问题时，请包括所有相关信息。这也直接反驳了你关于“在所有操作停止之前，此黑名单没有被修改”的说法。 - CodesInChaos

Answer 2

在 HashSet 上，只要没有修改 Blacklist，读取操作就是线程安全的，您不需要在其上加锁。此外，在黑名单检查内部应该加锁，这样可以减少加锁的次数，从而提高性能。

private static HashSet<string> Blacklist = new HashSet<string>();
private static List<string> IDList = new List<string>();

public static void AddIDToIDList(string ID)
{
    if (IsIDBlacklisted(ID))
        return;
    lock (IDList)
    {
        IDList.Add(ID);
    }
}
public static bool IsIDBlacklisted(string ID)
{
    return Blacklist.Contains(ID);
}

如果正在修改黑名单，最好的锁定方法是使用ReaderWriterLock（如果您使用较新版本的.NET，则使用轻量级版本）。

private static HashSet<string> Blacklist = new HashSet<string>();
private static List<string> IDList = new List<string>();
private static ReaderWriterLockSlim BlacklistLock = new ReaderWriterLockSlim();

public static void AddIDToIDList(string ID)
{
    if (IsIDBlacklisted(ID))
        return;
    lock (IDList)
    {
        IDList.Add(ID);
    }
}
public static bool IsIDBlacklisted(string ID)
{
    BlacklistLock.EnterReadLock();
    try
    {
        return Blacklist.Contains(ID);
    }
    finally
    {
        BlacklistLock.ExitReadLock();
    }
}

public static bool AddToIDBlacklist(string ID)
{
    BlacklistLock.EnterWriteLock();
    try
    {
        return Blacklist.Add(ID);
    }
    finally
    {
        BlacklistLock.ExitWriteLock();
    }
}

- Scott Chamberlain

---

使用ReaderWriterLockSlim相比静态锁对象有什么好处？ - blizz

ReaderWriterLock 允许无限并发读取，只有在有人想要写入（然后它会阻止写入者和读取者）时才像锁一样起作用。 - Scott Chamberlain

但是ReaderWriterLock(Slim)每次调用的开销比lock大，因此即使在大多数情况下都是读取操作的情况下，它的速度也很可能会更慢。 - CodesInChaos

@CodesInChaos，你有任何支持这个观点的东西吗？在高度争用的频繁读取但不经常写入的情况下，我期望ReadWriterLock会表现得更好，因为除了偶尔的写入情况外，您永远不需要阻塞线程。我可以看到在单线程情况或没有争用的情况下，“lock”可能更便宜，但是如果资源永远不会受到争用，那么为什么要锁定呢？ - Scott Chamberlain

@ScottChamberlain 我不记得来源，而且可能已经过时了。但我记得对于细粒度锁定，lock 通常更好，因为它的开销较小。对于粗粒度锁定，如果是大多数情况下都是读取操作，那么 ReadWriterLockSlim 更胜一筹。请使用两种类型的锁来测试您特定的场景。不要简单地假设其中一种比另一种更快。 - CodesInChaos

@CodesInChaos，我完全同意这一点：不要盲目听从互联网上随机人士的建议，进行基准测试并查看在您所处的情况下哪种方法最有效！ - Scott Chamberlain

Answer 3

两个要考虑的问题 - 首先，如果您使用 .NET 字典（即 System.Collections.Generic.Dictionary）的索引器，像这样（而不是调用 Add() 方法）：

idList[id] = id;

如果该项不存在，则会添加该项 - 否则，它将替换该键处的现有项。其次，您可以使用ConcurrentDictionary（位于System.Collections.Concurrent命名空间中）实现线程安全，因此您不必担心锁定问题。关于使用索引器的评论同样适用。

- Steve Michelotti

---

有趣的笔记 - +1。不幸的是，它并没有回答我的效率问题。 - blizz

实际上，我想表达的是这更有效率，因为你只需调用索引器一行代码，而不必先执行Contains()检查，然后再执行Add()。 - Steve Michelotti

Answer 4

在您的情况下，是的，HashSet是最好的选择，因为它只包含一个要查找的值，而不像Dictionary需要键和值才能进行查找。

当然，如果HashSet没有被修改，就不需要锁定它，并考虑将其标记为只读。

- Ehsan