Web / Apache Commons Collections Interview questions
How does a TreeBag maintain element ordering internally?
TreeBag<E> is backed internally by a TreeMap, mapping each distinct element to a mutable occurrence counter rather than storing the same element multiple times as separate map entries.
TreeBag<String> bag = new TreeBag<>(); bag.add("banana"); bag.add("apple"); bag.add("apple"); for (String fruit : bag) { System.out.println(fruit); } // apple // apple // banana
Because the backing structure is a TreeMap, keys are kept sorted according to their natural ordering (via Comparable) or a Comparator supplied at construction, and the Bag's iterator walks that sorted key sequence, yielding each element back-to-back as many times as its counter indicates.
This design means insertion, removal, and count updates run in O(log n) time (the TreeMap's put/get cost), rather than the average O(1) that a HashMap-backed HashBag achieves - the ordering guarantee is what costs the extra log n factor.
TreeBag stores duplicate elements by:
Because it's backed by a TreeMap, TreeBag's add/remove operations run in:
More Related questions...
