哈希表与 Big O 的比较二叉搜索树

题

哪个需要更长的时间？

按排序顺序打印二叉搜索树中存储的所有项目，或按排序顺序打印哈希表中存储的所有项目。

按排序顺序打印哈希表的项目会花费更长的时间，因为哈希表永远不会正确排序？BST 是？

解决方案

您是正确的。哈希表是由一些散列函数来分类，而不是由他们的自然排序，所以你必须提取所有条目O（N），并对其进行排序O（NlogN），而你可以在O的自然顺序遍历二叉搜索树（ N）。

不过请注意，在Java中，例如，有一个LinkedHashSet和LinkedHashMap中，让你一些可以在其加入的顺序经过哈希的，但其优势，所以你可以对它进行排序，并能够穿越它在排序顺序以及由散列提取的项目。

其他提示

正确，哈希表是不是在你可能想要的方式“排序”。在哈希表的元素是尚未完全排序，通常情况下，虽然安排往往是那种在某种附近。但它们根据散列函数，这通常是类似的短语似地不同地布置。这不是一个排序任何度量的人会使用。

如果您与您的收藏做更主要的是在打印的排序顺序，你最好使用某种类型的BST的。

二叉搜索树存储的方式，如果你做一个深度优先遍历，你会发现在有序的项目（假设你有一个比较一致的功能）。大O的只是已经返回项目树将遍历树的大O。

您即将哈希表是正确的，它们没有排序。事实上，为了在一个普通的哈希表中列举的一切，你必须检查每一个桶，看看是什么在那里，将其拉出，然后排序你会得到什么。工作很多得到一个排序列表了这一点。

因为哈希表未排序数据存储在哈希表

正确，印刷排序的数据将是慢。它只是给你一个快速的方法来找到特定项目。在“大O符号”这是说，该项目可在固定的时间可以找到，即O（1）时间。

在另一方面，你可以找到在“对数时间”二叉搜索树中的项目（O（log n）的），因为该数据已排序你。

因此，如果你的目标是要打印排序的列表，你是好得多具有存储在排序的顺序的数据（即二进制树）。

享受，

罗伯特C. Cartaino

这带来了一些有趣的问题。考虑到以下因素，搜索树是否仍然更快？

合并哈希表和 BST 的设置时间？
如果哈希算法产生一个排序的单词列表。从技术上讲，您可以创建一个使用相应算法的哈希表。在这种情况下，BST 与哈希表的速度必须归结为按排序顺序填充哈希表所需的时间。

还检查了跳跃列表的相关考虑与二叉树：跳跃列表与二叉树

许可以下： CC-BY-SA 和归因