Why doesn't java's HashMap just use trees for collision chaining2019 Community Moderator ElectionIs there any reason to have 8 on TREEIFY_THRESHOLD in Java Hashmap?When do you use Java's @Override annotation and why?Why does Java's hashCode() in String use 31 as a multiplier?Why doesn't Java allow overriding of static methods?Why don't Java's +=, -=, *=, /= compound assignment operators require casting?Best way to make many generic objectsWhy Don't Hash Tables for Strings Simply Use This Collision-Less Function? (included below)Why doesn't RecyclerView have onItemClickListener()?Why does java.util.HashMap use a linked list internallyHow do java implement hash map chain collision resolutionWhy hash maps in Java 8 use binary tree instead of linked list?
My adviser wants to be the first author
It's a yearly task, alright
PTIJ: Who should pay for Uber rides: the child or the parent?
How to answer questions about my characters?
Brexit - No Deal Rejection
Dot in front of file
Good allowance savings plan?
Ban on all campaign finance?
Is a lawful good "antagonist" effective?
2D counterpart of std::array in C++17
What is IP squat space
PlotLabels with equations not expressions
Counting certain elements in lists
How could a female member of a species produce eggs unto death?
How is the Swiss post e-voting system supposed to work, and how was it wrong?
What options are left, if Britain cannot decide?
The use of "touch" and "touch on" in context
Calculus II Professor will not accept my correct integral evaluation that uses a different method, should I bring this up further?
Why using two cd commands in bash script does not execute the second command
Can elves maintain concentration in a trance?
Latest web browser compatible with Windows 98
Is it true that real estate prices mainly go up?
Will a pinhole camera work with instant film?
Using "wallow" verb with object
Why doesn't java's HashMap just use trees for collision chaining
2019 Community Moderator ElectionIs there any reason to have 8 on TREEIFY_THRESHOLD in Java Hashmap?When do you use Java's @Override annotation and why?Why does Java's hashCode() in String use 31 as a multiplier?Why doesn't Java allow overriding of static methods?Why don't Java's +=, -=, *=, /= compound assignment operators require casting?Best way to make many generic objectsWhy Don't Hash Tables for Strings Simply Use This Collision-Less Function? (included below)Why doesn't RecyclerView have onItemClickListener()?Why does java.util.HashMap use a linked list internallyHow do java implement hash map chain collision resolutionWhy hash maps in Java 8 use binary tree instead of linked list?
For my computer science data structures class we had an assignment on hashing and java's HashMaps. Through this assignment I learned that collisions are handled as linked lists for the first 8 nodes, followed by a binary tree (or red black tree) for the rest. Why... Why aren't they just handled as tree for O(log n) efficiency?
The only writes ups that I could find were that when Java 8 released, it increased the efficiency of the chains by handling them this way instead of strictly linked list, which would be O(n).
If anyone has any insight on this it would be greatly appreciated.
Thanks,
Matt
java
asked Mar 6 at 18:53
crickoncrickon
11
|
show 5 more comments
For my computer science data structures class we had an assignment on hashing and java's HashMaps. Through this assignment I learned that collisions are handled as linked lists for the first 8 nodes, followed by a binary tree (or red black tree) for the rest. Why... Why aren't they just handled as tree for O(log n) efficiency?
The only writes ups that I could find were that when Java 8 released, it increased the efficiency of the chains by handling them this way instead of strictly linked list, which would be O(n).
If anyone has any insight on this it would be greatly appreciated.
Thanks,
Matt
java
asked Mar 6 at 18:53
crickoncrickon
11
4
Keeping a tree balanced requires O(log n) insertions and deletions, as opposed to a list's O(1), so it's not strictly always better. The red black tree is really only there to mitigate poorly implemented hash functions (or, I suppose, random bad luck with regards to collisions). Making every bucket a tree would make performance worse in the general case.
– Michael
Mar 6 at 19:01
I don't think I explained my assignment properly. We were forcing collisions to see how HashMap handles them. My question is more of why the whole chain is not handled with a tree. Why are the first 8 nodes linked and treeify only starts when the chain becomes longer than that.
– crickon
Mar 7 at 0:11
Yes. I already answered that. A tree is not always used because a tree is not always best.
– Michael
Mar 7 at 0:16
Correct me if i'm wrong, wouldn't a poorly implemented tree still have the same performance as a LinkedList.
– crickon
Mar 7 at 0:17
No. Like I said, a tree is slower to insert and remove. And anyway, big O does not tell the whole story. Something can be constant time and still be slow (considerThread.sleep(10000)).
– Michael
Mar 7 at 0:30
|
show 5 more comments
For my computer science data structures class we had an assignment on hashing and java's HashMaps. Through this assignment I learned that collisions are handled as linked lists for the first 8 nodes, followed by a binary tree (or red black tree) for the rest. Why... Why aren't they just handled as tree for O(log n) efficiency?
The only writes ups that I could find were that when Java 8 released, it increased the efficiency of the chains by handling them this way instead of strictly linked list, which would be O(n).
If anyone has any insight on this it would be greatly appreciated.
Thanks,
Matt
java
asked Mar 6 at 18:53
crickoncrickon
11
For my computer science data structures class we had an assignment on hashing and java's HashMaps. Through this assignment I learned that collisions are handled as linked lists for the first 8 nodes, followed by a binary tree (or red black tree) for the rest. Why... Why aren't they just handled as tree for O(log n) efficiency?
The only writes ups that I could find were that when Java 8 released, it increased the efficiency of the chains by handling them this way instead of strictly linked list, which would be O(n).
If anyone has any insight on this it would be greatly appreciated.
Thanks,
Matt
java
java
asked Mar 6 at 18:53
crickoncrickon
11
asked Mar 6 at 18:53
crickoncrickon
11
edited Mar 7 at 0:14
crickon
asked Mar 6 at 18:53
crickoncrickon
11
asked Mar 6 at 18:53
crickoncrickon
11
asked Mar 6 at 18:53
crickoncrickon
11
11
4
Keeping a tree balanced requires O(log n) insertions and deletions, as opposed to a list's O(1), so it's not strictly always better. The red black tree is really only there to mitigate poorly implemented hash functions (or, I suppose, random bad luck with regards to collisions). Making every bucket a tree would make performance worse in the general case.
– Michael
Mar 6 at 19:01
I don't think I explained my assignment properly. We were forcing collisions to see how HashMap handles them. My question is more of why the whole chain is not handled with a tree. Why are the first 8 nodes linked and treeify only starts when the chain becomes longer than that.
– crickon
Mar 7 at 0:11
Yes. I already answered that. A tree is not always used because a tree is not always best.
– Michael
Mar 7 at 0:16
Correct me if i'm wrong, wouldn't a poorly implemented tree still have the same performance as a LinkedList.
– crickon
Mar 7 at 0:17
No. Like I said, a tree is slower to insert and remove. And anyway, big O does not tell the whole story. Something can be constant time and still be slow (considerThread.sleep(10000)).
– Michael
Mar 7 at 0:30
|
show 5 more comments
4
Keeping a tree balanced requires O(log n) insertions and deletions, as opposed to a list's O(1), so it's not strictly always better. The red black tree is really only there to mitigate poorly implemented hash functions (or, I suppose, random bad luck with regards to collisions). Making every bucket a tree would make performance worse in the general case.
– Michael
Mar 6 at 19:01
I don't think I explained my assignment properly. We were forcing collisions to see how HashMap handles them. My question is more of why the whole chain is not handled with a tree. Why are the first 8 nodes linked and treeify only starts when the chain becomes longer than that.
– crickon
Mar 7 at 0:11
Yes. I already answered that. A tree is not always used because a tree is not always best.
– Michael
Mar 7 at 0:16
Correct me if i'm wrong, wouldn't a poorly implemented tree still have the same performance as a LinkedList.
– crickon
Mar 7 at 0:17
No. Like I said, a tree is slower to insert and remove. And anyway, big O does not tell the whole story. Something can be constant time and still be slow (considerThread.sleep(10000)).
– Michael
Mar 7 at 0:30
4
4
Keeping a tree balanced requires O(log n) insertions and deletions, as opposed to a list's O(1), so it's not strictly always better. The red black tree is really only there to mitigate poorly implemented hash functions (or, I suppose, random bad luck with regards to collisions). Making every bucket a tree would make performance worse in the general case.
– Michael
Mar 6 at 19:01
Keeping a tree balanced requires O(log n) insertions and deletions, as opposed to a list's O(1), so it's not strictly always better. The red black tree is really only there to mitigate poorly implemented hash functions (or, I suppose, random bad luck with regards to collisions). Making every bucket a tree would make performance worse in the general case.
– Michael
Mar 6 at 19:01
I don't think I explained my assignment properly. We were forcing collisions to see how HashMap handles them. My question is more of why the whole chain is not handled with a tree. Why are the first 8 nodes linked and treeify only starts when the chain becomes longer than that.
– crickon
Mar 7 at 0:11
I don't think I explained my assignment properly. We were forcing collisions to see how HashMap handles them. My question is more of why the whole chain is not handled with a tree. Why are the first 8 nodes linked and treeify only starts when the chain becomes longer than that.
– crickon
Mar 7 at 0:11
Yes. I already answered that. A tree is not always used because a tree is not always best.
– Michael
Mar 7 at 0:16
Yes. I already answered that. A tree is not always used because a tree is not always best.
– Michael
Mar 7 at 0:16
Correct me if i'm wrong, wouldn't a poorly implemented tree still have the same performance as a LinkedList.
– crickon
Mar 7 at 0:17
Correct me if i'm wrong, wouldn't a poorly implemented tree still have the same performance as a LinkedList.
– crickon
Mar 7 at 0:17
No. Like I said, a tree is slower to insert and remove. And anyway, big O does not tell the whole story. Something can be constant time and still be slow (consider
Thread.sleep(10000)).– Michael
Mar 7 at 0:30
No. Like I said, a tree is slower to insert and remove. And anyway, big O does not tell the whole story. Something can be constant time and still be slow (consider
Thread.sleep(10000)).– Michael
Mar 7 at 0:30
|
show 5 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55030269%2fwhy-doesnt-javas-hashmap-just-use-trees-for-collision-chaining%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55030269%2fwhy-doesnt-javas-hashmap-just-use-trees-for-collision-chaining%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
Keeping a tree balanced requires O(log n) insertions and deletions, as opposed to a list's O(1), so it's not strictly always better. The red black tree is really only there to mitigate poorly implemented hash functions (or, I suppose, random bad luck with regards to collisions). Making every bucket a tree would make performance worse in the general case.
– Michael
Mar 6 at 19:01
I don't think I explained my assignment properly. We were forcing collisions to see how HashMap handles them. My question is more of why the whole chain is not handled with a tree. Why are the first 8 nodes linked and treeify only starts when the chain becomes longer than that.
– crickon
Mar 7 at 0:11
Yes. I already answered that. A tree is not always used because a tree is not always best.
– Michael
Mar 7 at 0:16
Correct me if i'm wrong, wouldn't a poorly implemented tree still have the same performance as a LinkedList.
– crickon
Mar 7 at 0:17
No. Like I said, a tree is slower to insert and remove. And anyway, big O does not tell the whole story. Something can be constant time and still be slow (consider
Thread.sleep(10000)).– Michael
Mar 7 at 0:30