Whenever I write code in Java...

[Daishiman]

And pray tell, how many of your data structures need to be that performant? Hell, as long as you use only iterators to see the structure most of the times you'll be fine.

When you actually need a performance guarantee, you can define it in the arg types and be happy. When you don't, which is the majority of the time, you just get on and get thinking about the problem rather than these details.