松散词典，需要咨询

我需要创建一个口令，其中键是字符串，值是对象。但我不希望密钥与用户提供的字符串完全匹配。相反，我想要键包含字符串的一部分。让我通过示例来解释松散词典，需要咨询

如果在密钥“Johnson”下的字典中有条目，我希望能够在给定输入字符串“John”，“Jo”的情况下找到值。另外我希望能够提取几个匹配输入字符串的值。例如，如果有条目“John A”和“John B”，我希望具有像FindFirst这样的功能，它会将迭代器返回到第一个匹配值。

理想我宁愿使用现有System.Collections.Generic.Dictionary 可能派生新类并覆盖一些方法

来源

2009-12-07 Captain Comic

它听起来像你真的想要一个trie – 2009-12-07 11:16:24

我怀疑SortedList<TKey, TValue>将是在这里你最好的选择，这是一种基于二叉搜索树的字典。其Keys财产返回一个IList<TKey> O（1）访问时间。

你会获取Keys财产和执行二进制搜索，找到与你的搜索键启动键。然后从该示例键上下查找实际匹配的键的范围。这会给O（log n）性能，而不是通过查看所有键的O（n）性能。

我不会从这个虽然获得 - 我会写这有一个SortedList<,>内部一个类型。

来源

2009-12-07 10:31:21

你绝对正确的是，SortedList（而不是SortedDictionary）将通过在Keys集合上允许O（1）操作来帮助查找范围。更有效率的方法可能是仅仅对List 进行排序并对其进行二分搜索，以避免必须通过键查找值。 – SoftMemes 2009-12-07 10:55:27

尽管当然Values集合可以通过索引来访问（索引与键的索引相同），所以它不是一个真正的问题。没关系。 – SoftMemes 2009-12-07 10:56:51

虽然我怀疑一本字典是否适合这样的事情，你可以使用：

dictionary[dictionary.Keys.First(d=>d.StartsWith("Jo"))]

你失去了最字典的价值在这里，因为它的价值的快速检索优化，通过使用该密钥。在这种情况下，你必须迭代列表中的每个键。

我得+1乔恩您指出SortedList<TKey,TValue>

来源

2009-12-07 10:27:41

可以通过提供的IEqualityComparer实现与使用自定义词典相等比较。然而，Dictionary是一个散列映射，需要从每个键映射到同一个整数散列，这使得它在你的情况下不太有用。您可以使用SortedDictionary（也是IDictionary），提供自定义IComparer并获得O（log（n））查找时间（而不是字典理想情况下可以提供的O（1））。

来源

2009-12-07 10:35:12 SoftMemes

注意自我：这不能解决多个匹配的问题，SortedDictionary将只返回第一个“相等”键。 – SoftMemes 2009-12-07 10:47:54

你可以使用一个正常字典并提供你自己的比较器，看看generic dictionary，特别是关于providing your own comparer的部分。

的主要问题是，你基本上是要比较对所有键，直到你找到一个匹配，由于您使用的自定义规则，所以请确保您的自定义比较迅速地退出。如果不能匹配（例如开始用不同的字母）。

来源

2009-12-07 10:37:14

你打算GetHashCode在这种情况下返回什么？ – SoftMemes 2009-12-07 10:48:48

我想你应该考虑将来自基础记录的访问相应的键搜索。

那你，例如，有单纯的键的B树+结构，其中您找到第一个匹配的记录，那么按照B树+枚举，直到你有不匹配。

与数据库中的非聚簇索引类似。首先你找到钥匙，然后找到记录。

“Johnson”中的示例“Jo”和“John”是“StartsWith（）”的示例，其中关键排序将有利于您。如果你也希望仅仅寻找一个子字符串而不是仅仅是初始段，那么你需要查看其他存储和查找密钥的算法。

如果你不积极，你们都需要并且能够利用优化搜索，那么你应该对所有的键进行内存中的扫描，然后专注于优化匹配的谓词。例如，使用预编译搜索的Regex选项。

来源

2009-12-07 11:04:49 Tormod

btree与内存中的搜索有什么关系？ – SoftMemes 2009-12-07 11:47:45

松散词典，需要咨询

回答

相关问题