c# - 高效的字符串插入和搜索

Question

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

我可以最好地使用哪种结构，哈希表、树(红-黑、Splay、....)还是有序列表(也许是 StringArray？)？

(附加说明:也将不胜感激指向良好 C# 实现的链接)

Answer 1

听起来您只需要一个哈希表。 HashSet<T> 因此似乎是理想的选择。 (您似乎不需要 key ，但如果需要，Dictionary<T> 将是正确的选择，当然。)

这里总结了 HashSet<T> 上不同操作的时间复杂度尺寸n .它们部分基于该类型使用数组作为支持数据结构这一事实。

• 插入:通常为 O(1) , 但可能是 O(n)如果数组需要调整大小。
• 删除: O(1)
• 存在(包含): O(1) (给定理想的哈希表桶)

如有不妥之处请指正。它们只是我对实现/哈希表的一般了解的最佳猜测。