为什么Java的TreeMap不允许初始大小？

Question

加载1 000 000个数字需要2秒才能加载到树形图(二叉搜索树)中,但需要几毫秒才能加载到hashmap(在java中).
两者之间的唯一区别是我可以看到我可以设置一个hashmap的初始大小,因此它不需要经常重新调整大小.

假设TreeMap的数组的初始大小应该能够设置,我错了吗？它有这么慢的原因吗？
是否存在逻辑上的原因导致无法设置TreeMap或任何通用二叉搜索树的大小,或者这是错误的？

Answer 1

与HashMap插入新内核时重新分配其内部结构不同,TreeMap通常不会在添加新节点时重新分配其节点.差异可以非常宽松地说明为a ArrayList和a 之间LinkedList:第一个重新分配调整大小,而第二个重新分配调整大小.这就是为什么设置a的初始大小TreeMap与尝试设置a的初始大小大致毫无意义的原因LinkedList.

速度差异是由于两个容器的时间复杂度不同:将N节点插入到a HashMap中O(n),而对于TreeMap它来说O(N*LogN),1000000个节点大约是20次渐近差.虽然渐近复杂度的差异并不直接转化为时序差异,因为各个算法决定了不同的常数,但它可以作为决定哪种算法在非常大的输入上更快的好方法.

Answer 2

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

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

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

它这么慢有什么不同的原因吗？

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

笔记：

1. TreeMap使用给出平衡树的二叉树组织，因此O(log2N)是最坏情况的查找时间。
2. HashMap性能取决于散列函数和密钥空间的碰撞率。在最坏的情况下，所有的键最终都在同一个哈希链上，aHashMap有O(N)查找。
3. 理论上，当您达到最大可能的散列数组大小时，HashMap性能就会变得O(N)更好；即 ~2^31 个条目。但是如果你有HashMap这么大的一个，你可能应该寻找一个具有更好内存使用和垃圾收集特性的替代映射实现。