快速字符串查找的最佳集合

我需要一个字符串列表和一种方法来快速确定字符串是否包含在该列表中。快速字符串查找的最佳集合

为了提高查询速度，我考虑了SortedList和Dictionary;然而，两者都与KeyValuePair s一起工作，当我需要的只是一个string。

我知道我可以使用KeyValuePair并简单地忽略Value部分。但我更喜欢高效，只是想知道是否有一个更适合我的要求的集合。

2011-04-03 Jonathan Wood

如果您使用.NET 3.5或更高版本，请使用HashSet<String>。

做不到这一点，一个Dictionary<string, byte>（或任何你想要的类型为TValue类型参数），如果你有很多条目会比SortedList更快 - 后者将使用二进制搜索，因此这将是O（日志n）查找，而不是O（1）。

来源

2011-04-03 17:31:50

酷，谢谢。（尽管看起来有点奇怪，但直到3.5才有这样的课程。） – 2011-04-03 17:33:58

@Jonathan：同意 - 尽管如此。在.NET 4中，有一个接口来表示集合（'ISet '），也是'SortedSet '中的另一个选项（在这种情况下，这又不会特别有用）。 – 2011-04-03 17:37:19

我只是回头看这个。 O（1）查找确实很快。不过，我猜这个集合实现了某种哈希。那么O（1）不会假设没有碰撞？（顺便说一下，我正在通过你的书工作。） – 2011-06-16 16:13:02

如果你只是想知道，如果一个字符串是在装置使用HashSet<string>

来源

2011-04-03 17:32:03 BrokenGlass

HashSet<string>就像一个Dictionary，但只有钥匙。

来源

2011-04-03 17:32:30

如果您想旋转自己的数据结构，请使用Trie。 http://en.wikipedia.org/wiki/Trie

最坏情况是如果字符串是本：O（串的长度）

来源

2011-04-03 17:33:20 James

这听起来像

var keys = new HashSet<string>();

每MSDN作业：将包含函数O（1）复杂。

但是，您应该知道，添加时，它不会给出重复的错误。

来源

2011-04-03 17:33:29

更确切地说，Add方法不会引发异常，但如果已添加密钥，则返回true;如果已存在，则返回false。 – 2011-04-03 17:35:47

@Alois：听起来很完美。每当有些事情不仅仅是抛出异常时，.NET库中的大部分习惯总是困扰着我。 – 2011-04-03 17:41:40

我知道这个答案对这个聚会来说有点迟，但我遇到了一个问题，我们的系统运行缓慢。分析后，我们发现有很多字符串查找与我们的数据结构的结构有关。

所以我们做了一些研究，came across these benchmarks，做了我们自己的测试，现在已经切换到使用SortedList。

if (sortedlist.ContainsKey(thekey)) 
{ 
//found it. 
}

尽管字典被证明速度更快，但是我们不得不重构的代码更少，性能提升对我们来说足够好。

无论如何，要分享的网站，以防其他人遇到类似问题。他们在数据结构之间进行比较，其中你要查找的字符串是一个“键”（如HashTable，Dictionary等），或者是一个“值”（列表，数组或字典等）存储。

来源

2014-11-10 00:14:15

我知道这个问题已经过时了，但我只需要解决同样的问题，只适用于一小部分字符串（在2到4之间）。

在我的情况下，我实际上对一串字符串使用了手动查找，结果比HashSet<string>（我测试过它的速度）快得多。

for (int i = 0; i < this.propertiesToIgnore.Length; i++) 
{ 
    if (this.propertiesToIgnore[i].Equals(propertyName)) 
    { 
     return true; 
    } 
}

请注意，它比散列集仅适用于微小阵列！

编辑：只适用于手动for循环，不使用LINQ，在该评论的详细

来源

2018-01-14 16:08:58

是的，'HashSet <>'有一些开销。我只会在搜索较大的集合时推荐它。顺便说一句，你的代码可以缩短为'return PropertiesToIgnore.Any（p => p.Equals（propertyName））' – 2018-01-14 16:12:03

不幸的是，使用Linq减慢了执行速度10倍！基准结果'ArrayManualLoop：6.018 ns''ArrayLinq：59.171 ns'。 Linq将处理器缓存区分开来，所有可能的收益都会丢失。 – 2018-01-14 16:20:40

快速字符串查找的最佳集合

回答

相关问题