Core Java

Collections

Slide navigation: Forward with space bar, → arrow key, or PgDn. Backwards with ← or PgUp.

Understand the benefit of separate collection classes and interfaces

Collection Interfaces

• Collections framework separates interfaces and implementations.
• Queue interface provides abstract specification:

  public interface Queue<E> // a simplified form of the interface in the standard library
  {
     void add(E element);
     E remove();
     int size();
  }
  

  

Collection Classes

• A collection interface can have multiple implementing classes:

  public class CircularArrayQueue<E> implements Queue<E>
  public class LinkedListQueue<E> implements Queue<E>
     // not actual library classes

  
• Always use the interface after creation:

  Queue<Customer> expressLane = new CircularArrayQueue<>(100);
  

Become familiar with the types in the collections framework

Fundamental Interfaces

• Collection<E> has methods:

  boolean add(E element)
  Iterator<E> iterator()
  . . .
  

• Iterator<E> has methods:

  E next();
  boolean hasNext();
  void remove();
  default void forEachRemaining(Consumer<? super E> action);

Using Iterators

• Get an iterator from a collection to visit all elements:

  Collection<String> c = . . .;
  Iterator<String> iter = c.iterator();
  while (iter.hasNext())
  {
     String element = iter.next();
     do something with element
  }

• More concisely:

  for (String element : c) // works for any Iterable 
  {
     do something with element
  }
  

• The Collection<E> interface extends the Iterable<E> interface.
• Or without any loop:

  iterator.forEachRemaining(element -> do something with element);

More about Iterators

• Traversal order depends on collection.
• Think of iterator position as being between elements.
• The remove method removes the element that was just returned by next:

  Iterator<String> it = c.iterator();
  it.next(); // skip over the first element
  it.remove(); // now remove it
  

• Caution: Calling remove twice in a row without calling next in between is an error.
• Oddball remove behavior was chosen to make this loop possible:

  while (it.hasNext())
     if (it.next() fulfills some property)
        it.remove();
  

Useful Collection Methods

int size()
boolean isEmpty()
boolean contains(Object obj)
boolean containsAll(Collection<?> c)
boolean equals(Object other)
boolean addAll(Collection<? extends E> from)
boolean remove(Object obj)
boolean removeAll(Collection<?> c)
boolean removeIf(Predicate<? super E> filter)
void clear()
boolean retainAll(Collection<?> c)
Object[] toArray()
<T> T[] toArray(T[] arrayToFill)

Interfaces in the Collection Framework

• Collection holds elements, Map holds key/value pairs.
• List: Ordered collection.
• Set: Unordered collection without duplicates.
• SortedSet/SortedMap: Traversed in sorted order.
• NavigableSet/NavigableMap: Additional methods for sorted sets/maps.

Lists

• Linear traversal with iterators.
• Random access with integer indexes.
• List<E> methods:

  void add(int index, E element)
  void remove(int index)
  E get(int index)
  E set(int index, E element)

• Poor design: Array lists and linked lists have very different performance for these methods.
  • Can use RandomAccess tagging interface to distinguish between the two.
• ListIterator<E> extends Iterator<E> and provides methods:

  void add(E element)
  E previous()
  . . .
  

Concrete Collections

Collection Classes

Work with linked lists and array lists

Why Linked Lists?

• Two ordered collection implementations: array lists and linked lists.
• Array lists manage an array that can grow or shrink.
• What's not to like?
  • Inserting and removing in the middle is slow:
    

Linked Lists

• Linked list=chain of “links”:
  
• Easy to remove in the middle:
  

Concurrent Modifications

• Suppose one iterator traverses a collection.
• At the same time, another modifies the collection by removing or adding elements.
• In the case of a linked list, that won't work—the links will not be consistent.
• Linked list iterators detect concurrent modifications:

  List<String> list = . . .;
  ListIterator<String> iter1 = list.listIterator();
  ListIterator<String> iter2 = list.listIterator();
  iter1.next();
  iter1.remove();
  iter2.next(); // throws ConcurrentModificationException

• The list and all iterators keep a “modification count”.
  • Ok to have multiple readers and no writer.
  • Ok to have one writer and no reader.

linkedList

Other Lists

• ArrayList is the other concrete implementation of the List interface.
• You already know everything about array lists.
• No need to use iterators since you have efficient random access.
• They are lists, so you may want to save references in List variables:

  List<String> names = new ArrayList<>();
  

• Moment of truth: You won't use linked lists much. Most of the time, an array list is fine.
• Some methods give you a List value:

  List<String> names = Arrays.asList("Peter", "Paul", "Mary");
  

• It's a list, but you don't know which kind.

Java 9 News Flash - Collection Literals

• In 2009, Josh Bloch proposed collection literals for Java 7 as part of Project Coin:

  List<Integer> piDigits = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9];
  Set<Integer> primes = { 2, 7, 31, 127, 8191, 131071, 524287 };

• This is what we are getting for Java 9:

  List<Integer> piDigits = List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9);
  Set<Integer> primes = Set.of(2, 7, 31, 127, 8191, 131071, 524287);
  

• Library feature, not a language change.
• Constructs objects of some class that implement the List and Set interface.
• Similar to Arrays.asList, but objects are immutable.

Map Literals

• Original syntax proposal:

  Map<Integer, String> platonicSolids = { 4 : "tetrahedron", 6 : "cube",
     8 : "octahedron", 12 : "dodecahedron", 20 : "icosahedron" };

• This is what we are getting for Java 9:

  Map<Integer, String> platonicSolids = Map.of(4, "tetrahedron", 6, "cube",
     8, "octahedron", 12, "dodecahedron", 20, "icosahedron");
  

  or

  import static java.util.Map.*;
  platonicSolids = ofEntries(entry(4, "tetrahedron"), entry(6, "cube"), ...);
  

• The first version works only for maps with ≤ 10 elements.

Work with hash sets and sorted sets

Hash Sets

• If you don't care about element ordering, you can use more efficient collections.
• Sets can add, remove, and find elements quickly.
• Hash set uses hash codes to group elements into buckets:
  
• Elements are visited in seemingly random order.

set

Tree Sets

• Tree sets visit elements in sorted order.
• In practice, a bit slower than hash sets.
• But performance is guaranteed, whereas hash sets can perform poorly when the hash function does not scramble values well.
• Tree set needs total ordering—not always easy to find.
  • In a total ordering, two elements compare identically only when they are equal.
  • What would be a total ordering for Rectangle? For Employee?
• Use tree sets when your elements are comparable and you need traversal in sorted order.

treeSet

Work with queues, deques, and priority queues

Queues, Deques, and Priority Queues

• Queues let you efficiently add at the tail and remove from the head.
• Think “queue of people”.
• Useful for adding work assignments to the tail and removing them from the head.
• Common tool in concurrent programs to even out workload.
• Deque can add/remove on both ends.
• Priority queue isn't a queue.
  • The priority queue does not remember in which order elements were added.
  • When removing, the “highest priority” element is removed.
  • Useful for work scheduling.

priorityQueue

Use maps to organize key/value pairs

Maps

• A map stores key/value associations.
• HashMap hashes the keys, TreeMap organizes them in sorted order.
• Add an association to a map:

  Map<String, Employee> staff = new HashMap<>(); // HashMap implements Map
  Employee harry = new Employee(. . .);
  staff.put("987-98-9996", harry);

• Retrieve a value with a given key:

  String id = "987-98-9996";
  Employee e = staff.get(id); // gets harry

• The get method returns null if the key is absent. Better approach:

  Map<String, Integer> scores = . . .;
  int score = scores.getOrDefault(id, 0); // Gets 0 if the id is not present
  

• map.remove(key) removes a key.
• Easiest way to iterate over a map:

  scores.forEach((k, v) ->
     System.out.println("key=" + k + ", value=" + v));
  

map

Updating Map Entries

• Updating a map entry is tricky because the first time is special.
• Consider updating a word count:

  counts.put(word, counts.get(word) + 1);
  

• What if word wasn't present?

  counts.put(word, counts.getOrDefault(word, 0) + 1);

• Another approach:

  counts.putIfAbsent(word, 0);
  counts.put(word, counts.get(word) + 1); // Now we know that get will succeed
  

• Even better:

  counts.merge(word, 1, Integer::sum);

• If word wasn't present, put 1. Otherwise, put the sum of 1 and the previous value.

Map Views

• In the Java collections framework, a map isn't a collection.
• Can get collections of keys, values, and key/value pairs:

  Set<K> keySet()
  Collection<V> values()
  Set<Map.Entry<K, V>> entrySet()

• To visit all keys and values, can use:

  Set<String> keys = staff.keySet();
  for (String k : keys) do something with k and  staff.get(k)

• More efficiently:

  for (Map.Entry<String, Employee> entry : staff.entrySet())
  {
     String k = entry.getKey();
     Employee v = entry.getValue();
     do something with k, v
  }

• Efficient and elegant:

  staff.forEach((k, v) ->  do something with k, v);
  

• Calling remove on the key set removes the key and associated value from the map.

Linked Hash Maps

• A linked hash map traverses entries in the order in which they were added.
• In the Java ServerFaces framework, you can specify a map of displayed and submitted values in an HTML select tag:

  options.put("Monday", 1);
  options.put("Tuesday", 2);
  options.put("Wednesday", 3);
  options.put("Thursday", 4);
  . . .

• You don't want them to show up in random or sorted order.
• Use a LinkedHashMap.
  

Understand collection wrappers and views

Views

• A view implements a collection interface without actually storing the elements.
• Example:

  Collection<String> greetings = Collections.nCopies(100, "Hello");

• Useful to pass small collections to a method:

  Collection<String> greetings = Collections.singleton("Hello");
  Set<String> deepThoughts = Collections.emptySet();
  

• Subranges give a view into an existing collection:

  List<Employee> group2 = staff.subList(10, 20);
  

• The view is live:

  group2.clear(); // staff reduction
  

• For sorted sets and maps, can view intervals:

  SortedSet<E> subSet(E from, E to)
  SortedSet<E> headSet(E to)
  SortedSet<E> tailSet(E from)
  SortedMap<K, V> subMap(K from, K to)
  SortedMap<K, V> headMap(K to)
  SortedMap<K, V> tailMap(K from)
  

Restricted Views

• Useful methods for producing unmodifiable views:

  Collections.unmodifiableCollection
  Collections.unmodifiableList
  Collections.unmodifiableSet
  Collections.unmodifiableSortedSet
  Collections.unmodifiableNavigableSet
  Collections.unmodifiableMap

• Good idea whenever you want to give a “look, don't touch” copy of a collection.
• Synchronized views for safe concurrent access.
  • But you should instead use a threadsafe collection.
• Checked views for debugging class cast exceptions:

  List<String> safeStrings = Collections.checkedList(strings, String.class);

Use common algorithms with collections

Common Algorithms

• Collections.sort sorts a list of Comparable, or any list with a Comparator instance.
• Collections.binarySearch finds an element in a sorted list.
• Collections.min and Collections.max find the smallest and largest element.
• Collections.fill fills a list with a specified element.
• Collections.shuffle randomly shuffles a list.
• More useful examples:

  Collections.replaceAll(words, "C++", "Java");
  words.replaceAll(String::toLowerCase);
  words.removeIf(w -> w.length() <= 3);
  

• That's a lot nicer than an explicit loop:

  for (int i = 0; i < words.size(); i++)
     if (words.get(i).equals("C++")) words.set(i, "Java");
  

Bulk Operations

• Can copy or remove elements in bulk:

  coll1.addAll(coll2);
  coll1.removeAll(coll2);
  coll1.retainAll(coll2);

• When working with sets, addAll is set union, retainAll is set intersection, removeAll is set difference.
• Can combine with views:

  staffMap.keySet().removeAll(terminatedIDs);
  relocated.addAll(staff.subList(0, 10));
  

Converting between Collections and Arrays

• To turn an array into a collection, use the Arrays.asList method:

  String[] names = . . .;
  List<String> list = Arrays.asList(names);
  Set<String> set = new HashSet<>(Arrays.asList(names));
  

• To turn a collection into an array, you can call coll.toArray(), but you only get a useless Object[] array.
• To get an array of the right type, supply an array of length 0:

  Collection<String> coll = . . .;
  String[] names = coll.toArray(new String[0]);
  

• Or, more efficiently, allocate the array with the correct size:

  String[] names = coll.toArray(new String[coll.size()]);
  

shuffle

Be able to use collections from old versions of Java

Legacy Collections

• Some APIs still use ancient collections.
• Vector, Hashtable are predecessors of ArrayList, HashMap.
• Enumeration is a precessor of Iterator.
• Properties are used when specifying program configurations. They are similar to Map<String, String>.
• A Stack is the classic stack structure. Just use an ArrayList instead.
• A BitSet is a sequence of bits. It can be used to represent a set of integers. Operations include:

  int bit = bucketOfBits.get(i);
  bucketOfBits.set(i);
  bucketOfBits.clear(i);
  

sieve