由于 Java 使用红黑树来实现 TreeMap 类，因此 put() 和 get() 的效率为 lg(N)，其中 N = 不同键的数量，或 N = 您计划执行的插入/检索次数?
例如，假设我想使用
TreeMap<Integer, ArrayList<String>>
存储以下数据：
100 万 <1, "bob"> 对和 100 万 <2, "jack"> 对（字符串被插入到与键对应的数组列表值中）
最终的树形图将有 2 个键，每个键存储数百万个“bob”或“jack”字符串的数组列表。时间效率是 lg(2mil) 还是 lg(2)？我猜它是 lg(2) 因为这就是红黑树的工作原理，但只是想检查一下。
具有 2 对的 TreeMap 的性能将表现为 N=2，无论之前进行了多少重复添加。多余的添加没有“记忆”，因此它们不可能产生任何开销。
所以是的，您可以非正式地假设时间效率为“log 2”。
尽管它相当没有意义，因为大 O 表示法旨在与渐近效率相关，而不是与小尺寸相关。对于 N=2，O(N^3) 算法很容易比 O(log N) 算法更快。
对于这种情况，树形图就是lg(n)您n=2所描述的位置。地图中只有 2 个值：一个数组列表和另一个数组列表。无论其中包含什么，地图只知道两个值。
虽然不直接关心您的问题，但您可能需要考虑不为此使用树形图......我的意思是，您打算如何访问存储在“bob”或“jack”列表中的数据？这些将是O(n)搜索，除非您要对它们使用某种二进制搜索或其他东西，n这里是 100 万。如果您详细说明最终目标，也许可以实现更全面的解决方案。