c# - C#中快速查找唯一单词的有效方法

Question

我遇到以下问题。我必须在内存中存储多种语言的唯一单词列表，当然，当我添加新单词时，我必须检查新单词是否已经存在。

当然，这需要非常快，主要是因为单词数量巨大。

我正在考虑实现 Suffix Tree ，但我想知道对于一些已经实现的内部结构是否有更简单的方法。

附注字数 ≈ 10⁷。

Answer 1

首先，请注意，后缀树在这里可能有点过头了，因为它们允许快速搜索任何单词的任何后缀，这可能比您要查找的内容有点太多。一个trie是一个非常相似的 DS，也允许快速搜索单词，但由于它不支持快速搜索任何后缀 - 它的创建更简单(无论是编程还是效率)。

另一个更简单的替代方案是使用简单的哈希表，它在 C# 中实现为 HashSet 。虽然 HashSet 理论上在最坏情况下速度较慢 - 每次查找的平均情况需要恒定时间，这对于您的应用程序来说可能足够了。

我的建议是:

1. 首先尝试使用 HashSet，这需要更少的工作量来实现，对其进行基准测试并检查它是否足够。
2. 确保您的 DS 是可修改的，以便您以后决定时可以轻松切换它。这通常是通过引入 interface 来完成的。它负责添加和查找单词，如果您需要更改它 - 只需向接口(interface)引入不同的实现即可。
3. 如果您决定添加后缀树或特里树 - 使用社区资源，无需重新发明轮子 - 有人已经实现了大部分数据结构，并且可以在线获取。