字典实现（平衡二叉搜索树与哈希表）
在什么情况下使用平衡二叉搜索树而不是哈希表来实现字典ADT会更好？
我的假设是使用二叉搜索树总是更好，因为它的自然排序。
但哈希表的搜索时间确实可以与 O(1) 一样好，而二叉树的搜索时间则为 O(logn) 。
所以我不确定情况会怎样。
Under what circumstances would it be better to implement a Dictionary ADT using a balanced binary search tree rather than a hash table?
My assumption was that it is always better to use a binary search tree because of its natural ordering.
But it's true that the hash table's search time can be as good as O(1) , v.s. O(logn) for the binary tree.
so I'm not sure what the circumtaces would be.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
当哈希表被填满并且需要重新分配内存时（在硬实时系统的上下文中），哈希表可能会出现性能问题。二叉树不存在这个问题。
哈希表需要比实际使用更多的内存，而二叉树则使用所需的内存。
Hash tables might have a performance issue when they get filled up and need to reallocate memory (in the context of a hard real-time system).Binary trees don't have this issue.
Hash tables need more memory than they actually use, where as binary trees use as much memory as they need.
您的问题已经包含答案：
如果您不需要任何内在排序，则使用哈希表以获得更好的性能。如果您的要求需要某种排序，那么请考虑使用树。
Your question already contains the answer:
If you don't require any intrinsic ordering then use a hashtable for better performance. If your requirements demand some kind of ordering then consider using a tree.
Dictionary 的时间复杂度是：
那么你在哪里使用 BST 和 Dictionary 呢？以下是 BST 的一些主要优点。
The time complexity for Dictionary is:
So where do you use BST vs Dictionary? Here are some main advantages of BST.