在一个应用程序中,我将拥有大约 3000 到 30000 个字符串。 创建后(从无序文件中读取)不会经常添加很多字符串(但有时会有!)。删除字符串也不会经常发生。 将字符串与存储的字符串进行比较会经常发生。
我可以最好地使用哪种结构,哈希表、树(红-黑、Splay、....)还是有序列表(也许是 StringArray?)?
(附加说明:也将不胜感激指向良好 C# 实现的链接)
最佳答案
听起来您只需要一个哈希表。 HashSet<T>
因此似乎是理想的选择。 (您似乎不需要 key ,但如果需要,Dictionary<T>
将是正确的选择,当然。)
这里总结了 HashSet<T>
上不同操作的时间复杂度尺寸n
.它们部分基于该类型使用数组作为支持数据结构这一事实。
- 插入:通常为
O(1)
, 但可能是O(n)
如果数组需要调整大小。 - 删除:
O(1)
- 存在(包含):
O(1)
(给定理想的哈希表桶)
如有不妥之处请指正。它们只是我对实现/哈希表的一般了解的最佳猜测。
关于c# - 高效的字符串插入和搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1021873/