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

Question

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

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

Answer 1

与 HashMap 在插入新节点时重新分配其内部结构不同，TreeMap 通常不会在添加新节点时重新分配其节点。可以非常粗略地说明 ArrayList 和 LinkedList 之间的区别:第一个重新分配以调整大小，而第二个则没有。这就是为什么设置 TreeMap 的初始大小与尝试设置 LinkedList 的初始大小大致一样毫无意义。

速度差异是由于两个容器的时间复杂度不同:将N个节点插入到一个HashMap中是O(n) ，而对于 TreeMap，它是 O(N*LogN)，对于 1000000 个节点，这大约是 渐近 差的 20 倍。尽管由于各个算法规定的常数不同，渐近复杂度的差异不会直接转化为时序差异，但它是决定哪种算法在非常大的输入上更快的好方法。