如何在哈希表和 Trie(前缀树)之间进行选择? [英] How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?

问题描述

因此，如果我必须在哈希表或前缀树之间进行选择，有哪些区别因素会导致我选择一个而不是另一个.从我自己幼稚的角度来看，似乎使用 trie 有一些额外的开销，因为它没有存储为数组，但在运行时间方面(假设最长的键是最长的英文单词)它本质上可以是 O(1)(关于上限).也许最长的英文单词是 50 个字符?

So if I have to choose between a hash table or a prefix tree what are the discriminating factors that would lead me to choose one over the other. From my own naive point of view it seems as though using a trie has some extra overhead since it isn't stored as an array but that in terms of run time (assuming the longest key is the longest english word) it can be essentially O(1) (in relation to the upper bound). Maybe the longest english word is 50 characters?

哈希表是即时查找一旦您获得索引.然而，对键进行哈希处理以获取索引似乎很容易需要近 50 个步骤.

Hash tables are instant look up once you get the index. Hashing the key to get the index however seems like it could easily take near 50 steps.

有人可以为我提供一个更有经验的观点吗?谢谢！

Can someone provide me a more experienced perspective on this? Thanks!

推荐答案

尝试的优点:

基础知识:

• 可预测的 O(k) 查找时间，其中 k 是密钥的大小
• 如果不存在，查找时间可能少于 k 次
• 支持有序遍历
• 不需要哈希函数
• 删除很简单

新操作:

• 您可以快速查找键的前缀、枚举具有给定前缀的所有条目等.

链接结构的优点:

• 如果有很多公共前缀，它们需要的空间是共享的.
• 不可变的尝试可以共享结构.您可以构建一个仅在一个分支上不同的新树，而不是在适当的位置更新树，而在其他地方指向旧树.这对于并发、表的多个同时版本等很有用.
• 不可变的 trie 是可压缩的.也就是说，它也可以通过散列约束共享 后缀 的结构.

哈希表的优点:

• 每个人都知道哈希表，对吧?您的系统已经有一个很好的优化实施，比大多数用途的尝试都快.
• 您的密钥不需要任何特殊结构.
• 比明显的链接特里树结构更节省空间(请参阅下面的评论)

这篇关于如何在哈希表和 Trie(前缀树)之间进行选择?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！