The Collections Framework Core Java

A framework is a set of classes that form the basis for building advanced functionality. A framework contains superclasses with useful functionality, policies, and mechanisms. The user of a framework forms subclasses to extend the functionality without having to reinvent the basic mechanisms. For example, Swing is a framework for user interfaces.

The Java collections library forms a framework for collection classes. It defines a number of interfaces and abstract classes for implementors of collections , and it prescribes certain mechanisms, such as the iteration protocol. You can use the collection classes without having to know much about the framework we did just that in the preceding sections. However, if you want to implement generic algorithms that work for multiple collection types or if you want to add a new collection type, it is helpful to understand the framework.

There are two fundamental interfaces for collections: Collection and Map. You insert elements into a collection with a method:
boolean add(E element)

The interfaces of the collections framework

The interfaces of the collections framework

However, maps hold key/value pairs, and you use the put method to insert them.

To read elements from a collection, you visit them with an iterator. However, you can read values from a map with the get method:

A List is an ordered collection. Elements are added into a particular position in the container. An object can be placed into its position in two ways: by an integer index and by a list iterator. The List interface defines methods for random access:

As already discussed, the List interface provides these random access methods whether or not they are efficient for a particular implementation. To avoid carrying out costly random access operations, Java SE 1.4 introduced a tagging interface, RandomAccess. That interface has no methods, but you can use it to test whether a particular collection supports efficient random access:

The ArrayList and Vector classes implement the RandomAccess interface.

NOTE: From a theoretical point of view, it would have made sense to have a separate Array interface that extends the List interface and declares the random access methods. If there were a separate Array interface, then those algorithms that require random access would use Array parameters and you could not accidentally apply them to collections with slow random access. However, the designers of the collections framework chose not to define a separate interface, because they wanted to keep the number of interfaces in the library small. Also, they did not want to take a paternalistic attitude toward programmers. You are free to pass a linked list to algorithms that use random access you just need to be aware of the performance costs. The ListIterator interface defines a method for adding an element before the iterator position:

To get and remove elements at a particular position, you simply use the next and remove methods of the Iterator interface. The Set interface is identical to the Collection interface, but the behavior of the methods is more tightly defined. The add method of a set should reject duplicates. The equals method of a set should be defined so that two sets are identical if they have the same elements, but not necessarily in the same order. The hashCode method should be defined such that two sets with the same elements yield the same hash code.

Why make a separate interface if the method signatures are the same? Conceptually, not all collections are sets. Making a Set interface enables programmers to write methods that accept only sets. The SortedSet and SortedMap interfaces expose the comparator object used for sorting, and they define methods to obtain views of subsets of the collections. Finally, Java SE 6 introduced interfaces NavigableSet and NavigableMap that contain additional methods for searching and traversal in sorted sets and maps. (Ideally, these methods should have simply been included in the SortedSet and SortedMap interface.) The TreeSet and TreeMap classes implement these interfaces.

Now, let us turn from the interfaces to the classes that implement them. We already discussed that the collection interfaces have quite a few methods that can be trivially implemented from more fundamental methods. Abstract classes supply many of these routine implementations:

If you implement your own collection class, then you probably want to extend one of these classes so that you can pick up the implementations of the routine operations. The Java library supplies concrete classes:

Classes in the collections framework

Classes in the collections framework

Finally, a number of “legacy” container classes have been present since the first release of Java, before there was a collections framework:

They have been integrated into the collections framework.

Legacy classes in the collections framework

Legacy classes in the collections framework

Views and Wrappers

If you look at Figures above, you might think it is overkill to have lots of interfaces and abstract classes to implement a modest number of concrete collection classes. However, these figures don’t tell the whole story. By using views, you can obtain other objects that implement the Collection or Map interfaces. You saw one example of this with the keySet method of the map classes. At first glance, it appears as if the method creates a new set, fills it with all keys of the map, and returns it. However, that is not the case. Instead, the keySet method returns an object of a class that implements the Set interface and whose methods manipulate the original map. Such a collection is called a view. The technique of views has a number of useful applications in the collections framework.

Lightweight Collection Wrappers

The static asList method of the Arrays class returns a List wrapper around a plain Java array. This method lets you pass the array to a method that expects a list or collection argument. For example:

The returned object is not an ArrayList. It is a view object with get and set methods that access the underlying array. All methods that would change the size of the array (such as add and the remove method of the associated iterator) throw an UnsupportedOperationException. As of Java SE 5.0, the asList method is declared to have a variable number of arguments. Instead of passing an array, you can also pass individual elements. For example:

returns an immutable object that implements the List interface and gives the illusion of having n elements, each of which appears as anObject.For example, the following call creates a List containing 100 strings, all set to "DEFAULT":

There is very little storage cost the object is stored only once. This is a cute application of the view technique.

NOTE: The Collections class contains a number of utility methods with parameters or return values that are collections. Do not confuse it with the Collection interface.

The method call

returns a view object that implements the Set interface (unlike ncopies, which produces a List). The returned object implements an immutable single-element set without the overhead of data structure. The methods singletonList and singletonMap behave similarly.

Subranges

You can form subrange views for a number of collections. For example, suppose you have a list staff and want to extract elements 10 to 19. You use the subList method to obtain a view into the subrange of the list.

The first index is inclusive, the second exclusive just like the parameters for the substring operation of the String class. You can apply any operations to the subrange, and they automatically reflect the entire list. For example, you can erase the entire subrange:

The elements are now automatically cleared from the staff list, and group2 is empty. For sorted sets and maps, you use the sort order, not the element position, to form subranges. The SortedSet interface declares three methods:

These return the subsets of all elements that are larger than or equal to from and strictly smaller than to. For sorted maps, the similar methods

return views into the maps consisting of all entries in which the keys fall into the specifiedranges. The NavigableSet interface that was introduced in Java SE 6 gives more control over these subrange operations. You can specify whether the bounds are included:

Unmodifiable Views

The Collections class has methods that produce unmodifiable views of collections. These views add a runtime check to an existing collection. If an attempt to modify the collection is detected, then an exception is thrown and the collection remains untouched.You obtain unmodifiable views by six methods:

Each method is defined to work on an interface. For example, Collections.unmodifiableList works with an ArrayList, a LinkedList, or any other class that implements the List interface. For example, suppose you want to let some part of your code look at, but not touch, the contents of a collection. Here is what you could do:

The Collections.unmodifiableList method returns an object of a class implementing the List interface. Its accessor methods retrieve values from the staff collection. Of course, the lookAt method can call all methods of the List interface, not just the accessors. But all mutator methods (such as add) have been redefined to throw an UnsupportedOperationException instead of forwarding the call to the underlying collection.

The unmodifiable view does not make the collection itself immutable. You can still modify the collection through its original reference (staff, in our case). And you can still call mutator methods on the elements of the collection. Because the views wrap the interface and not the actual collection object, you only have access to those methods that are defined in the interface. For example, the LinkedList class has convenience methods, addFirst and addLast, that are not part of the List interface. These methods are not accessible through the unmodifiable view.

CAUTION: The unmodifiableCollection method (as well as the synchronizedCollection and checkedCollection methods discussed later in this section) returns a collection whose equals method does not invoke the equals method of the underlying collection. Instead, it inherits the equals method of the Object class, which just tests whether the objects are identical. If you turn a set or list into just a collection, you can no longer test for equal contents. The view acts in this way because equality testing is not well defined at this level of the hierarchy. The views treat the hashCode method in the same way. However, the unmodifiable Set and unmodifiableList class use the equals and hashCode methods of the underlying collections.

Synchronized Views

If you access a collection from multiple threads, you need to ensure that the collection is not accidentally damaged. For example, it would be disastrous if one thread tried to add to a hash table while another thread was rehashing the elements. Instead of implementing thread-safe collection classes, the library designers used the view mechanism to make regular collections thread safe. For example, the static synchronizedMap method in the Collections class can turn any map into a Map with synchronized access methods:

You can now access the map object from multiple threads. The methods such as get and put are serialized each method call must be finished completely before another thread can call another method.

Checked Views

Java SE 5.0 added a set of “checked” views that are intended as debugging support for a problem that can occur with generic types. it is actually possible to smuggle elements of the wrong type into a generic collection. For example:

The erroneous add command is not detected at runtime. Instead, a class cast exception will happen later when another part of the code calls get and casts the result to a String. A checked view can detect this problem. Define a safe list as follows:

The view’s add method checks that the inserted object belongs to the given class and immediately throws a ClassCastException if it does not. The advantage is that the error is reported at the correct location:

CAUTION: The checked views are limited by the runtime checks that the virtual machine can carry out. For example, if you have an ArrayList<Pair<String>> , you cannot protect it from inserting a Pair<Date> since the virtual machine has a single “raw” Pair class.

A Note on Optional Operations

A view usually has some restriction it may be read-only, it may not be able to change the size, or it may support removal, but not insertion, as is the case for the key view of a map. A restricted view throws an UnsupportedOperationException if you attempt an inappropriate operation.

In the API documentation for the collection and iterator interfaces, many methods are described as “optional operations.” This seems to be in conflict with the notion of an interface. After all, isn’t the purpose of an interface to lay out the methods that a class must implement? Indeed, this arrangement is unsatisfactory from a theoretical perspective.

A better solution might have been to design separate interfaces for read-only views and views that can’t change the size of a collection. However, that would have tripled the number of interfaces, which the designers of the library found unacceptable. Should you extend the technique of “optional” methods to your own designs? We think not. Even though collections are used frequently, the coding style for implementing them is not typical for other problem domains. The designers of a collection class library have to resolve a particularly brutal set of conflicting requirements. Users want the library to be easy to learn, convenient to use, completely generic, idiot proof, and at the same time as efficient as hand-coded algorithms. It is plainly impossible to achieve all these goals simultaneously, or even to come close. But in your own programming problems, you will rarely encounter such an extreme set of constraints. You should be able to find solutions that do not rely on the extreme measure of “optional” interface operations.

java.util.Collections 1.2

  • static <E> Collection unmodifiableCollection(Collection<E> c)
  • static <E> List unmodifiableList(List<E> c)
  • static <E> Set unmodifiableSet(Set<E> c)
  • static <E> SortedSet unmodifiableSortedSet(SortedSet<E> c)
  • static <K, V> Map unmodifiableMap(Map<K, V> c)
  • static <K, V> SortedMap unmodifiableSortedMap(SortedMap<K, V> c)
    constructs views of the collection whose mutator methods throw an UnsupportedOperationException.
  • static <E> Collection<E> synchronizedCollection(Collection<E> c)
  • static <E> List synchronizedList(List<E> c)
  • static <E> Set synchronizedSet(Set<E> c)
  • static <E> SortedSet synchronizedSortedSet(SortedSet<E> c)
  • static <K, V> Map<K, V> synchronizedMap(Map<K, V> c)
  • static <K, V> SortedMap<K, V> synchronizedSortedMap(SortedMap<K, V> c)
    constructs views of the collection whose methods are synchronized.
  • static <E> Collection checkedCollection(Collection<E> c, Class<E> elementType)
  • static <E> List checkedList(List<E> c, Class<E> elementType)
  • static <E> Set checkedSet(Set<E> c, Class<E> elementType)
  • static <E> SortedSet checkedSortedSet(SortedSet<E> c, Class<E> elementType)
  • static <K, V> Map checkedMap(Map<K, V> c, Class<K> keyType, Class<V> valueType)
  • static <K, V> SortedMap checkedSortedMap(SortedMap<K, V> c, Class<K> keyType, Class<V> valueType)
    constructs views of the collection whose methods throw a ClassCastException if an element of the wrong type is inserted.
  • static <E> List<E> nCopies(int n, E value)
  • static <E> Set<E> singleton(E value)
    constructs a view of the object as either an unmodifiable list with n identical elements, or a set with a single element.

java.util.Arrays 1.2

  • static <E> List<E> asList(E... array)
    returns a list view of the elements in an array that is modifiable but not resizable.

java.util.List<E> 1.2

  • List<E> subList(int firstIncluded, int firstExcluded)
    returns a list view of the elements within a range of positions.

java.util.SortedSet<E> 1.2

  • SortedSet<E> subSet(E firstIncluded, E firstExcluded)
  • SortedSet<E> headSet(E firstExcluded)
  • SortedSet<E> tailSet(E firstIncluded)
    returns a view of the elements within a range.

java.util.NavigableSet<E> 6

  • NavigableSet<E> subSet(E from, boolean fromIncluded, E to, boolean toIncluded)
  • NavigableSet<E> headSet(E to, boolean toIncluded)
  • NavigableSet<E> tailSet(E from, boolean fromIncluded)
    returns a view of the elements within a range. The boolean flags determine whether the bound is included in the view.

java.util.SortedMap<K, V> 1.2

  • SortedMap<K, V> subMap(K firstIncluded, K firstExcluded)
  • SortedMap<K, V> headMap(K firstExcluded)
  • SortedMap<K, V> tailMap(K firstIncluded)
    returns a map view of the entries whose keys are within a range.

java.util.NavigableMap<K, V> 6

  • NavigableMap<K, V> subMap(K from, boolean fromIncluded, K to, boolean toIncluded)
  • NavigableMap<K, V> headMap(K from, boolean fromIncluded)
  • NavigableMap<K, V> tailMap(K to, boolean toIncluded)
    returns a map view of the entries whose keys are within a range. The boolean flags determine whether the bound is included in the view

Bulk Operations

So far, most of our examples used an iterator to traverse a collection, one element at a time. However, you can often avoid iteration by using one of the bulk operations in the library. Suppose you want to find the intersection of two sets, the elements that two sets have in common. First, make a new set to hold the result.

Here, you use the fact that every collection has a constructor whose parameter is another collection that holds the initialization values. Now, use the retainAll method:

It retains all elements that also happen to be in b. You have formed the intersection without programming a loop. You can carry this idea further and apply a bulk operation to a view. For example, suppose you have a map that maps employee IDs to employee objects and you have a set of the IDs of all employees that are to be terminated.

Simply form the key set and remove all IDs of terminated employees.

Because the key set is a view into the map, the keys and associated employee names are automatically removed from the map. By using a subrange view, you can restrict bulk operations to sublists and subsets. For example, suppose you want to add the first 10 elements of a list to another container.

Form a sublist to pick out the first 10:

The subrange can also be a target of a mutating operation.

Converting between Collections and Arrays

Because large portions of the Java platform API were designed before the collections framework was created, you occasionally need to translate between traditional arrays and the more modern collections. If you have an array, you need to turn it into a collection. The Arrays.asList wrapper serves this purpose. For example:

Obtaining an array from a collection is a bit trickier. Of course, you can use the toArray method:

But the result is an array of objects. Even if you know that your collection contained objects of a specific type, you cannot use a cast:

The array returned by the toArray method was created as an Object[] array, and you cannot change its type. Instead, you use a variant of the toArray method. Give it an array of length 0 of the type that you’d like. The returned array is then created as the same array type:

If you like, you can construct the array to have the correct size:

In this case, no new array is created.

NOTE: You may wonder why you don’t simply pass a Class object (such as String.class) to the toArray method. However, this method does “double duty,” both to fill an existing array (provided it is long enough) and to create a new array.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Core Java Topics