General-Purpose Implementations

   

General-Purpose Implementations

Fortunately, Sun did not stop with the definition of interfaces when the collections framework was established. The Java API includes seven concrete implementations of the various interfaces found within the framework. These general-purpose implementations will typically suffice when you need a particular collection or map class to support a program. Even if you find a need for a more specialized implementation, you will likely find it easier to use one of the classes in this hierarchy as a starting point rather than implementing one of the interfaces from scratch.

Troubleshooting Tip

If you experience runtime exceptions when using collection classes other than the general-purpose implementations, see " UnsupportedOperationException, " in the "Troubleshooting" section at the end of this chapter.


The implementations discussed in this section provide the basic functionality required by the corresponding interfaces. They are unsynchronized; they do not restrict the elements that can be contained; and the iterators they produce fail quickly and cleanly if any illegal concurrent modification is detected . These implementations are complete in that they support all the optional operations defined by the interfaces.

In an example of good design that you should also adopt, the general-purpose implementations are built from a group of abstract classes that provide partial implementations of the collection framework interfaces. You will find that interfaces often define methods that could easily be supported with default implementations. Given that an interface cannot define any implementation details, the best way to handle this from a design approach is to capture that behavior in an abstract class that can then be extended by multiple concrete implementations. The collections framework does just that with AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList, and AbstractMap. These classes, for the most part, implement the required interface operations and throw an UnsupportedOperationException for the optional ones. If no default behavior exists at this level for a required operation, the corresponding method is declared as abstract in these classes.

A common comment about these implementations is that, unlike the legacy collection classes introduced earlier, they are not synchronized to support access by multiple threads. This is not a drawback, however. The later section "Collection Utilities and Wrappers" describes how to obtain synchronized versions of these classes when you require them. This aspect of the general-purpose implementations is actually a feature. When using these classes, you have the flexibility to select between synchronized and unsynchronized implementations. You should avoid the overhead of synchronized collections when your application does not require it.

ArrayList

ArrayList is a resizable implementation of List based on an array that is the collection framework replacement for Vector. Its functionality is much like Vector, but it is not synchronized. It supports all the optional methods of Collection and List and allows all values, including null, as elements. When the capacity of an ArrayList is exceeded, it is recreated to grow as necessary. The use of an underlying array gives ArrayList much better performance for retrieving objects by index than that obtained with LinkedList. The tradeoff is that ArrayList does not perform as well when inserting and removing elements.

An ArrayList can be constructed with no arguments, an initial capacity, or a Collection to copy:

 public ArrayList() public ArrayList(int initialCapacity) public ArrayList(Collection c) 

ArrayList extends AbstractList, which in turn extends AbstractCollection. Part of the basic List functionality that is required is provided through this inheritance hierarchy. The ArrayList implementation overrides the abstract and optional methods found in AbstractList.

ArrayList also defines the ensureCapacity and trimToSize methods to allow better management of its internal mechanisms. You should call ensureCapacity prior to adding a large number of items to an ArrayList to prevent the possibility of multiple internal reallocations. You can use trimToSize to minimize the amount of memory required by an ArrayList after its maximum size is determined These methods are declared with the following signatures:

 public void ensureCapacity(int minCapacity) public void trimToSize() 

Listing 10.1 shows example calls to many of the methods implemented by ArrayList.

Listing 10.1 ArrayListExample.java ” Calls to the Various ArrayList Methods
 import java.util.ArrayList; public class ArrayListExample {   public void doExample() {     ArrayList myList = new ArrayList(5);  // set initial array capacity to 5     // load the list with integers 0-4 wrapped in Integer     for ( int i=0; i<5; i++) {       myList.add( new Integer(i) );     }     System.out.println( "List contains " + myList.size() + " elements" );     // locate a specific object in the list     Integer int2 = new Integer(2);     System.out.println( "List contains Integer(2): " +       myList.contains(int2) );     System.out.println( "Integer(2) is at index " + myList.indexOf(int2) );     // replace an object and then locate it by index     myList.set(2, new Integer(99));     System.out.println( "Get element at index 2: " + myList.get(2) );     // add 5 more elements - capacity will grow automatically     for ( int i=5; i<10; i++) {       // add by specifying the index       myList.add( i, new Integer(i) );     }     // add 5 more elements, but increase the capacity first     myList.ensureCapacity(15);     for ( int i=10; i<15; i++) {       myList.add( new Integer(i) );     }     // take the last 5 elements back out and reduce the capacity     myList.subList(10,15).clear();     myList.trimToSize();     // create another list and copy it into the original one     ArrayList otherList = new ArrayList();     otherList.add( new String("otherList 1") );     otherList.add( new String("otherList 2") );     myList.add(7,otherList);     // display the list elements     System.out.println(myList);   }   public static void main( String args[] ) {     new ArrayListExample().doExample();   } } 

If you execute the code in Listing 10.1, you get the following output:

 List contains 5 elements List contains Integer(2): true Integer(2) is at index 2 Get element at index 2: 99 [0, 1, 99, 3, 4, 5, 6, [otherList 1, otherList 2], 7, 8, 9] 

LinkedList

The array-based List implementation provided by ArrayList works well when you need random access to a collection of objects. Of course, there are always tradeoffs to consider. ArrayList is well suited for accessing objects by index, but at the price of reduced performance when inserting and removing elements. This is where the value of an interface-based collection framework comes into play. LinkedList also implements the List interface, but it is optimized instead for sequential data access and fast insertions and removals. By way of class hierarchy, LinkedList extends AbstractSequentialList, which extends AbstractList. AbstractSequentialList partially implements List in a manner that favors sequential access.

As with the other general-purpose implementations, LinkedList implements all the optional List methods and allows all values, including null. LinkedList supports its operations based on a doubly linked list implementation, which is a concept you have likely seen, or even implemented yourself, in other languages. In this construct, each element in the list maintains a reference to the element before it and the element after it. When a new element is inserted, only the references associated with the new element and the two existing elements between which it is inserted are changed. The removal of an element is just as easy. The tradeoff between LinkedList and ArrayList is in accessing an element by its index. A LinkedList must be traversed sequentially to locate a specific object, so it will never have the performance of an ArrayList when random access is required.

Note

If you have worked with linked lists in other languages, you are probably accustomed to working with pointers to maintain the links. As in all cases, Java works only with object references and not pointers. There is nothing within the implementation of LinkedList, or any other Java class, that relies on pointer arithmetic.


A LinkedList can be constructed with no arguments, or a Collection to copy:

 public LinkedList() public LinkedList(Collection c) 

The elements in the middle of a LinkedList are slow to retrieve, but those at the beginning and end are easily accessible. The class provides two methods beyond those defined by List to simplify this further:

 public Object getFirst() public Object getlast() 

The storage mechanism used by LinkedList also readily supports adding to, or removing from, the beginning or end of a list, so convenience methods are provided for that also:

 public void addFirst(Object o) public void addLast(Object o) public Object removeFirst() public Object removeLast() 

The two removal methods return the object that is removed from the collection. These methods throw a NoSuchElementException if called when the list is empty, so you should also check isEmpty before using either of them.

The ease of inserting and removing elements from a LinkedList make it the preferred choice for stack and queue implementations. Where ArrayList is the framework's replacement for Vector, LinkedList is a similar replacement for Stack. Again, LinkedList is not synchronized, but you can obtain a synchronized version using a static method of the Collections class.

Listing 10.2 shows how a LinkedList can be used to implement a stack using the same method signatures as the Stack class.

Listing 10.2 LinkedListStack.java ” A Stack Built from a LinkedList
 import java.util.LinkedList; import java.util.EmptyStackException; public class LinkedListStack {   private LinkedList listDelegate = new LinkedList();   public boolean empty() {     return listDelegate.isEmpty();   }   // return the element on top of the stack without removing it   public Object peek() {     if ( !this.empty() ) {       return listDelegate.getFirst();     }     throw new EmptyStackException();   }   // return the element on top of the stack and remove it   public Object pop() {     if ( !this.empty() ) {       return listDelegate.removeFirst();     }     throw new EmptyStackException();   }   // place an object on top of the stack   public Object push(Object item) {     listDelegate.addFirst(item);     return item;   }   // look for an object in the stack   public int search(Object item) {     return listDelegate.indexOf(item);   }   public static void main( String args[] ) {     LinkedListStack stack = new LinkedListStack();     // push 5 elements onto the stack     for ( int i=0; i<5; i++ ) {       stack.push( new Integer(i) );     }     System.out.println("Peek at the top of the stack: " + stack.peek() );     // empty the stack     while ( !stack.empty() ) {       System.out.println("Pop: " + stack.pop() );     }   } } 

If you execute the code in Listing 10.2, you get the following output:

 Peek at the top of the stack: 4 Pop: 4 Pop: 3 Pop: 2 Pop: 1 Pop: 0 

Listing 10.2 defines a fairly simple class, but, in addition to showing the use of LinkedList, it also demonstrates an important design concept. LinkedListStack could have been implemented by extending LinkedList instead of holding a LinkedList object as a class member. Instead, the approach shown here is one of delegation, which focuses on composition rather than class inheritance. To reflect a good object-oriented design, LinkedListStack should reuse the functionality of LinkedList in a way that leaves it encapsulated and clearly divides responsibility between the cooperating classes. Inheriting from LinkedList would have achieved some of the same benefits, but it would have locked LinkedListStack into a class hierarchy without providing any advantages. If a better underlying implementation for a stack were to come along later, LinkedListStack could be modified internally to use it without requiring any externally visible changes.

HashMap

Just as Vector and Stack have their replacements in ArrayList and LinkedList, Hashtable has a replacement in HashMap. HashMap extends AbstractMap to implement the Map interface using an internal hashtable representation. It makes no guarantee about the storage order of its associations, and, similar to the other general-purpose implementations, it supports the optional methods of Map, allows null (as either a key or a value), and is not synchronized.

A HashMap can be constructed with no arguments, an initial capacity, a capacity and a load factor, or a Map to copy:

 public HashMap() public HashMap(int initialCapacity) public HashMap(int initialCapacity, float loadFactor) public HashMap(Map m) 

The hash table basis for HashMap supports good performance of both its put and get operations. Performance of the class is driven, for the most part, by the assigned capacity and load factor. The tradeoffs related to these parameters are mostly based on competition between iteration speed and element insertion time. The capacity of a HashMap is the number of buckets it uses to hold keys, and the load factor is a weighting used to determine how full the map can get before the capacity is automatically increased.

Whenever the number of elements stored in a HashMap exceeds the product of its capacity and load factor, the rehash method is called to double the capacity and restructure the map. You can reduce the occurrences of this operation by setting the initial capacity sufficiently high, but the time to iterate through a HashMap grows when you do this. The load factor defaults to 0.75, which is regarded as a good balance between access time and storage space costs. If you isolate a performance bottleneck to the use of a HashMap, you should experiment with other values for the initial capacity.

Listing 10.3 shows example calls to many of the methods implemented by HashMap.

Listing 10.3 HashMapExample.java ” Calls to Various HashMap Methods
 import java.util.HashMap; public class HashMapExample {   public void doExample() {     HashMap myMap = new HashMap(2);     Employee emp = new Employee( "123-45-6789", "Smith", "John" );     myMap.put( emp.getSocialSecurityNumber(), emp );     emp = new Employee( "987-65-4321", "Doe", "Jane" );     myMap.put( emp.getSocialSecurityNumber(), emp );     if ( myMap.containsKey("123-45-6789") ) {       System.out.println("Found by key: " + myMap.get("123-45-6789"));     }     if ( myMap.containsValue(emp) ) {       System.out.println("Map contains value: " +         myMap.get(emp.getSocialSecurityNumber()));     }     // clear the list and verify that it's empty     myMap.clear();     System.out.println("Map is now " +       (myMap.isEmpty() ? "Empty" : "Not Empty"));   }   public static void main( String args[] ) {     new HashMapExample().doExample();   } } class Employee {   private String socialSecurityNumber;   private String lastName;   private String firstName;   public Employee( String ssn, String lname, String fname ) {     socialSecurityNumber = ssn;     lastName = lname;     firstName = fname;   }   // the SSN can be retrieved, but is immutable, which   // is best for an object used as a key   public String getSocialSecurityNumber() {     return socialSecurityNumber;   }   public String toString() {     return socialSecurityNumber + " " + lastName + ", " + firstName;   } } 

If you execute the code in Listing 10.3, you get the following output:

 Found by key: 123-45-6789 Smith, John Map contains value: 987-65-4321 Doe, Jane Map is now Empty 

TreeMap

TreeMap implements SortedMap by extending AbstractMap and using a Red-Black tree to maintain its keys in sorted order. This sorting results in performance of the containsKey, get, put, and remove operations that remains logarithmically proportional to the number of entries in the map. Although this is relatively efficient, you should rely on HashMap if you do not require sorting functionality.

A TreeMap can be constructed with no arguments, a Map or a SortedMap to copy, or a Comparator:

 public TreeMap() public TreeMap(Map m) public TreeMap(SortedMap m) public TreeMap(Comparator c) 

Remember that a SortedMap must be told how to sort its keys. This can be accomplished by either providing a Comparator or using keys that implement java.lang.Comparable. The constructor that accepts a Comparator obviously relies on this first method for sorting its keys. If you construct a TreeMap without any arguments or with a Map, the keys must implement Comparable. If you supply a SortedMap, a new map is created using the same sort mechanism.

You use a TreeMap exactly like you use HashMap, only you have access to the additional methods defined by SortedMap that rely on the ordering of the keys.

WeakHashMap

The WeakHashMap provides a hash table “based implementation of Map just as in the case of HashMap, but it does it using weak references to the keys. Prior to Java 1.2, the garbage collector would reclaim the memory allocated to an object only when no references to that object remained. The Java 1.2 release introduced the java.lang.ref package to allow you to make use of references that release their association to an object when certain events occur. In particular, you can establish a WeakReference to an object that is automatically cleared when the garbage collector detects that no other references to the object exist. Basically, it's your way of telling the compiler that you care about an object, but only as long as some other part of your program is using it too.

When you create a WeakHashMap, you can associate information with each key object that is only maintained as long as that key is in use elsewhere. After all other references to the object are released, the garbage collector will mark it as unused and remove it from the hash table.

Just like a HashMap, a WeakHashMap can be constructed with no arguments, an initial capacity, a capacity and a load factor, or a Map to copy:

 public WeakHashMap() public WeakHashMap(int initialCapacity) public WeakHashMap(int initialCapacity, float loadFactor) public WeakHashMap(Map m) 

The WeakHashMap constructor that accepts a Map was added in the Java 1.3 release. The primary purpose was to make it consistent with HashMap and to follow the Map interface decree that each implementation implement a copy constructor of this type.

HashSet

HashSet provides a basic implementation of Set by extending AbstractSet and making use of an underlying HashMap instance. A HashSet does not maintain any particular order of its elements, but it does implement the optional methods of Set and allow null as an element. When you need a collection that does not allow duplicate elements and does not have to be ordered, HashSet can supply the appropriate functionality and produce quick lookup times given its HashMap backing.

A HashSet can be constructed with no arguments, an initial capacity, a capacity and a load factor, or a Collection to copy:

 public HashSet() public HashSet(int initialCapacity) public HashSet(int initialCapacity, float loadFactor) public HashSet(Collection c) 

The capacity and load factor parameters in the HashSet constructors are used to construct the supporting HashMap.

TreeSet

TreeSet implements SortedSet by extending AbstractSet and using an underlying TreeMap instance. The use of TreeMap keeps the performance of the add, contains, and remove operations logarithmically proportional to the number of entries in the set. HashSet is a better choice if you do not require sorting functionality.

A TreeSet can be constructed with no arguments, a Collection or a SortedSet to copy, or a Comparator:

 public TreeSet() public TreeSet(Collection c) public TreeSet(SortedSet s) public TreeSet(Comparator c) 

As with SortedMap, a SortedSet must be told how to sort its elements. This can be accomplished by either providing a Comparator or only storing Comparable objects. If you construct a TreeSet without any arguments or with a Collection, the elements must implement Comparable. If you supply a SortedSet, a new set is created using the same sort mechanism.

You use a TreeSet exactly like you use HashSet, only you have access to the additional methods defined by SortedSet that rely on the ordering of the elements.

   


Special Edition Using Java 2 Standard Edition
Special Edition Using Java 2, Standard Edition (Special Edition Using...)
ISBN: 0789724685
EAN: 2147483647
Year: 1999
Pages: 353

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net