高效地插入和搜索字符串

Question

在一个应用程序中，我将有大约3000到30000个字符串。创建后（从文件无序读取），不会经常添加许多字符串（但有时会添加！）。删除字符串也不会经常发生。经常会将一个字符串与存储的字符串进行比较。

最好使用什么样的结构，哈希表，树（红黑树，Splay，...）还是只是一个无序列表（可能是StringArray？）？

（额外的说明：也欢迎提供一个好的C#实现链接）

- SoftwareTester

Answer 1

看起来你只需要一个哈希表。因此，HashSet<T> 似乎是理想的选择。（如果你需要键，则当然可以使用 Dictionary<T>）。

下面是关于 HashSet<T> 不同操作的时间复杂度摘要，其中一部分基于该类型使用数组作为支撑数据结构的事实。

• 插入：通常为 O(1)，但如果需要调整数组大小，则可能为 O(n)。
• 删除：O(1)
• 存在（包含）：O(1)（假设理想的哈希表桶）

如有错误，请有经验的人纠正。这些只是我从对实现/哈希表的了解中得出的最佳猜测。

- Noldorin

---

感谢RichardOD和Noldorin。 - SoftwareTester

Answer 2

HashSet在快速插入和搜索方面非常出色。Add、Remove和Contains的时间复杂度都是O(1)。

需要注意的是，如果数组不需要调整大小，则Add操作的时间复杂度为O(n)，正如Noldorin所说。

我最近参与了一个VB 6（我没有写）升级到.NET 3.5项目，在该项目中，我遍历了一个具有子项的集合，每个子项都可以出现在多个父项中。该应用程序处理了一个要发送到API的项目列表，每次调用API都会收取很高的费用。

我基本上使用HashSet来跟踪已经发送过的项目，以防止我们产生不必要的费用。由于该过程被多次调用（它基本上是一个批处理作业，带有多个命令），因此我在调用之间对HashSet进行了序列化。这个方法效果非常好- 我需要尽可能多地重用现有的代码，因为这些代码已经经过了充分的测试。HashSet的性能表现非常快速。

- RichardOD

Answer 3

如果您需要实时性能或最佳内存效率，我建议使用基数树、显式后缀或前缀树。否则，我可能会使用哈希。

树的优点是在最坏情况下查找、插入和删除时间有固定的边界（基于您要查找的模式的长度）。基于哈希的解决方案的优点是编写起来要容易得多（在C#中可以直接使用），初始构造成本更低，并且如果正确配置，则具有类似的平均性能。然而，它们往往使用更多的内存，并且具有非确定性的时间查找、插入（并且根据实现方式可能还包括删除）。

- patros

Answer 4

推荐使用HashSet<T>，如果您的比较只是“这个字符串是否存在于集合中”。您甚至可以使用不同的IEqualityComparer<string>实现（可能从StringComparer中选择），用于区分大小写等。

您需要的是仅此类比较，还是需要像“如果它实际上是有序列表中的一个元素，那么这个字符串将出现在集合中的哪里？”这样的检查？如果您需要这种类型的检查，那么您可能需要进行二进制搜索。（List<T>提供了BinarySearch方法；我不知道为什么SortedList和SortedDictionary没有，因为两者都能够很容易地进行搜索。诚然，SortedDictionary搜索不会完全与普通二进制搜索相同，但我认为它通常具有类似的特性。）

正如我所说，如果您仅需要“在集合中或不在”检查，则HashSet<T>是您的朋友。我只是想提出其他情况 :)

- Jon Skeet

---

SortedList和SortedDictionary在内部使用哈希表，那么为什么要使用二分查找呢？哈希表的查找理想情况下是O(1)，而二分查找则提供了O(log n)。也许我有点误解你的意思了？ - Noldorin

SortedList和SortedDictionary 不使用哈希表（当然，我指的是泛型类型。非泛型SortedList我不确定，但我认为它应该是一样的）。SortedList只是一个键数组和一个值数组，并确保它们保持有序。SortedDictionary是一个二叉搜索树。不要被它们实现IDictionary<TKey, TValue>所迷惑。关于哈希表查找的重点在于它仅提供了存在/不存在信息。而二分查找则提供了缺失元素的“将会”位置。请参见List<T>.BinarySearch的返回值。 - Jon Skeet

是的，你当然是对的。我因为某些原因与Dictionary<T>混淆了。不过根据问题的描述，OP似乎并不是在寻找任何项的索引，虽然这仍然是一种假设。 - Noldorin

我认为微软只是使用了一种命名约定，使得普通开发人员可以通过名称基本上识别类型的功能。这似乎适用于Dictionary和SortedList。这两个名称都不会特别困扰我，尽管我对Dictionary<T>和Hashtable之间的不一致性并不太热衷。（这肯定会引起许多人的困惑。）这本质上类似于关于实现相对于接口价值的辩论。 - Noldorin

@Jon：但它实际上可以有效地用于这个目的。 - Noldorin

Answer 5

如果你需要知道“如果它实际上是一个有序列表，这个字符串将出现在集合中的哪里”（如Jon Skeet的答案中所述），你可以考虑使用trie。这种解决方案只能用于某些类型的“类似字符串”的数据，并且如果“字母表”与字符串数量相比较大，则可能会迅速失去其优势。缓存局部性也可能成为问题。

然而，对于仅包含N = 30,000个事先计算的东西的集合来说，这可能过于工程化了。你甚至可以更好地分配一个k * N Optional数组，并通过跳过每个实际事物之间的k个空格来填充它（从而减少你的稀有插入需要重新分配的概率，仍然让你拥有二分搜索的变体，并保持你的项目按排序顺序排列。如果你需要精确“这个字符串将出现在集合中的哪里”，这种方法不起作用，因为你需要O(n)时间来检查每个空间，然后检查它是否为空白或者在插入时更新每个插槽中的“在我之前真正有多少项”的计数器需要O(n)时间。但它可以为你提供非常快速的不精确索引，并且这些索引在插入/删除之间是稳定的。

- Doug McClean