最近一个面试问题让我感到不确定。
对于 TreeMap 和 HashMap 中的 get() 方法，它的性能如何？
a) 平均：常数（与 n 无关） 最差：常数（与 n 无关）
b) 平均：常数（与 n 无关） 最差：与 log(n) 成正比
c) 平均：常数（与 n 无关） 最差：与 (n) 成正比
d) 平均：与 log(n) 成比例 最差：与 (n) 成比例
哪个是对的？
问问题
6910 次
2 回答
8
此实现为基本操作（get 和 put）提供恒定时间性能，假设哈希函数将元素正确地分散在桶中。
但是请注意，修改负载因子（默认值 = 0.75）可能会对HashMap.
作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。
可以通过使用重载构造函数之一来强制执行不同的负载因子值。
此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。
于 2013-03-03T17:20:34.890 回答
0
答案是d
树图实现了一个红黑树，因此平均情况是 o(log n)
Hashmap 在最坏的情况下取 o(n)
于 2013-03-03T17:27:26.670 回答