den*_*631 5 hashtable hashmap time-complexity binary-search-tree data-structures
由于伸展树用于缓存，我想知道当我想高效缓存时，伸展树相对于哈希表有什么优势？
什么时候我应该更喜欢展开树而不是哈希表？
我想这是一个比 BST 更特殊的情况，请不要链接到 BST 与 Hashtable 答案。
这实际上取决于你所说的效率是什么意思。
如果它在数据结构消耗的存储/空间上，它们将是相同的。另一方面，当我们谈论时间复杂度时，它仍然取决于数据结构的使用方式。
如果您的用户说，以他们将访问非常相似的数据（每次相关数据）的方式使用您的数据结构，那么使用展开树进行缓存会很棒，因为它的最坏情况围绕 O(log n) 进行，而哈希表最坏情况为 O(n)。
哈希表工作得非常糟糕的一个例子是，当你的哈希值存储在少于 3 个桶中，或者更糟糕的是，只有 1 个桶、链或线程中时。我想您可以想象当您尝试访问数据时会发生什么。
但一般来说，当涉及到缓存时，哈希表会工作得很好，因为它的平均时间复杂度为 O(1)。
你也可以这样想。如果您想要的是让您的数据结构更快地访问“最新”/“访问次数最多”的数据，那么您可以考虑使用展开树。但如果您希望数据结构能够轻松访问不同类型的数据，那么您需要考虑使用哈希表。
您还需要注意的是，确保选择一个好的哈希函数、表大小和数据结构以在存储桶中使用，以使其能够很好地适合您的用例，这一点非常重要。
事实上，将两者结合起来也可以工作:)
这实际上只是基于我的意见，所以我希望我能有所帮助！这确实是一个非常浅薄的比较，我建议您在谷歌上搜索一下两者在缓存方面的工作原理并进行自己的比较！荣誉！
| 归档时间： |
|
| 查看次数： |
888 次 |
| 最近记录： |