在LINQ中，遍历HashSet<string>的一个聪明替代方案是什么？

Question

我有一个URL白名单，存储在HashSet<string>中。我想要查找url是否以白名单中的任何一项开头（必须是这样）。

编辑：之前的示例有点误导，并且存在打字错误 - 我已经有一个基本的URL，例如yahoo.com，白名单只是路径。

HashSet<string> whiteList = new HashSet<string>();

string path = "/sport/baseball/";
bool validUrl = false;

foreach (string item in whiteList)
{
    if (path.StartsWith(item))
    {
        validUrl = true;
        break;
    }
}

有没有更优雅的方法使用LINQ（针对对象）进行查找？列表不是很大，因此性能不是问题。

- Chris S

---

顺便说一下，HashSet<T> 在这里并没有帮助你；它只有在进行相等性测试时才有用。如果你不以其他方式使用 HashSet<T>，请将其替换为 List<T> - 这样构建速度会更快（假设你没有大量重复项）。 - Marc Gravell

Marc：他可能正在使用HashSet，这样就不会出现重复的链接。 - Noon Silk

如果列表很小且性能良好，则应坚持使用HashSet。如果列表变得很大，您可以通过使用排序列表而不是哈希集来提高渐近性能。排序列表的构建成本更高，但搜索速度更快；您可以对列表进行二进制搜索以查找最接近路径的匹配项，然后仅检查该项以查看它是否是精确前缀匹配。 - Eric Lippert

哦，说起来，我听说下一个框架基类库中将会有一个SortedSet类型。 - Eric Lippert

终于与Java的集合相当了！这是我认为Java比.NET/C#更强大的唯一部分。 - Chris S

Answer 1

bool validUrl = whiteList.Any(item => linkUrl.StartsWith(item));

顺便提一下，通常情况下，哈希表不是解决这种问题的好数据结构（当你没有键并且基于函数匹配键时），因为你必须一直枚举整个表。相比之下，你可以使用一个简单的List<string>来保存项目，这样可以获得更好的性能。

- Mehrdad Afshari

---

@Spence：函数式编程是一个奇妙的洞穴。随着时间的推移，奇迹将被重新发现。 - Mehrdad Afshari

在C#中，它还没有完全实现，因为编译器通常仍然会编写命令式代码。如果C#编译器可以开始根据您要求计算机执行给定功能的事实而不是如何执行它来进行高级操作，那将非常有趣。 - Spence

Spence：这完全没有意义。 - Noon Silk

我猜Any比哈希表的开销更小，尽管白名单实际上只在构造函数中从文件路径中读取一次。 - Chris S

@Chris S：Any 基本上是一个 foreach 循环，从性能上来说应该与你编写的代码类似。然而，对于实现了 IEnumerable<T> 接口的 任何 对象，都可以使用相同的代码，包括 List<string>。我认为对于你的情况来说，这并没有什么实质性的区别，因为白名单可能很小。 - Mehrdad Afshari

Answer 2

这里的问题在于查找。您的白名单中是否有任何规律？例如，它总是一个域名，而不一定是其中的页面或特定子域名？

如果是这样，您可以使用 string.split 方法从字符串中获取第一个 URL 部分，然后使用您的哈希集的 .Contains() 方法获取该项。这将删除对列表中每个元素运行一次的 string.StartsWith() 命令以及昂贵的字符串比较，并用一次性的 string.split 和 O(1) 查找替换它。

HashSet<string> whiteList = new HashSet<string>();
//add items

string urlStartsWith = "http://www.yahoo.com";
bool validURL = whiteList.Contains(url);

- Spence