 Aggregate | Java Programming Collection | ArrayList |
| NavigateAggregate topic:() |
The most basic collection interface is calledCollection. This interface gives the user the generic usage of a collection. All collections need to have the same basic operations. Those are:
|
|
When you put an object in a collection, this object is not actuallyin the collection. Only its object reference is added to the collection. This means that if an object is changed after it was put in an collection, the object in the collection also changes. Thecode listing 5.2 computes the seven next days from tomorrow and stores each date in a list to read it afterwards. See what happens:
|
|
All collection items were meant to be updated to a different date but they all have been updated to the last one. This means that each update has updated all the collection items. ThecurrentDate has been used to fill all the collection items. The collection didn't keep trace of the added values (one of the seven dates) but the added object references (currentDate). So the collection contains the same object seven times! To avoid this issue, we should have coded it this way:
|
|
Now each time we add an item to the collection, it is a different instance. All the items evolve separately. To add an object in a collection and avoid this item being changed each time the source object is changed, you have to copy or clone the object before you add it to the collection.
Objects put into a collection are upcasted to theObject class. This means that you need to cast the object reference back when you get an element out of the collection. It also means thatyou need to know the type of the object when you take it out. If a collection contains different types of objects, we will have difficulty finding out the type of the objects obtained from a collection at run time. For example. let's use this collection with two objects in it:
 | Code section 5.1: Collection feeding.CollectionageList=newArrayList();ageList.add(newInteger(46));ageList.add("50"); |
|
|
This error could have been found earlier, at compile time, by using generic types. TheGenerics have been added since JDK version 1.5. It is an enhancement to the type system of the Java language. All collection implementations since 1.5 now have aparameterized type <E>. TheE refers to anElement type. When a collection is created, the actualElement type will replace the E. In the collection, the objects are now upcasted toE class.
| Code section 5.3: Collection with generics.Collection<Integer>ageList=newArrayList<Integer>();ageList.add(newInteger(46));// Integer can be addedageList.add("50");// Compilation error, ageList can have only Integers inside |
ageList is a collection that can contain only Integer objects as elements. No casting is required when we take out an element.
| Code section 5.4: Item reading.Integerage=ageList.get(0); |
Generics are not mandatory but are is often used with the collection classes.
There is no direct implementation for thejava.util.Collection interface. The Collection interface has five sub interfaces.
Figure 1: The five sub interfaces of the java.util.Collection interface. |
 |
A set collection contains unique elements, so duplicates are not allowed. It is similar to a mathematical Set. When adding a new item to a set, the set calls the methodint hashCode() of the item and compares its result to the hash code of all the already inserted items. If the hash code is not found, the item is added. If the hash code is found, the set calls theboolean equals(Object obj); method for all the set items with the same hashcode as the new item. If all equal-calls return false, the new item is inserted in the set. If an equal-call returns true, the new item is not inserted in the set.
Figure 2: Set class diagram. |
 |
Set interface. Not synchronized. Allows thenull elementsnull not allowedSet cannot have duplicates in it. You may wonder how duplicates are detected when we are adding an object to theSet. We have to see if that object exists in the Set or not. It is not enough to check the object references, the objects' values have to be checked as well.
To do that, fortunately, each java object has theboolean equals(Object obj), method available inherited fromObject. You need to override it. That method will be called by the Set implementation to compare the two objects to see if they are equal or not.
There is a problem, though. What if I put two different type of objects to the Set. I put an Apple and an Orange. They can not be compared. Calling theequals() method would cause aClassCastException. There are two solutions to this:
int hashCode() method and return the same values for the same type of objects and return different values for different type of objects. Theequals() method is used to compare objects only with the same value of hashCode. So before an object is added, the Set implementation needs to:equals() methods passing in the candidate objectequals() andhashCode() methods in the Apple and Orange classesappleEquals() method in the Apple class, and createorangeEquals() method in the Orange classhashCode() method in the Fruit class and return the same value, so theequals() is called by the Set implementationequals() method in the Fruit class for something like this. | Code section 5.5:equals method implementation.publicbooleanequals(Objectobj){booleanret=false;if(thisinstanceofApple&&objinstanceofApple){ret=this.appleEquals(obj);}elseif(thisinstanceofOrange&&objinstanceofOrange){ret=this.orangeEquals(obj);}else{// Can not compare Orange to Appleret=false;}returnret;} |
Note:
equals() andhashCode() methods. The default implementations in Object won't work.hashCode() method if you want to eliminate value duplicates.hashCode() method if you know that the values of your objects are different, or if you only want to prevent adding the exactly same object.hashCode() may be used in other collection implementations, like in a Hashtable to find an object fast. Overriding the defaulthashCode() method may affect performance there.hashCode() method, there is no point overriding theequals() method, as it won't be called.TheSortedSet interface is the same as the Set interface plus the elements in the SortedSet are sorted. It extends the Set Interface. All elements in the SortedSet must implement the Comparable Interface, furthermore all elements must be mutually comparable.
Note that the ordering maintained by a sorted set must be consistent with equals if the sorted set is to correctly implement the Set interface. This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compare method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal.
The SortedSet interface has additional methods due to the sorted nature of the 'Set'. Those are:
E first(); | returns the first element |
E last(); | returns the last element |
SortedSet headSet(E toElement); | returns from the first, to the exclusive toElement |
SortedSet tailSet(E fromElement); | returns from the inclusive fromElement to the end |
SortedSet subSet(E fromElement, E toElement); | returns elements range from fromElement, inclusive, to toElement, exclusive. (If fromElement and toElement are equal, the returned sorted set is empty.) |
In a list collection, the elements are put in a certain order, and can be accessed by an index. Duplicates are allowed, the same element can be added twice to a list. It has the following implementations:
Figure 3: List class diagram. |
 |
List interface is theArrayList. The ArrayList is not synchronized, not thread safe.Vector is synchronized, and thread safe.Vector is slower, because of the extra overhead to make it thread safe. When only one thread is accessing the list, use the ArrayList. Whenever you insert or remove an element from the list, there are extra overhead to reindex the list. When you have a large list, and you have lots of insert and remove, consider using theLinkedList.LinkedList implies a special data structure where the elements/nodes are connected by pointers.Head Node 1 Node 2 Node n ______ | Size | _________________ _______________ _____________ |______| | | point | | | point | | | | | First|-------->| Data | to next |------>| Data | to next|-- ... -->| Data | null | | elem | |______|_________| |______|________| |______|______| |______| ^ | Last | | | elem |----------------------------------------------------------------- |______|
Each node is related to an item of the linked list. To remove an element from the linked list the pointers need to be rearranged. After removing Node 2:
Head Node 1 Node 2 Node n ______ _____________________ | Size | _________________ | _______________ | ______________ |_- 1__| | | point | | | | point | | | | | | First|-------->| Data | to next |---- | Data | to next| -...-->| Data | null | | elem | |______|_________| |______|________| |______|______| |______| ^ | Last | | | elem |----------------------------------------------------------------- |______|
The Queue interface provides additional insertion, extraction, and inspection operations. There are FIFO (first in, first out) and LIFO (last in, first out) queues. This interface adds the following operations to the Collection interface:
E element() | Retrieves, but does not remove, the head of this queue. This method differs from the peek method only in that it throws an exception if this queue is empty |
boolean offer(E o) | Inserts the specified element into this queue, if possible. |
E peek() | Retrieves, but does not remove, the head of this queue, returning null if this queue is empty |
E poll() | Retrieves and removes the head of this queue, or null if this queue is empty |
E remove() | Retrieves and removes the head of this queue. This method differs from the poll method in that it throws an exception if this queue is empty. |
Figure 4: Queue class diagram. |
 |
Figure 5: UML class diagram of the Collection interfaces and their implementations. |
 |
Synchronization is important when you are running several threads. Beware, synchronization does not mean that your collection is thread-safe. A thread-safe collection is also called aconcurrent collection. Most of the popular collection classes have implementations for both single thread and multiple thread environments. The non-synchronized implementations are always faster. You can use the non-synchronized implementations in multiple thread environments, when you make sure that only one thread updates the collection at any given time.
A new Java JDK package was introduced at Java 1.5, that isjava.util.concurrent. This package supplies a few Collection implementations designed for use in multi-threaded environments.
The following table lists all the synchronized collection classes:
| synchronized | non-synchronized | |
|---|---|---|
| List | java.util.Vector | java.util.ArrayList |
| java.util.Stack | ||
| java.util.LinkedList | ||
| java.util.concurrent.CopyOnWriteArrayList | ||
| Set | java.util.TreeSet | |
| java.util.HashSet | ||
| java.util.LinkHashSet | ||
| java.util.concurrent.CopyOnWriteArraySet |
The Java JDK collection implementations are quite powerful and good, so it is unlikely that you will need to write your own. The usage of the different collections are the same but the implementations are different. If the existing collection implementations do not meet your needs, you can write your version of the implementation. Your version of the implementation just needs to implement the samejava.util.Collection interface, then you can switch to using your implementation and the code that is using the collection does not need to be changed.
Use the Collection interface if you need to keep related (usually the same type of) objects together in a collection where you can:
The advantages of using theCollection interface are:
TheCollection interface defines the following basic operations:
boolean add(E o); | Using Element type E |
boolean addAll(Collection c); | |
boolean remove( | |
boolean removeAll(Collection c); | |
boolean retainAll(Collection c); | Returntrue if the collection has changed due to the operation. |
Note that inaddAll() we can add any type of collection. This is the beauty of using the Collection interface. You can have aLinkedList and just call theaddAll(list) method, passing in a list. You can pass in aVector, anArrayList, aHashSet, aTreeSet, aYourImpOfCollection, ...All those different types of collection will bemagically converted to aLinkedList.
Let's have a closer look at thismagic. The conversion is easy because theCollection interface defines a standard way of looping through the elements. The following code is a possible implementation ofaddAll() method of theLinkedList.
| Code section 5.6: Collection transfer.importjava.util.Collectionimportjava.util.Iterator...publicbooleanaddAll(Collectioncoll){intsizeBefore=this.size();Iteratoriter=coll.iterator();while(iter.hasNext()){this.add(iter.next());}if(sizeBefore>this.size()){returntrue;}else{returnfalse;}} |
The above code just iterates through the passed in collection and adds the elements to the linked list. You do not have to do that, since that is already defined. What you might need to code for is to loop through aCustomer collection:
| Code section 5.7: Iteration on a collection.importjava.util.Collectionimportjava.util.Iteratorimportjava.yourcompany.Customer...publicStringprintCustomerNames(CollectioncustomerColl){StringBufferbuf=newStringBuffer();Iteratoriter=customerColl.iterator();while(iter.hasNext()){Customercust=(Customer)iter.next();buf.append(cust.getName());buf.append("\n");}returnbuf.toString();} |
Notice two things:
 | To do: |
| Aggregate | Java Programming Collection | ArrayList |