algorithm - 就内存而言，二叉搜索树与哈希表

Question

我在互联网上听到过不同的事情，包括有人明确指出 BST 与 hast 表相比需要更少的内存，因为哈希表一次获得的内存比他们目前需要的多。

谁能告诉我每种结构与其他结构相比的优缺点，仅它在内存方面。

标签： algorithmmemorybinary-search-treehashtable

Answer 1

二叉搜索树只不过是一个链表，每个节点有 2 个指针。所需内存的数量级为 O(n) ，即与存储在其中的元素数量相同。另一方面，哈希映射通常实现为数组。所以，总是有一些未使用的空间。在这里阅读有关如何在 java 中实现哈希映射。：http: //java-performance.info/memory-consumption-of-java-data-types-2/

HashMap 建立在 Map.Entry 对象数组之上。该实现确保此数组长度始终至少等于 max(size, capacity) / load_factor。HashMap 的默认加载因子是 0.75，默认容量是 16。加载因子指定数组的哪个部分可用于存储，并且是介于 0 和 1 之间的值。加载因子越高，浪费的空间越少，但是由于冲突率的增加，HashMap 开始工作得更慢。负载因子越小，浪费的内存越多，但由于碰撞的可能性较小，HashMap 的性能正在提高。