c# - 哪种 C# 数据结构允许在一对字符串中最有效地搜索子字符串？

Question

我有一个由成对值组成的数据结构，第一个是整数，第二个是字母数字字符串(可能以数字开头):

+--------+-----------------+
| Number | Name            |
+--------+-----------------+
| 15     | APPLES          |
| 16     | APPLE COMPUTER  |
| 17     | ORANGE          |
| 21     | TWENTY-1        |
| 291    | 156TH ELEMENT   |
+--------+-----------------+

这些表格最多可包含 100,000 行。

我想提供一个查找函数，用户可以在其中查找数字(就好像它是一个字符串)或字符串的一部分。理想情况下，查找将在用户输入时“实时”进行；每次击键后(或者可能在短暂延迟 ~250-500 毫秒后)将进行新的搜索以找到最有可能的候选人。因此，例如搜索

• 1将返回 15 APPLES , 16 APPLE COMPUTER , 17 ORANGE ， 和 291 156TH ELEMENT
• 15将搜索范围缩小到 15 APPLES , 291 156TH ELEMENT
• AP将返回 15 APPLES和 16 APPLE COMPUTER
• (理想情况下，但不是必需的)ELEM将返回 291 156TH ELEMENT .

我正在考虑使用两个 Dictionary<string, string>因为最终 int s 被比较为 string s -- 一个将按整数部分索引，另一个按字符串部分索引。

但真正按子字符串搜索不应该使用散列函数，而且使用两倍我认为应该需要的内存似乎很浪费。

最终的问题是，是否有任何性能良好的方法可以同时在两个大列表中搜索子字符串？

否则，SortedDictionary 怎么样？ ？可能会提高性能，但仍然无法解决哈希问题。

考虑过动态创建一个正则表达式，但我认为那会表现得非常糟糕。

我是 C# 的新手(来自 Java 世界)，所以我还没有研究过 LINQ；那是答案吗？

编辑 18:21 EST:“名称”字段中的所有字符串都不会超过 12-15 个字符，如果这会影响您的潜在解决方案的话。

Answer 1

如果可能，我会避免将所有 100,000 个条目加载到内存中。我会使用数据库或 Lucene.Net索引值。然后使用适当的查询语法来高效地搜索结果。