在设计像字典这样的东西时推荐的数据结构？

Question

TRIE是最值得推荐的数据结构,同时设计类似于存储单词的字典吗？是否有其他改善时间或内存性能的替代方案？

我相信如果没有碰撞,哈希可能会很好但是内存需求开始变得不好重叠的单词:重叠,重叠,重叠,重叠,重叠都会占用独占存储,而我们可以在trie中共享空间.

编辑:感谢@Moron和大家提供的非常有用的答案.我同意 - 生成散列键是O(n),因此是TRIE搜索.然而,对于哈希事物可能会更糟糕,链接增加时间,而对于TRIE,这不会发生.我担心的是,对于TRIE中的每个节点,我需要保留一个指针,如果字典大小很小,它可能正在吹东西.

Answer 1

与Hash表相比,trie具有以下优点:

1. O(m)与不完美的哈希表相比,查找特里结构中的数据在最坏的情况下,时间更快.不完美的哈希表可能存在关键冲突.密钥冲突是将不同密钥的哈希函数映射到哈希表中的相同位置.不完美的哈希表中的最坏情况查找速度是O(N)时间,但更典型的是O(1),O(m)花费时间来评估哈希.
2. trie中没有不同键的冲突.
3. 如果单个键与多个值相关联,则仅在存储键冲突的散列表桶中类似的trie中的桶才是必需的.
4. 随着更多密钥被添加到trie中,不需要提供散列函数或更改散列函数.
5. 特里可以按键提供条目的字母顺序.

尝试有以下缺点:

1. 在某些情况下,尝试可能比查找数据的哈希表更慢,特别是如果数据直接在硬盘驱动器或其他辅助存储设备上访问,其中随机访问时间比主存储器高.
2. 将所有键表示为字符串并不容易,例如浮点数 - 使用其编码的位串的简单编码导致长链和前缀不是特别有意义.

如果缺点是你可以忍受的东西,我建议你去看看.

来源:维基百科:Trie#作为其他数据结构的替代品