c# - 用于查找字符串属性以开头的所有项目的最快集合

Question

我目前正在使用 ICollection 返回所有位于 location.path.StartsWith(value) 的项目。

集合本身保存在一个单例对象中，并在从存储过程调用到 Sql 数据库的对象实例化时被水化。虽然项目的数量只有 1300 左右，但集合本身有可能被经常搜索(我无法定义经常 - 可能 100,000 或 100 万 - 它会有所不同)。

考虑到上述详细信息，也许还需要更多信息，用于查找 path.StartsWith(value) 中的所有项目的最有效集合类型是什么？

Answer 1

我认为您正在寻找 Trie它允许您添加与该键相关联的项目，然后查找具有以您的搜索词开头的键的所有项目

来自页面:

As discussed below, a trie has a number of advantages over binary search trees.[4] A trie can also be used to replace a hash table, over which it has the following advantages:

• Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.

IIRC，我查找了一些 C# 代码并找到了 this implementation合理地工作

编辑评论:您需要扫描字典的所有键以查看它们是否以您的搜索字符串开头。在 Trie 中，您请求与您的搜索字符串匹配的节点，然后您可以保证该节点下的所有元素都有一个以您提供的搜索字符串开头的键。

在这里您可以看到搜索 te 需要向下钻取 Trie 中的两个节点，并且您到达一个所有后代都以 te 开头的节点/p>