Chapter 13. Collections

1.  If you need a circular array queue, use the ArrayDeque class. For a linked list queue, simply use the LinkedList class—it implements the Queue interface.

 

2.  It makes sense to use the concrete class only when you construct the collection object. Use the interface type to hold the collection reference. With this approach, if you change your mind, you can easily use a different implementation. You only need to change your program in one place—in the constructor call.

 

3.  The fundamental interface for collection classes in the Java library is the Collection interface. The interface has two fundamental methods:

public interface Collection<E>
{
   boolean add(E element);
   Iterator<E> iterator();
   . . .
}

 The add method adds an element to the collection. The add method returns true if adding the element actually changes the collection, and false if the collection is unchanged. The iterator method returns an object that implements the Iterator interface. You can use the iterator object to visit the elements in the collection one by one.

 

 

4.  The Iterator interface has three methods:

public interface Iterator<E>
{
   E next();
   boolean hasNext();
   void remove();
}

 By repeatedly calling the next method, you can visit the elements from the collection one by one. However, if you reach the end of the collection, the next method throws a NoSuchElementException. hasNext method returns true if the iterator object still has more elements to visit.

 

 

5.  The “for each” loop works with any object that implements the Iterable interface, an interface with a single method:

public interface Iterable<E>
{
   Iterator<E> iterator();
}

 The compiler simply translates the “for each” loop into a loop with an iterator.

 

 

6.  The remove method of the Iterator interface removes the element that was returned by the last call to next. It is illegal to call remove if it wasn’t preceded by a call to next. If you try, an IllegalStateException is thrown.(If you want to remove two adjacent elements, you cannot simply call remove method twice.)

 

7.  To make life easier for implementors, the library supplies a class AbstractCollection that leaves the fundamental methods size and iterator abstract but implements the routine methods in terms of them.

 

8.  Collection.toArray returns an array of the objects in the collection:

 

<T> T[] toArray(T[] arrayToFill)

 If arrayToFill has sufficient length, it is filled with the elements of this collection. If there is space, a null element is appended. Otherwise, a new array with the same component type as arrayToFill and the same length as the size of this collection is allocated and filled.

 

9.  The following table shows the collections in the Java library and briefly describes the purpose of each collection class:

 

 
10.  Arrays and array lists suffer from a major drawback. Removing an element from the middle of an array is expensive since all array elements beyond the removed one must be moved toward the beginning of the array. The same is true for inserting elements in the middle.

 

11.  In the Java programming language, all linked lists are actually doubly linked; that is, each link also stores a reference to its predecessor.

 

12.  The position-dependent add method is the responsibility of an iterator, since iterators describe positions in collections. Using iterators to add elements makes sense only for collections that have a natural ordering. Therefore, there is no add method in the Iterator interface. Instead, the collections library supplies a subinterface ListIterator that contains an add method. The add method adds the new element before the iterator position. If you call the add method multiple times, the elements are simply added in the order in which you supplied them. If the linked list has n elements, there are n + 1 spots for adding a new element:
|ABC
A|BC
AB|C
ABC|
In addition, the ListIterator interface has two methods that you can use for traversing a list backwards:

E previous()
boolean hasPrevious()

 

13.  Unlike the add method, which depends only on the iterator position, the remove method depends on the iterator state. Immediately after a call to next, the remove method indeed removes the element to the left of the iterator. However, if you have just called previous, the element to the right will be removed.

 

14.  A set method replaces the last element, returned by a call to next or previous, with a new element.

 

15.  If an iterator finds that its collection has been modified by another iterator or by a method of the collection itself, it throws a ConcurrentModificationException. Concurrent modification detection is done in a simple way. The collection keeps track of the number of mutating operations (such as adding and removing elements). Each iterator keeps a separate count of the number of mutating operations that it was responsible for. At the beginning of each iterator method, the iterator simply checks whether its own mutation count equals that of the collection. If not, it throws a ConcurrentModificationException.

 

16.  The linked list only keeps track of structural modifications to the list and the set method does not count as a structural modification.

 

17.  Linked lists do not support fast random access. The LinkedList object makes no effort to cache the position information.

 

18.  The list iterator interface also has a method to tell you the index of the current position. The nextIndex method returns the integer index of the element that would be returned by the next call to next; the previousIndex method returns the index of the element that would be returned by the next call to previous. List.listIterator(n) returns an iterator that points just before the element with index n.

 

19.  The only reason to use a linked list is to minimize the cost of insertion and removal in the middle of the list.

 

20.  All methods of the Vector class are synchronized. It is safe to access a Vector object from two threads. In contrast, the ArrayList methods are not synchronized.

 

21.  In Java, hash tables are implemented as arrays of linked lists. Each list is called a bucket. To find the place of an object in the table, compute its hash code and reduce it modulo the total number of buckets. The resulting number is the index of the bucket that holds the element. Sometimes you will hit a bucket that is already filled. This is called a hash collision. Compare the new object with all objects in that bucket to see if it is already present.

 

22.  If you want more control over the performance of the hash table, you can specify the initial bucket count. The bucket count gives the number of buckets used to collect objects with identical hash values. You should set it to somewhere between 75% and 150% of the expected element count. The standard library uses bucket counts that are powers of 2, with a default of 16. (Any value you supply for the table size is automatically rounded to the next power of 2.)

 

23.  If the hash table gets too full, it needs to be rehashed. To rehash the table, a table with more buckets is created, all elements are inserted into the new table, and the original table is discarded. The load factor which is the number of entries in the hash table divided by the number of buckets in the hash table determines when a hash table is rehashed.

 

24.  The Java collections library supplies a HashSet class that implements a set based on a hash table.

 

25.  Be careful when you mutate set elements. If the hash code of an element were to change, the element would no longer be in the correct position in the data structure.

 

26.  A tree set is a sorted collection. You insert elements into the collection in any order. When you iterate through the collection, the values are automatically presented in sorted order. The current implementation uses a red-black tree. If the tree contains n elements, then an average of log2 n comparisons are required to find the correct position for the new element.

 

27.  By default, the tree set assumes that you insert elements that implement the Comparable interface. That interface defines a single method:

public interface Comparable<T>
{
   int compareTo(T other);
}

The call a.compareTo(b) must return 0 if a and b are equal, a negative integer if a comes before b in the sort order, and a positive integer if a comes after b.

 

28.  You tell the tree set to use a different comparison method, by passing a Comparator object into the TreeSet constructor. The Comparator interface declares a compare method with two explicit parameters:

public interface Comparator<T>
{
   int compare(T a, T b);
}

Just like the compareTo method, the compare method returns a negative integer if a comes before b, zero if they are identical, or a positive integer otherwise.

 

29.  The Comparator<T> interface is also declared to have an equals method. You need not override the equals method but that doing so may yield improved performance in some cases. For example, the addAll method of the TreeSet class can work more effectively if you add elements from another set that uses the same comparator.

 

30.  As of Java SE 6, the TreeSet class implements the NavigableSet interface. That interface adds several convenient methods for locating elements and for backward traversal.

 

31.  A double-ended queue, or deque, lets you efficiently add or remove elements at the head and tail. Adding elements in the middle is not supported. Java SE 6 introduced a Deque interface. It is implemented by the ArrayDeque and LinkedList classes, both of which provide deques whose size grows as needed.

 

32.  Queue.add and Queue.offer add the given element to the tail of this deque and returns true, provided the queue is not full. If the queue is full, the first method throws an IllegalStateException, whereas the second method returns false. Queue.remove and Queue.poll remove and returns the element at the head of this queue, provided the queue is not empty. If the queue is empty, the first method throws a NoSuchElementException, whereas the second method returns null. Queue.element and Queue.peek return the element at the head of this queue without removing it, provided the queue is not empty. If the queue is empty, the first method throws a NoSuchElementException, whereas the second method returns null.

 

33.  A priority queue retrieves elements in sorted order after they were inserted in arbitrary order. However, the priority queue does not sort all its elements. The iteration does not visit the elements in sorted order. The priority queue makes use of an elegant and efficient data structure called a heap. A heap is a self-organizing binary tree in which the add and remove operations cause the smallest element to gravitate to the root, without wasting time on sorting all elements.

 

34.  A priority queue can either hold elements of a class that implements the Comparable interface or a Comparator object you supply in the constructor.

 

35.  The Java library supplies two general-purpose implementations for maps: HashMap and TreeMap. Both classes implement the Map interface. A hash map hashes the keys, and a tree map uses a total ordering on the keys to organize them in a search tree. The hash or comparison function is applied only to the keys.

 

36.  The collections framework does not consider a map itself as a collection. However you can obtain views of the map—objects that implement the Collection interface or one of its subinterfaces. There are three views: the set of keys, the collection of values (which is not a set), and the set of key/value pairs:

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

The keySet is not a HashSet or TreeSet, but an object of some other class that implements the Set interface. You cannot add an element to the views.

 

37.  The WeakHashMap class cooperates with the garbage collector to remove key/value pairs when the only reference to the key is the one from the hash table entry. It uses weak references to hold keys. A WeakReference object holds a reference to another object—in our case, a hash table key. Objects of this type are treated in a special way by the garbage collector. Normally, if the garbage collector finds that a particular object has no references to it, it simply reclaims the object. However, if the object is reachable only by a WeakReference, the garbage collector still reclaims the object, but places the weak reference that led to it into a queue. The operations of the WeakHashMap periodically check that queue for newly arrived weak references. The arrival of a weak reference in the queue signifies that the key was no longer used by anyone and has been collected. The WeakHashMap then removes the associated entry.

Commented By Sean, the hash map Entry extends the WeakReference, using the key to initialize parent class and caches the hash of the key.

 

38.  LinkedHashSet and LinkedHashMap remember in which order you inserted items. As entries are inserted into the table, they are joined in a doubly linked list.

 

39.  A linked hash map can alternatively use access order, not insertion order, to iterate through the map entries. Every time you call get or put, the affected entry is removed from its current position and placed at the end of the linked list of entries. (Only the position in the linked list of entries is affected, not the hash table bucket. An entry always stays in the bucket that corresponds to the hash code of the key.) To construct such a hash map, call LinkedHashMap<K, V>(initialCapacity, loadFactor, true)

 

40.  You can create an LRU cache by forming a subclass of LinkedHashMap and override the method:

protected boolean removeEldestEntry(Map.Entry<K, V> eldest)

 Adding a new entry then causes the eldest entry to be removed whenever your method returns true. (This method is called in the add method. )

 

41.  The EnumSet is an efficient set implementation with elements that belong to an enumerated type. Since an enumerated type has a finite number of instances, the EnumSet is internally implemented simply as a sequence of bits. A bit is turned on if the corresponding value is present in the set.

 

42.  The EnumSet class has no public constructors. Use a static factory method to construct the set:

enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);

 

 43.  An EnumMap is a map with keys that belong to an enumerated type. It is simply and efficiently implemented as an array of values. You need to specify the key type in the constructor:

EnumMap<Weekday, Employee> personInCharge = new EnumMap<>(Weekday.class);

 

44.  For IdentityHashMap , the hash values for the keys should not be computed by the hashCode method but by the System.identityHashCode method. That’s the method that Object.hashCode uses to compute a hash code from the object’s memory address. Also, for comparison of objects, the IdentityHashMap uses ==, not equals. It is useful for implementing object traversal algorithms (such as object serialization), in which you want to keep track of which objects have already been traversed.

Commented by Sean: both Object.hashCode and System.identityHashCode are native method.

 

45.  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. The following chart shows the main interfaces of the collection framework:
 

 
46.  There are two fundamental interfaces for collections: Collection and Map. A List is an ordered collection. It provides methods for random accesses.

 

47.  The tagging interface, RandomAccess 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.

 

48.  The Set interface is identical to the Collection interface, but the behavior of the methods is more tightly defined.

 

49.  The SortedSet and SortedMap interfaces expose the comparator object used for sorting, and they define methods to obtain views of subsets of the collections Java SE 6 introduced interfaces NavigableSet and NavigableMap that contain additional methods for searching and traversal in sorted sets and maps.

 

50.  The collection interfaces have quite a few methods that can be trivially implemented from more fundamental methods. The following chart shows these abstract classes and their provided implementations:
 

 
51.  The following chart shows a number of “legacy” container classes which have been integrated into the collections framework:
 

 
52.  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.

 

53.  The static asList method of the Arrays class returns a List wrapper around a plain Java array. 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 the add and remove methods of the associated iterator) throw an UnsupportedOperationException.

 

54.  The method call

Collections.nCopies(n, anObject)

returns an immutable object that implements the List interface and gives the illusion of having n elements, each of which appears as anObject.

 

55.    The method call

Collections.singleton(anObject)

returns a view object that implements the Set interface. The returned object implements an immutable single-element set without the overhead of data structure. The methods singletonList and singletonMap behave similarly.

 

56.  You can form subrange views for a number of collections (i.e. List.subList). You can apply any operations to the subrange, and they automatically reflect the entire list.

 

57.  For sorted sets and maps, you use the sort order, not the element position, to form subranges. The SortedSet interface declares three methods:

SortedSet<E> subSet(E from, E to)
SortedSet<E> headSet(E to)
SortedSet<E> tailSet(E from)

 SortedMap also declares the similar methods

SortedMap<K, V> subMap(K from, K to)
SortedMap<K, V> headMap(K to)
SortedMap<K, V> tailMap(K from)

The NavigableSet interface that was introduced in Java SE 6 lets you specify whether the bounds are included:

NavigableSet<E> subSet(E from, boolean fromInclusive, E to, boolean toInclusive)
NavigableSet<E> headSet(E to, boolean toInclusive)
NavigableSet<E> tailSet(E from, boolean fromInclusive)

 

58.  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, an exception(UnsupportedOperationException) is thrown and the collection remains untouched:

Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap

 

59.  The unmodifiableCollection method (as well as the synchronizedCollection and checkedCollection methods) 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. 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 unmodifiableSet and unmodifiableList methods use the equals and hashCode methods of the underlying collections.

 

60.  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(i.e. Collections.synchronizedCollection). For such views, each method call must be finished completely before another thread can call another method.

 

61.  It is actually possible to smuggle elements of the wrong type into a generic collection:

ArrayList<String> strings = new ArrayList<>();
ArrayList rawList = strings; // get warning only, not an error, for compatibility with legacy code
rawList.add(new Date()); // now strings contains a Date object!

A checked view can detect this problem:

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

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.

 

62.  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.

 

63.  Every collection has a constructor whose parameter is another collection that holds the initialization values.

 

64.  If you have an array that you need to turn into a collection, the Arrays.asList wrapper serves this purpose.

 

65.  The array returned by the toArray method was created as an Object[] array, and you cannot change its type. Instead, use a variant of the toArray method and 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:

String[] values = staff.toArray(new String[0]);

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

staff.toArray(new String[staff.size()]);

In this case, no new array is created.

 

66.  The sort method in the Collections class sorts a collection that implements the List interface. This method assumes that the list elements implement the Comparable interface. If you want to sort the list in some other way, you can pass a Comparator object as a second parameter. If you want to sort a list in descending order, use the static convenience method Collections.reverseOrder(). It returns a comparator that returns b.compareTo(a).

 

67.  The implementation of sorting in the Java programming language does simply dumps all elements into an array, sorts the array by using a different variant of merge sort, and then copies the sorted sequence back into the list. The merge sort algorithm used in the collections library is a bit slower than QuickSort but it’s stable.

 

68.  The list passed to the Collections.sort method must be modifiable but need not be resizable. A list is modifiable if it supports the set method. A list is resizable if it supports the add and remove operations.

 

69.  The Collections class has a method shuffle that does the opposite of sorting—it randomly permutes the order of the elements in a list. If the specified list does not implement the RandomAccess interface and is large, this implementation dumps the specified list into an array before shuffling it, and dumps the shuffled array back into the list.

 

70.  The binarySearch of the Collections class implements the Binary Search algorithm. Note that the collection must already be sorted, or the algorithm will return the wrong answer. A non-negative return value from the binarySearch method denotes the index of the matching object. If the value is negative, then there is no matching element. However, you can use the return value to compute the location where you should insert element into the collection to keep it sorted. The insertion location is insertionPoint = -i - 1;

 

71.  Binary search requires random access. The binarySearch method checks whether the list parameter implements the RandomAccess interface. If it does, the method carries out a binary search; otherwise, it uses a linear search.

 

72.  The legacy collections use the Enumeration interface for traversing sequences of elements. The Enumeration interface has two methods, hasMoreElements and nextElement. These are entirely analogous to the hasNext and next methods of the Iterator interface. The static method Collections.enumeration yields an enumeration object that enumerates the elements in the collection.

 

73.  A property map (Properties) is a map structure of a very special type. It has three particular characteristics:
    a)  The keys and values are strings.
    b)  The table can be saved to a file and loaded from a file.
    c)  A secondary table for defaults is used.

 

74.  The methods of Hashtable are synchronized.

 

75.  Stack class extending the Vector class has the familiar push and pop methods.

 

76.  BitSet class stores a sequence of bits. (It is not a set in the mathematical sense—bit vector or bit array would have been more appropriate terms.) Use a bit set if you need to store a sequence of bits (for example, flags) efficiently. It gives you a convenient interface for reading, setting, and resetting individual bits. Using this interface avoids the masking and other bit-fiddling operations that are necessary if you store bits in int or long variables.