由于使用splay树进行缓存，我想知道当我想有效缓存时，Splay Tree相对于HashTable有何优势？
什么时候我应该更喜欢八卦树而不是哈希表？
我想这是一个比BST更专业的案例，请不要链接到BST vs Hashtable答案。
最佳答案
这实际上取决于您所说的效率。
如果它在数据结构所占用的存储空间上，它们将是相同的。另一方面，当我们谈论时间复杂性时，它仍然取决于如何使用您的数据结构。
如果您的用户说，使用您的数据结构的方式是他们将访问非常相似的数据（每次都是相关数据），那么使用splay树进行缓存将非常有用，因为它的最坏情况围绕O（log n），而散列表最坏的情况是O（n）。
当哈希表存储在少于3个存储桶中或更糟的情况下，仅将1个存储桶，链或线程存储在哈希表中时，哈希表将真正无法正常工作。我想您可以想象当您尝试访问数据时会发生什么。
但通常在缓存方面，哈希表会很好地工作，因为它的平均时间复杂度为O（1）。
您也可以这样想。如果要使数据结构更快地访问“最近” /“访问最多”的数据，则可以考虑使用八叉树。但是，如果您希望自己的数据结构能够轻松访问不同类型的数据，则可以考虑使用哈希表。
您还要注意，确保选择一个良好的哈希函数，表大小和数据结构以在存储桶中使用以使其与您的用例一起使用非常重要。
实际上，将两者结合也可以:)
这实际上只是基于我的意见，因此希望我有所帮助！这确实是一个非常肤浅的比较，我建议您只是谷歌搜索缓存时两者的工作原理，并进行自己的比较！荣誉！