Core Interfaces – Collections: Part II
Core Interfaces
The generic Collection<E> interface is a generalized interface for maintaining collections, and is the root of the interface inheritance hierarchy for collections shown in Figure 15.1a. These generic subinterfaces are summarized in Table 15.1. The Collection<E> interface extends the Iterable<E> interface that specifies an iterator to sequentially access the elements of an Iterable object (p. 791).
The elements in a Set<E> must be unique—that is, no two elements in the set can be equal. The order of elements in a List<E> is positional, and individual elements can be accessed randomly according to their position in the list.
Queues and deques, represented respectively by the Queue<E> and the Deque<E> interfaces, define collections whose elements can be processed according to various policies.
As can be seen in Figure 15.1b, the Map<K, V> interface does not extend the Collection<E> interface because conceptually, a map is not a collection. A map does not contain elements. It contains mappings (also called entries) from a set of key objects to a set of value objects. A key can, at most, be associated with one value— that is, it must be unique. As the name implies, the SortedMap<K, V> interface extends the Map<K, V> interface to maintain its mappings sorted in key order. It is superseded by the NavigableMap<K, V> interface which should be the preferred choice in new code.
Implementations
The java.util package provides implementations of a selection of well-known abstract data types, based on the core interfaces. Figures 15.2 and 15.3 show the inheritance relationship between the core interfaces and the corresponding implementations. None of the concrete implementations inherit directly from the Collection<E> interface. The abstract classes that provide the basis on which concrete classes are implemented are not shown in Figures 15.2 and 15.3.
Figure 15.2 The Core Collection Interfaces and Their Implementations
Figure 15.3 The Core Map Interfaces and Their Implementations
By convention, each of the collection implementation classes provides a constructor for creating a collection based on the elements of another Collection object passed as an argument. This allows the implementation of a collection to be changed by merely passing the collection to the constructor of the desired implementation. This interchangeability is also true between Map implementations. But collections and maps are not interchangeable. Note that a collection (or a map) only stores reference values of objects, and not the actual objects.
The collections framework is interface-based, meaning that collections are manipulated according to their interface types, rather than by the implementation types. By using these interfaces wherever collections of objects are used, various implementations can be used interchangeably.
All the concrete classes shown in Figures 15.2 and 15.3 implement the Serializable and the Cloneable interfaces; therefore, the objects of these classes can be serialized and also cloned.
A summary of collection and map implementations is given in Table 15.2. The contents of this table will be the focus as each core interface and its corresponding implementations are discussed in the subsequent sections.
Table 15.2 Summary of Collection and Map Implementations
| Concrete collections and maps | Interface | Duplicates | Ordered/Sorted | Methods the implementations expect the elements to provide | Data structures on which implementation is based |
| ArrayList<E> | List<E> | Allowed | Insertion order | equals() | Resizable array |
| LinkedList<E> | List<E>, Deque<E> | Allowed | Insertion/priority/deque order | equals() | Linked list |
| Vector<E> | List<E> | Allowed | Insertion order | equals() | Resizable array |
| HashSet<E> | Set<E> | Unique elements | No order | equals(), hashCode() | Hash table |
| LinkedHash- Set<E> | Set<E> | Unique elements | Insertion order | equals(), hashCode() | Hash table and doubly linked list |
| TreeSet<E> | Navigable- Set<E> | Unique elements (not null) | Sort order | equals(), hashCode(), compareTo() | Balanced tree |
| Priority- Queue<E> | Queue<E> | Allowed (not null) | Access according to priority order | equals(), compareTo() | Priority heap (tree-like structure) |
| ArrayDeque<E> | Deque<E> | Allowed (not null) | Deque order | equals() | Resizable array |
| HashMap<K,V> | Map<K,V> | Unique keys | No order | equals(), hashCode() | Hash table |
| LinkedHash- Map<K,V> | Map<K,V> | Unique keys | Key insertion order/Access order of entries | equals(), hashCode() | Hash table and doubly linked list |
| Hash- table<K,V> | Map<K,V> | Unique keys (no null key and no null values) | No order | equals(), hashCode() | Hash table |
| TreeMap<K,V> | Navigable-Map<K,V> | Unique keys (no null key) | Sorted in key order | equals(), hashCode(), compareTo() | Balanced tree |
In Table 15.2, we see that only lists and queues allow duplicates—that is, the same value can be stored multiple times in the collection. The TreeSet<E> class and the queue classes PriorityQueue<E> and ArrayDeque<E> do not allow the null value to be stored in the collection. All maps require that the keys are unique—that is, no two keys can be equal, and only the classes Hashtable<K, V> and TreeMap<K, V> disallow the null value as a key. A Hashtable<K, V>, in addition, does not allow the null value to be associated with a key.
From Table 15.2, we also see that elements in a LinkedHashSet<E> are ordered, in a TreeSet<E> they are sorted, and in a HashSet<E> they have no order (i.e., they are unordered). Sorting implies ordering the elements in a collection according to some ranking criteria, usually based on the values of the elements. However, elements in an ArrayList<E> are maintained in the order they are inserted in the list, known as the insertion order. The elements in such a list are thus ordered, but they are not sorted, as it is not the values of the elements that determine their ranking in the list but their position in the list. Thus ordering does not necessarily imply sorting. In a HashSet<E>, the elements are unordered. No ranking of elements is implied in such a set. Whether a collection is sorted, ordered, or unordered also has implications when iterating over the collection (p. 791).
In order for sorting and searching to work properly, the collections and maps in Table 15.2 also require that their elements implement the appropriate methods for object comparison. Comparing objects is covered in Chapter 14, p. 741. Sorting and searching in collections is covered in §15.11, p. 856.
Methods defined for collections that specify functional interfaces as a parameter and require lambda expressions as arguments are covered in Chapter 13, p. 673.
Using streams with collections is covered in Chapter 16, p. 879.
The collection and map implementations discussed in this chapter, except for Vector<E> and Hashtable<K, V>, are not thread-safe—that is, their integrity can be jeopardized by concurrent access. Concurrent collections and maps are covered in Chapter 22, p. 1365.
The Java Collections Framework provides a plethora of collections and maps for use in single-threaded and concurrent applications, which should eliminate the need to implement one from scratch.