什麼是TreeMap＆HashMap中大小爲n的get（）方法的運行時性能？

對於TreeMap和HashMap中的get（）方法，它的性能如何？

一個）平均：常數（n無關）最差：常數（n無關）

B）平均：常數（n無關）最差：成比例的log（n）

C）平均：常數（n無關）最差：正比於（N）

d）平均：成比例的log（n）最差：數比例（n）

這是正確的嗎？

2013-03-03 DerekY

順便說一下，這是在Java – DerekY 2013-03-03 17:16:44

此實現提供穩定的性能爲基本操作（get和put），假定哈希函數將分散的桶中正確的元素。

但是請注意，修改客座率（默認值= 0.75）可能在HashMap一些運營成本有一定的影響。

作爲一般規則，默認加載因子（.75）在時間和空間成本之間提供良好的權衡。較高的值會減少空間開銷，但會增加查找成本（反映在大部分HashMap類的操作中，包括get和put）。

不同的值加載因子可以通過使用一個重載的構造函數來實施。

此實現提供了保證的log（n）的時間成本，爲的containsKey，GET，PUT和刪除操作。

2013-03-03 17:20:34

所以@ user838204是正確的（保證合理平衡）'TreeMap'的情況下混淆。 – 2013-03-03 19:00:31

對於'TreeMap'，最糟糕的是'log（n）'。沒有任何選擇表明它。 – 2013-03-03 19:12:34

對不起，讓你困惑。所以HashMap的答案是A，TreeMap的答案是：Average：與log（n）成正比最差：與log（n）成正比 – DerekY 2013-03-04 01:32:18

答案是d

樹映射implemeneted一個紅黑樹，因此平均情況下爲O（log n）的

的Hashmap花費O（N）在最壞的情況下

2013-03-03 17:27:26 Pradheep

從上面的答案，HashMap在最壞情況下是否需要恆定時間？ – DerekY 2013-03-04 01:34:58

回答