二叉搜索树相对于哈希表的优势 [英] Advantages of Binary Search Trees over Hash Tables

问题描述

二叉搜索树相对于哈希表的优势是什么?

What are the advantages of binary search trees over hash tables?

哈希表可以在 Theta(1) 时间内查找任何元素，并且添加元素同样容易......但我不确定相反的优势.

Hash tables can look up any element in Theta(1) time and it is just as easy to add an element....but I'm not sure of the advantages going the other way around.

推荐答案

请记住二叉搜索树(基于引用)是内存高效的.他们不会保留比他们需要的更多的内存.

Remember that Binary Search Trees (reference-based) are memory-efficient. They do not reserve more memory than they need to.

例如，如果一个散列函数的范围是 R(h) = 0...100，那么你需要分配一个包含 100 个(指向)元素的数组，即使你只是散列 20 个元素.如果您要使用二叉搜索树来存储相同的信息，您将只分配您需要的空间，以及一些有关链接的元数据.

For instance, if a hash function has a range R(h) = 0...100, then you need to allocate an array of 100 (pointers-to) elements, even if you are just hashing 20 elements. If you were to use a binary search tree to store the same information, you would only allocate as much space as you needed, as well as some metadata about links.

这篇关于二叉搜索树相对于哈希表的优势的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！