c# - 松散的字典，需要建议

Question

我需要创建一个字典，其中键是字符串，值是对象。但我不希望 key 与用户提供的字符串完全匹配。相反，我想键包含字符串的一部分。让我举例说明

如果在键“Johnson”下的字典中有一个条目，我希望能够找到值给定输入字符串“John”、“Jo”。我还希望能够提取几个匹配的值按给定条件输入字符串。例如，如果有条目“John A”和“John B”我想要以具有像 FindFirst 这样的功能，它将迭代器返回到第一个匹配值。

理想情况下，我更愿意使用现有的 System.Collections.Generic.Dictionary可能派生一个新类并覆盖一些方法

Answer 1

我怀疑 SortedList<TKey, TValue> 在这里将是你最好的选择，它是一个基于二叉搜索树的字典。它的Keys属性返回 IList<TKey>访问时间为 O(1)。

你会获取 Keys属性并执行二进制搜索以查找以您的搜索键开头的键。然后从该示例键向上和向下查找以找到实际匹配的键范围。这将提供 O(log n) 性能，而不是您通过查看所有键获得的 O(n) 性能。

虽然我不会从中推导 - 我会写一个有 SortedList<,> 的类型内部。