data structures - Java collections maintaining insertion order

Question

Why do some collection data structures not maintain the order of insertion? What is the special thing achieved compared to maintaining order of insertion? Do we gain something if we don't maintain the order?

Answer 1

Performance. If you want the original insertion order there are the LinkedXXX classes, which maintain an additional linked list in insertion order. Most of the time you don't care, so you use a HashXXX, or you want a natural order, so you use TreeXXX. In either of those cases why should you pay the extra cost of the linked list?