Collecting Objects - Beginning Java 7 - page 529

The AbstractList class,whichpartiallyimplements List ,hasthistosayabout
hashCode() : This implementation uses exactly the code that is used to define the
list hash function in the documentation for the List.hashCode() method.
When it comes to lists, you should also be aware of the RandomAccess interface:
ArrayList implements the RandomAccess interface, which is a marker inter-
face used by List implementation classes to indicate that they support fast (gener-
ally constant time) random access. The primary purpose of this interface is to allow
generic algorithms to alter their behavior to provide good performance when applied
to either random or sequential access lists.
The best algorithms for manipulating random access List implementations (such
as ArrayList ) can produce quadratic behavior when applied to sequential access
List implementations (such as LinkedList ). Generic list algorithms are en-
couraged to check whether the given list is an instance of this interface (via in-
stanceof ) before applying an algorithm that would provide poor performance if
it were applied to a sequential access list, and to alter their behavior if necessary to
guarantee acceptable performance.
The distinction between random and sequential access is often fuzzy. For example,
some List implementations provide asymptotically linear (a line whose distance to
a given curve tends to zero) access times if they get huge, but constant access times
in practice. Such a List implementation class should generally implement this in-
terface. As a rule of thumb, a List implementation class should implement this in-
terface if, for typical instances of the class, the following loop:
for (int i=0, n=list.size(); i < n; i++) list.get(i);
runs faster than the following loop:
for (Iterator i=list.iterator(); i.hasNext();) i.next();
Keep these advices in mind and you should find it easier to extend the Collections
Framework.
You might require a collection that isn't supported by the Collections Framework
(or perhaps you only think it isn't supported). For example, you might want to model
a sparse matrix , a table where many or most of its elements are zeros (see ht-
tp://en.wikipedia.org/wiki/Sparse_matrix ) .Asparsematrixisagood
data structure for implementing a spreadsheet, for example.
If the elements represent bits, you could use BitSet to represent the matrix. If
the elements are objects, you might use an array. The problem with either approach is
scalability and the limits of heap space. For example, suppose you need a table with
100,000 rows and 100,000 columns, yielding a maximum of 10 billion elements.