LinkedTreeMap效率怎么样,和HashMap相比呢？

[wenbochang888]

JsonObject的底层用的是LinkedTreeMap，Google自己写了一套。应该是有序的红黑树Map。 插入时间复杂度为O(lgn) + 左旋/右旋等等。查找时间复杂度为O(lgn) + 左旋/右旋等等。

而自带的HashMap，插入基本为O1, 查找基本为O1。就算有冲突，大于8，也会默认转为红黑树，优化的非常好。

那为什么Google要专门写一套呢？有人对比过效率么？

[wenbochang888]

刚刚测了一遍，效率还是有差距的。如下：

插入十万条数据测试(单位微秒)：

LinkedTreeMap花费时间为：40945
HashMap花费时间为：15017

LinkedTreeMap花费时间为：35710
HashMap花费时间为：16528

LinkedTreeMap花费时间为：37687
HashMap花费时间为：12644

获取十万条数据测试(单位微秒)：

LinkedTreeMap花费时间为：31972
HashMap花费时间为：5943

LinkedTreeMap花费时间为：32927
HashMap花费时间为：5795

LinkedTreeMap花费时间为：33777
HashMap花费时间为：6719

[lihy70]

I think the major difference is: The member elements of this object are maintained in order they were added by LinkedXXXMap, but not by HashMap. probably you should compare the performance with LinkedHashMap

[wenbochang888]

@lihy70
you can see that the gap is very obvious
So i am very curious why google use LinkedTreeMap without other map （jdk has）

Insert 100,000 data tests (in microseconds):

LinkedTreeMap花费时间为：46978
LinkedHashMap花费时间为：16244

LinkedTreeMap花费时间为：42532
LinkedHashMap花费时间为：17794

LinkedTreeMap花费时间为：45800
LinkedHashMap花费时间为：17178


Get 100,000 data tests (in microseconds):

LinkedTreeMap花费时间为：43718
LinkedHashMap花费时间为：6180

LinkedTreeMap花费时间为：41501
LinkedHashMap花费时间为：6736

LinkedTreeMap花费时间为：40812
LinkedHashMap花费时间为：7684

[Marcono1234]

The reason why LinkedTreeMap is used might be that the LinkedHashMap class (respectively HashMap) in older JDK versions was vulnerable to denial-of-service attacks, see #1992 (comment).
But this most likely does not apply to JDK >= 8 anymore.