I was curious and started learning about how TreeMap is internally implemented in Java. And, I found out that it uses Red-Black Trees for keeping the sorted order of entries based on keys.
My question is why doesn't it use an Array as buckets as well along with the red-black tree. Wouldn't that make the search average time complexity as O(1) ?
I mean like LinkedHashMap maintains insertion order using Doubly Linked List as well as entries are hashed into array buckets based on keys and capacity. Why did Java developers not make TreeMap in a similar way ? It would not make insertion more time-taking complexity wise, right, as we only have to maintain pointers to left, right, parent etc. for each entry and update these based on insertion rules for red-black tree. I mean the whole process would be same, except mapping into array buckets. And the search would become O(1) if it's also mapped to array buckets. Am I missing something here ?
TreeMap uses the comparator, and only the comparator, to look up elements.
That comparator is encouraged to be compatible with equals (and hashCode), but not required. TreeMap cannot depend on hash codes, or it would violate its own rules.
Moreover, hashing can degenerate to O(n) when many keys hash into the same bucket, whereas binary search trees are guaranteed to be O(log n). This is, in fact, why HashMaps fall back to binary search trees internally for bucket collisions.
If the user wanted to use hashes, they could. If they chose a TreeMap, there's a reason they wanted its behavior. This is not an oversight, and not a mistake.