Red black tree implementation in Hashmap of java 8 without comparator

Question

Treemap uses red-black tree internally for implementation. Treemap takes Comparable<> or Comparator<> as parameter which red-black tree uses for inserting data in binary search tree.

From java 8, hash map has started using red-black tree once threeshold of linklist is reached in case of hash collision. My question is, for custom class I implement equals() and hashcode() but not comparator and use this custom class as key in hashmap then how red black tree will work without comparator in case of hash collision.

@Holger If the keys are not Comparable and when we have hash collisions, then does it use a combination of binary search and linear search? Binary search for the keys with distinct hash code and use linear search for those keys that have the same hash code? — Thiyagu
– Thiyagu, Commented Jun 24, 2021 at 7:44
Yes, that’s how the lookup works. As discussed in this Q&A, it will still build a binary tree for those keys, but for the subtree where all keys have the same hash code and are not comparable, the search has to run through both branches. — Holger
– Holger, Commented Jun 24, 2021 at 7:55

anonymous · Accepted Answer · 2021-06-24 08:05:43Z

1

Summarizing my understanding for other viewers of this question:

If there is bucket collision(which is not necessarily hash code collision), then binary tree comes in picture and searches for hashcode
if hash code is same then it will rely on comparable implementation of key of hashmap.
If key has not implemented comparable then both(left and right) branches of tree will be traversed in this scenario.

answered Jun 24, 2021 at 8:05

anonymous

5713 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Red black tree implementation in Hashmap of java 8 without comparator

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related