hashtable - 哈希表的大 O 与二叉搜索树

Question

哪个需要更长的时间？

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

将哈希表的项目按排序顺序打印出来需要更长的时间，因为哈希表永远不会正确排序？BST 是什么？

score 13 · Accepted Answer

你是对的。哈希表是按一些哈希函数排序的，而不是按照它们的自然排序顺序，所以你必须提取所有条目 O(N) 并对它们进行排序 O(NlogN) 而你可以在 O( N)。

但是请注意，例如，在 Java 中，有一个 LinkedHashSet 和 LinkedHashMap 可以为您提供 Hash 的一些优点，但可以按照添加的顺序对其进行遍历，因此您可以对其进行排序并能够在其中遍历它排序顺序以及通过哈希提取项目。

score 3 · Accepted Answer

正确，哈希表没有按照您可能想要的方式“排序”。哈希表中的元素通常不是完全排序的，尽管排列通常在排序的附近。但是它们是根据散列函数排列的，对于相似的短语，散列函数通常有很大的不同。这不是人类会使用的任何度量标准。

如果您对收藏所做的主要事情是按排序顺序打印它，那么您最好使用某种类型的 BST。

score 2 · Accepted Answer

二叉搜索树的存储方式是，如果您进行深度优先遍历，您将按排序顺序找到项目（假设您具有一致的比较功能）。简单地返回树中已经存在的项目的大 O 将是遍历树的大 O。

您对哈希表是正确的，它们没有排序。事实上，为了枚举普通哈希表中的所有内容，您必须检查每个存储桶以查看其中的内容，将其拉出，然后对得到的内容进行排序。很多工作才能从中得到一个排序列表。

score 1 · Accepted Answer

正确，打印存储在哈希表中的排序数据会更慢，因为哈希表不是排序数据。它只是为您提供了一种快速查找特定项目的方法。在“大 O 表示法”中，据说可以在恒定时间内找到项目，即 O(1) 时间。

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

因此，如果您的目标是打印排序列表，那么最好将数据以排序顺序（即二叉树）存储。

score 0 · Accepted Answer

这带来了几个有趣的问题。考虑到以下情况，搜索树是否仍然更快？

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

score 0 · Accepted Answer

0

另请查看 Skip List vs. Binary Tree 的相关注意事项：Skip List vs. Binary Tree

于 2009-05-13T20:21:58.777 回答

6 回答 6