11

加载 1 000 000 个数字需要 2 秒才能加载到树图（二叉搜索树）中，但需要毫秒才能加载到哈希图中（在 java 中）。
两者之间的唯一区别是我可以看到我可以设置哈希图的初始大小，因此它不需要不断地重新调整大小。

假设 TreeMap 的数组的初始大小应该能够设置，我错了吗？它这么慢有其他原因吗？
为什么不能设置 TreeMap 或任何通用二叉搜索树的大小是否有逻辑原因，或者这是错误的？

4

4 回答 4

13

与HashMap在插入新节点时重新分配其内部不同的是，TreeMap通常不会在添加新节点时重新分配其节点。可以非常松散地说明差异为 anArrayList和 a之间的差异LinkedList：第一个重新分配以调整大小，而第二个则没有。这就是为什么设置 a 的初始大小TreeMap与尝试设置 a 的初始大小大致相同的原因LinkedList。

速度差异是由于两个容器的时间复杂度不同：将N节点插入 a HashMapis O(n)，而对于TreeMapit's O(N*LogN)，对于 1000000 个节点，大约是 20 倍的渐近差异。尽管由于各个算法规定的常数不同，渐近复杂度的差异不会直接转化为时序差异，但它可以作为一种很好的方法来确定哪种算法在非常大的输入上会更快。

于 2013-08-26T00:24:19.243 回答
5

假设 TreeMap 的数组的初始大小应该能够设置，我错了吗？

是的，这个假设是不正确的。ATreeMap没有数组。ATreeMap使用具有 2 个子节点的二进制节点。

如果您建议将树节点中的子节点数量作为参数，那么您需要弄清楚它对搜索时间的影响。而且我认为它将搜索时间从哪里变成了O(log2N)元素O(log2M * log2(N/M))数量N和M节点子节点的平均数量。（而且我正在做出一些乐观的假设......）这不是“胜利”。

它这么慢有其他原因吗？

是的。TreeMap在最佳情况下，a（大）相对于（大）慢的原因HashMap是使用具有 N 个条目的平衡二叉树进行查找需要大致查看log2N树节点。相比之下，在最佳HashMap查找中涉及 1 个哈希码计算并查看哈希O(1)链节点。

笔记：

  1. TreeMap使用提供平衡树的二叉树组织，因此O(log2N)最坏情况的查找时间也是如此。
  2. HashMap性能取决于散列函数和密钥空间的冲突率。在最坏的情况下，所有键都在同一个哈希链上，aHashMap有O(N)查找。
  3. 理论上，当您达到最大可能的哈希数组大小时，HashMap性能就变成了；O(N)即〜2 ^ 31个条目。但是，如果您有HashMap那么大的内存，您可能应该寻找具有更好内存使用和垃圾收集特性的替代地图实现。
于 2013-08-26T00:39:55.610 回答
4

Treemap 总是平衡的。每次将节点添加到树时，它必须确保节点都按提供的比较器排序。您没有指定大小，因为树形图是为平滑排序的节点组设计的，并且可以轻松遍历节点。

Hashmap 需要有足够的可用空间来存储您在其中存储的内容。我的教授总是告诉我，它需要的空间量是对象或您存储在该哈希图中的任何内容的 5 倍。因此，从最初创建 Hashmap 开始指定大小可以提高 hashmap 的速度。否则，如果进入 hashmap 的对象比您计划的要多，则 hashmap 必须“调整大小”。

（编辑拼写）

于 2013-08-26T00:36:43.713 回答
4

假设 TreeMap 的数组的初始大小应该能够设置，我错了吗？

是的。它没有数组。它有一棵树。

于 2013-08-26T01:02:08.093 回答