Why are bags considered unordered?

Question

Bags are stored in arrays. I do understand that we can change the size of bags as we want etc.. However, since it is stored in array, it basically has an index number isn't it? In this case, why do we still say that it is unordered?

Answer 1

Bags are stored in arrays

No they are not.

Actually, they might be, depending on implementation, but they surely don't have to be. It's like saying a List is stored in an array. That is e.g. true for an ArrayList, but not true for a LinkedList.

So what's the difference between a bag, a list, and a set?

• A list is ordered, allowing duplicates

  • Generally has slow lookup by value.
  • ArrayList implementation uses array, with fast lookup by position.
  • LinkedList implementation uses doubly-linked nodes, with fast insert/remove at beginning of list.

• A set is unordered, no duplicates

  • Generally allows fast lookup by value.
  • HashSet implementation is unordered.
  • LinkedHashSet implementation is ordered.
  • TreeSet implementation is sorted.

• A bag is unordered, allowing duplicates

  • No built-in Java support. Generally just use List if needed.
    Recommend using third-party library if fast lookup by value is needed.

It's the definition of the terms that specifies the ordered vs unordered semantics. An implementation of a bag might happen to keep ordering, but it's not required by the generic term bag.

---

Let's clear up the confusion about bags in Java.

• The Java Runtime Library doesn't have any Bag type.

• The Apache Commons Collections™ library has a Bag interface that implements java.util.Collection, although it violates the Collection contract. It has a HashBag and a TreeBag implementation, but no implementation using an array.

• The Google Guava library has a bag interface named Multiset that also implements java.util.Collection. It has HashMultiset, LinkedHashMultiset, and TreeMultiset implementations, but no implementation using an array.

• Hibernate ORM has a Bag class.

None of them specifies that a bag is a list, and none of them uses array to implement the bag.