Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LinkedTreeMap效率怎么样,和HashMap相比呢? #1596

Open
wenbochang888 opened this issue Oct 22, 2019 · 4 comments
Open

LinkedTreeMap效率怎么样,和HashMap相比呢? #1596

wenbochang888 opened this issue Oct 22, 2019 · 4 comments
Labels

Comments

@wenbochang888
Copy link

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

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

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

@wenbochang888
Copy link
Author

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

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

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

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

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

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

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

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

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

@ghost
Copy link

ghost commented Oct 30, 2019

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
Copy link
Author

@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
Copy link
Collaborator

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants