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?