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

问题描述

散列表可以在Theta（1）时间内查找任何元素，它也同样容易添加一个元素....但我不知道其他方式的优势。

解决方案

记住二进制搜索树（基于参考）是记忆效率高的。他们没有保留比他们需要的更多的内存。

例如，如果哈希函数的范围是 R（h）= 0 .. .100 ，那么你需要分配一个100（指针）元素的数组，即使你只是散列20个元素。如果要使用二叉搜索树来存储相同的信息，则只需分配所需的空间以及关于链接的一些元数据。

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

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.

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屋！