# Java collections and generics > A bag (multiset) built twice – on an ArrayList and on a HashMap – to show how to choose a collection, why equals and hashCode matter, and how to read generic signatures, sort with a Comparator and use views like subList. Source: https://laszlonemes.com/university/programming-technology/collections-generics · Author: László Nemes Session 3 · Programming Technology A bag (multiset) built twice – on an ArrayList and on a HashMap – to show how to choose a collection, why equals and hashCode matter, and how to read generic signatures, sort with a Comparator and use views like subList. 19 min read `List vs Set vs Map` `Generic types and methods` `equals and hashCode` `ArrayList vs HashMap lookup` `Comparator and stable sorting` `? super T and ? extends T` `ArrayList`, `HashMap` and `HashSet` are probably the three classes you will use most in your programming life. This session is about choosing between them and using them correctly: we build the same data structure – a **bag** (multiset) – twice, once on a list and once on a map, and compare what each costs. Along the way we learn to read the angle brackets that fill the JDK documentation: `List`, `` before a return type, `? super T`. > **The one idea to take away:** choose the collection by the question your program asks most often. "What is the 3rd one?" is a `List`. "Is this one in there?" is a `Set`. "What belongs to this key?" is a `Map`. Picking the wrong one still works – it just makes every other line harder. After this session you can - choose between List, Set and Map for a given task and declare variables with the interface type - read and write generic types and methods: List, Map, before the return type - explain why equals and hashCode decide whether a collection finds your object - implement bag operations on an ArrayList and on a HashMap and compare their cost - sort with a Comparator, and read ? super T and ? extends T in a signature - avoid the classic collection bugs: == on objects, removing while iterating, null from get ## Pick the collection by the question you ask The Java collections are a small family of interfaces with several implementations each (Fig. 1). The interface says *what* you can do – a `List` has positions, a `Set` has no duplicates, a `Map` pairs keys with values. The class says *how* it is stored, and therefore what is fast. > **Fig. 1** · The interfaces on top, the classes we use below. Map stands apart: it is not a Collection, it stores key–value pairs. > > *Diagram:* The collection interfaces and the classes this session uses. List and Set extend Collection; ArrayList implements List, HashSet implements Set, HashMap implements Map. Map is a separate hierarchy, not a Collection. Variables are declared with the interface and created with the class. | You mostly ask… | Use | Fast | Slow | | --- | --- | --- | --- | | "the i-th element", "in this order" | `ArrayList` | get(i), add at the end | contains, remove from the middle | | "is x in there?", "no duplicates" | `HashSet` | add, contains, remove | no order, no positions | | "what belongs to this key?" | `HashMap` | get, put, containsKey by key | searching by value | Declare variables, fields and parameters with the **interface** type, and name the class only after `new`. Then the rest of the code can only use what the interface promises, and swapping `ArrayList` for another `List` is a one-line change. Bag.java – the field is a List, the object an ArrayList ```java // The variable has the interface type; only "new" names the class. // Switching to another List later is a one-line change. private final List data; public Bag() { this.data = new ArrayList<>(); // diamond: is inferred } ``` In your assignment **Choose the collections of your model on purpose** The first assignment reads a list of objects from a file and simulates something with them (the sample in the next session is a race of creatures). Ask the questions above for each piece of data. The participants are processed in the order of the file – a `List`. Names must be unique – a `Set` answers "seen it already?" in one call. If the program looks things up by name, that is a `Map`. Race.java – a Set as a duplicate detector ```java Set names = new HashSet<>(); for (Creature creature : creatures) { if (!names.add(creature.getName())) { // add returns false for a duplicate throw new IllegalArgumentException("Duplicate creature name: " + creature.getName()); } } ``` If the question "why a list here?" comes up at the presentation, "because that's what I know" is the wrong answer; "because the order of the file matters and I never look up by name" is the right one. ## Generics: the type in angle brackets Every collection is **generic**: the type in `< >` – the **type parameter** – says what it holds. From then on the compiler checks every use, so a wrong element type is a compile error instead of a crash at runtime, and you never cast what you take out. A typed list ```java List names = new ArrayList<>(); names.add("Anna"); // fine names.add(42); // compile error: only Strings go in String first = names.get(0); // no cast: the compiler knows it's a String ``` | Notation | Meaning | | --- | --- | | `List` | a list of Strings | | `Map` | two type parameters, in order: the key type and the value type | | `Map.Entry` | one key–value pair of a map; Entry is declared inside Map, hence the dot | | `new ArrayList<>()` | the "diamond": the compiler fills in the type from the left-hand side | | `List` | type parameters can't be primitives – no List; the wrapper class is used and the compiler converts (autoboxing) | | `List` | a "raw type" without brackets, left over from before generics – avoid it, the compiler checks nothing | You can write generic methods yourself. The `numBoth` example counts the common elements of two collections of *any* element type. The `` before the return type is the **declaration** of the type variable – just as a variable must be declared before it is used. `Collection` in the parameter list only *uses* it (Fig. 2). > **Fig. 2** · declares, Collection uses. It sits before the return type because the return type itself may be T – as in T first(List list). > > *Diagram:* The signature of the generic method numBoth, piece by piece. The before the return type declares the type variable; Collection in both parameters uses it, so both collections hold the same element type. At the call site the compiler infers T from the arguments, here T = Integer. Without the , the compiler looks for a class named T and fails. A generic **class** declares its type variable after the class name, and every instance method can use it. `ReverseComparator` from the sorting example wraps any comparator and reverses it; `T` is decided when the object is created, `new ReverseComparator(…)` or with the diamond. ReverseComparator.java – a generic class ```java public class ReverseComparator implements Comparator { private final Comparator original; public ReverseComparator(Comparator original) { this.original = original; } @Override public int compare(T t1, T t2) { return original.compare(t2, t1); // swap, don't negate } } ``` Good to know **Single capital letters by convention** The name of a type variable is free, but the convention is one capital letter: `T` (type), `E` (element), `K` (key), `V` (value). That way nobody mistakes it for a class name. ## A bag on an ArrayList A **bag** is like a set, except that an element can be in it several times – so for each element we store how many copies there are. Operations: add some copies, remove some or all, ask how many, clear, and the set operations union, intersection and difference. The first version keeps a `List`, where a `BagItem` is a small class holding the element and its count. To find an element we walk the list (Fig. 3). > **Fig. 3** · Every add, remove and howMany starts with the same linear search. With three items that is nothing; with a hundred thousand it is the bottleneck. > > *Diagram:* The ArrayList bag in memory: the Bag holds a reference to an ArrayList whose slots point at BagItem objects, each with an item and a count. howMany("c") walks the list from index 0 and calls equals on every item until it finds "c", so the cost grows with the number of different items. Bag.java – linear search ```java private BagItem getItem(String item) { for (BagItem bi : data) { if (bi.getItem().equals(item)) { // equals, not == return bi; } } return null; // not in the bag } ``` Bag.java – add: a new entry or a bigger count ```java public void add(String item, int num) { Objects.requireNonNull(item, "item must not be null"); if (num <= 0) { throw new IllegalArgumentException("num must be positive: " + num); } BagItem bi = getItem(item); if (bi == null) { data.add(new BagItem(item, num)); // new entry } else { bi.addNum(num); // existing entry: only the count grows } } ``` Two decisions in `add` are worth copying. The method refuses bad arguments immediately with an exception, so the bag can never get into an invalid state – a negative count, a `null` element. And it keeps an **invariant**: an entry with count 0 never stays in the list; `remove` deletes the entry instead. Every other method can rely on that. Common mistake **Comparing objects with ==** `==` on objects asks "is this the *same object*?", not "do they have the same value?". Two Strings with the same letters can be two different objects – read from a file, built with `+` – and then `==` says false. Compare objects with `equals`; keep `==` for primitives and for the deliberate "same object" check. The collections' search methods – `contains`, `indexOf`, `remove(Object)` – all call `equals`. The version inherited from `Object` is plain `==`, so for your own classes you override it. And whoever overrides `equals` must override `hashCode` too: equal objects must have equal hash codes, otherwise `HashSet` and `HashMap` look in the wrong bucket and don't find them. BagItem.java – equals and hashCode together ```java @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof BagItem)) { // also false for null return false; } BagItem other = (BagItem) o; return Objects.equals(item, other.item) && num == other.num; } @Override public int hashCode() { // equal objects – equal hash codes return Objects.hash(item, num); } ``` Common mistake **A mutable object as a HashMap key** `BagItem`'s hash code depends on `num`, which changes. Put a `BagItem` into a `HashSet`, change its count, and the set can no longer find it – it looks in the bucket of the *new* hash code, while the object sits in the bucket of the old one. In an `ArrayList` this is harmless (a list doesn't use hash codes). Rule: use immutable things as keys and set elements – `String`, `Integer`, an `enum`, or a class whose fields are `final`. Common mistake **List.remove(1) removes by index** `List` has two `remove` methods: `remove(int index)` and `remove(Object o)`. With a `List`, `remove(1)` picks the index version. To remove the value, pass an object. ```java List numbers = new ArrayList<>(List.of(10, 20, 30)); numbers.remove(1); // remove(int index): removes 20 numbers.remove(Integer.valueOf(10)); // remove(Object): removes the value 10 ``` ## The same bag on a HashMap The bag really is a mapping from element to count, so a `Map` fits it exactly – no `BagItem` class needed. More importantly, the lookup is no longer a walk: the key's hash code points at one bucket, and only the few entries in it are compared (Fig. 4). > **Fig. 4** · A HashMap finds a key in (on average) constant time, independent of its size – the reason to prefer it whenever you look things up by key. > > *Diagram:* The HashMap bag: the map is an array of buckets. howMany("c") computes the key’s hashCode, which picks one bucket, and only the few entries in that bucket are compared with equals. The cost does not grow with the size of the bag. Bag.java – add and howMany on a map ```java private final Map data = new HashMap<>(); public void add(String item, int num) { // put overwrites the old value, so compute the new count first data.put(item, howMany(item) + num); // the same in one call: data.merge(item, num, Integer::sum); } public int howMany(String item) { return data.getOrDefault(item, 0); // get would return null for a missing key } ``` `put` *overwrites* the value of an existing key – the map can't know you meant "add to it". So we compute the new count first, or let `merge` do it in one call. To walk a map, iterate over `entrySet()`, which gives you key and value together; walking `keySet()` and calling `get` for every key does each lookup twice. Common mistake **get returns null – and null doesn't fit in an int** For a missing key, `get` returns `null`. Assigning that to an `int` unboxes it, and unboxing `null` throws `NullPointerException` – on a line that looks perfectly innocent. ```java int n = data.get("x"); // "x" is missing: get returns null, // unboxing null throws NullPointerException int m = data.getOrDefault("x", 0); // safe: 0 for a missing key ``` | | ArrayList bag | HashMap bag | | --- | --- | --- | | find an element | linear: up to n equals() calls | constant on average: one hash, one bucket | | extra class | BagItem (element + count) | none – the map entry is the pair | | order | insertion order | no guaranteed order | | equals/hashCode needed for | BagItem (for list search) | the key type – String has them | ## Union, intersection, difference On bags the set operations work element by element on the counts (Fig. 5): the union adds them, the intersection takes the smaller one, the difference subtracts – and whatever drops to zero or below is left out. > **Fig. 5** · The three operations on the example bags of the session. Each one builds a new Bag and leaves both inputs unchanged. > > *Diagram:* Bag operations work item by item on the counts. With bag = {a=21, b=33, c=32} and bag2 = {a=42, c=12}: the union adds the counts (a=63, b=33, c=44), the intersection takes the minimum (a=21, c=12) and the difference subtracts (b=33, c=20). A count of zero or less is left out of the result. Bag.java – union on the HashMap version ```java public Bag union(Bag other) { Bag result = new Bag(); for (Map.Entry entry : other.data.entrySet()) { result.add(entry.getKey(), entry.getValue()); } for (Map.Entry entry : data.entrySet()) { result.add(entry.getKey(), entry.getValue()); } return result; } ``` Notice that `union` reads `other.data` although `data` is private. Visibility in Java is per *class*, not per object: a `Bag` may see the private fields of another `Bag`. And the result is built through `add`, so it gets the validation and the zero-count invariant for free. Intersection and difference are your first tasks below. ## Bulk operations instead of loops Collections have operations that work on a whole collection at once: `addAll` (union), `retainAll` (intersection), `removeAll` (difference), `containsAll`. The `numBoth` example uses them to count the common elements of two collections without writing a single loop – the loops still run, inside the library (Fig. 6). > **Fig. 6** · Sets do two jobs here: they drop the duplicates, and they make retainAll fast, because retainAll calls contains on its argument for every element. > > *Diagram:* numBoth without a loop: each list is copied into a HashSet, which drops the duplicates, then retainAll keeps only the elements that are in both sets. [1, 2, 2, 3, 3, 4] and [2, 3, 3, 7, 8] become {1, 2, 3, 4} and {2, 3, 7, 8}; the intersection is {2, 3}, so the answer is 2. NumBoth.java – intersection without a loop ```java public static int numBoth(Collection c1, Collection c2) { Set common = new HashSet<>(c1); // copy: duplicates drop out Set s2 = new HashSet<>(c2); // fast contains() for retainAll common.retainAll(s2); // intersection, in place on the copy return common.size(); } ``` Common mistake **Removing from a list inside its for-each loop** The for-each loop uses an iterator, and the iterator notices when the list is changed behind its back: the next step throws `ConcurrentModificationException`. Use `removeIf`, or an explicit `Iterator` and its own `remove()`, or collect what to remove and call `removeAll` after the loop. ```java for (String name : names) { if (name.isEmpty()) { names.remove(name); // ConcurrentModificationException on the next step } } names.removeIf(name -> name.isEmpty()); // the safe way ``` Common mistake **Arrays.asList and List.of can't grow** `Arrays.asList` returns a fixed-size list and `List.of` an unmodifiable one – fine for reading, but `add` and `remove` throw `UnsupportedOperationException`. When you need to modify, copy them into a new `ArrayList`. ```java List fixed = Arrays.asList(5, 2, 8); fixed.add(1); // UnsupportedOperationException List growable = new ArrayList<>(Arrays.asList(5, 2, 8)); growable.add(1); // fine ``` ## Sorting with a Comparator Some classes have a **natural order**: they implement `Comparable` and compare themselves – numbers by size, Strings alphabetically. For every other order you hand the sort a `Comparator`: an object with one method, `compare(a, b)`, that returns a negative number if `a` comes first, zero if they are equal, positive if `b` comes first. The sort algorithm itself knows nothing about your order – it only keeps asking (Fig. 7). Natural order vs a Comparator ```java // Natural order: the class compares itself (String, Integer implement Comparable) Collections.sort(words); // Any other order: pass a Comparator words.sort(String.CASE_INSENSITIVE_ORDER); creatures.sort(Comparator.comparingInt(Creature::getDistance).reversed()); ``` The `Sort1` example sorts integers by their remainder modulo `n`, ascending or descending: RemainderComparator.java – the compare method ```java public class RemainderComparator implements Comparator { private final int n; private final boolean ascending; @Override public int compare(Integer i1, Integer i2) { int r1 = Math.floorMod(i1, n); // 0..n-1 even for negative numbers int r2 = Math.floorMod(i2, n); return ascending ? Integer.compare(r1, r2) : Integer.compare(r2, r1); } } ``` > **Fig. 7** · list.sort moves the elements; the comparator only answers which of two comes first. Change the comparator and the same algorithm produces a different order. > > *Diagram:* The sort algorithm knows nothing about order: it only asks the comparator which of two elements comes first. RemainderComparator(3, true) answers by comparing the remainders modulo 3, so the list ends up grouped by remainder 0, 1, 2. Elements with equal remainders keep their original order because the sort is stable. Three details in this small class are worth knowing. `Math.floorMod` instead of `%`, because `%` keeps the sign (`-1 % 3 == -1`), while the mathematical remainder is always between 0 and `n-1`. `Integer.compare(r1, r2)` instead of the tempting `r1 - r2`, which overflows for large numbers of opposite sign. And descending order by swapping the two arguments – negating the result fails for `Integer.MIN_VALUE`, whose negation is itself. Sort1.java – sort a copy; an overload instead of a default argument ```java public static List getSortedByNRemainder(List list, int n) { return getSortedByNRemainder(list, n, true); // the "default argument" } public static List getSortedByNRemainder(List list, int n, boolean ascending) { List listCopy = new ArrayList<>(list); // the caller's list stays as it was listCopy.sort(new RemainderComparator(n, ascending)); return listCopy; } ``` The function sorts a *copy*, so the caller's list is not touched – the signature returns a list, and a reader expects a function that returns something to leave its input alone. Java has no default parameter values; the usual substitute is an **overload** with fewer parameters that calls the full version, so the logic stays in one place. In your assignment **Rankings and standings** If your assignment prints a ranking – final standings, a leaderboard later in the semester – don't write a sorting loop. Sort a copy of the list with a `Comparator`, built with `Comparator.comparingInt(…)` and `.reversed()` or `.thenComparing(…)` for ties. Decide what happens with ties on purpose: the sort is stable, so equal elements keep the order of the input file. ## Reading ? super T and ? extends T The `Sort2` example has this signature, and the JDK documentation is full of similar ones: ```java public static void sort(List list, int i, int j, Comparator comparator) ``` `?` is a **wildcard** – "some type I don't name" – and `super T` restricts it to `T` or a supertype of `T`. Together: a comparator that can compare `T`s, or something more general. If we sort a `List` (so `T = Integer`, whose supertypes are `Number` and `Object`): | Comparator passed in | Accepted? | Why | | --- | --- | --- | | `Comparator` | yes | exactly T | | `Comparator` | yes | whoever can compare any two numbers can compare two Integers | | `Comparator