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 开头的节点