三叉树VS哈希表 [英] Ternary Tree Vs Hash Table

问题描述

我需要知道，如果一个三叉树比的hash表。

I need to know if a ternary tree is better than a hash table.

我的答复碰到这个问题<一href="http://stackoverflow.com/questions/822752/should-i-learn-haskell-or-f-if-i-already-know-ocaml/">another问题我有如果有人说，三元树往往比哈希表快。我发现很难相信，所以我决定稍微研究了进去。

I came across this question in a reply to another question I had where someone said that ternary trees are often faster than hash tables. I found that hard to believe, so I decided to research a little into it.

这普林斯顿一家网站似乎是信仰的源泉。我把其被描述为为O（log的n + k）的其中n是存储的字的数目，k是密钥的长度一看算法。

This one website from Princeton appears to be the source of the belief. I took a look at algorithm which is described to be O(log n + k) where n is the number of words stored, and k is the length of the key.

在我看来，这可能是更快的唯一方法是，如果你经常寻找那些尚未存储的元素。困扰我，另一件事是，一个线索的非连续爬行往往会引起你打已换出的页面，但是这是否是一个重大的影响只能通过基准测试中可以看出。

It seems to me that the only way this could be faster is if you are often searching for elements that are not already stored. Another thing that bothers me, is that the non-continuous crawling of a trie would tend to cause you to hit pages that have been swapped out, but whether this is a major effect could only be seen through benchmarks.

现在我知道，有可能利弊，他们两个，如果是的话，我想知道它们是什么。基准也是有帮助的。

Now I know that there are probably pros and cons to both of them, and if so, I want to know what they are. Benchmarks are also helpful.

推荐答案

下面是我从博士收集多布斯文章从普林斯顿大学访问链接你给了：

Here is what I gather from the Dr. Dobbs Article reachable from the Princeton link you gave:

1. 在三元搜索树均达到比一些搜索问题哈希表快10％。他们有时慢 - 这取决于大大使用的机器上
。
2. TRTS是由两个计算机科学的最优秀的头脑调整自定义数据结构 - 宾利乔恩和罗伯特·塞奇威克既写的好 教科书的，并已完成了他们的份额实际编程中。哈希表被认为是径流式的磨。
3. 在所涉及的常量显著，郝Wooi Lin说。
4. 总之，这取决于你正在解决问题。更快的开发时间，并且在很多编程语言的哈希表几乎无处不在的支持往往比在运行时将性能提升百分之十更重要。

1. Ternary Search Trees are up to 10% faster than hash tables on some search problems. They are sometimes slower - depending vastly on the machine used.
2. TRTs are a custom data structure tuned by two of the finest minds of Computer Science - Jon Bentley and Robert Sedgewick both wrote good textbooks, and have done their share of practical programming. Hash tables are considered run-of-the-mill.
3. The constants involved are significant, as Hao Wooi Lin says.
4. Overall, this depends on the problem you are solving. The faster development time and almost ubiquitous support for hash tables in many programming languages are often more important than a ten-percent improvement in run time.

这篇关于三叉树VS哈希表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！