Compared with collections such as Vector, array has a disadvantage that its size can not be varied, but it has two advantages: it is more efficient than any collection, and it performs compile-time type checking.
In contrast, because there is no parameterized type in Java, Java collections only have one type of handles - Object handles. Therefore, you can add every kind of different objects into one collection. In case that you expect all the objects in a collection to be of one type but in fact other types have been added into the collection, exception will be thrown when you down-cast the Object handle to your expected type.
You can try to handle this mistake in the catch block and thus avoid a termination of the program. However, when a wrong object is put into the collection in one part of program, and you get an exception in another part of program, there is not much you can do except the worst debugging job - inspecting the code.
Therefore, as a general guideline, always try to use array first.
Whenever the compiler expects a String object but it encounters an object of another type, it will call its method toString, which is defined in class Object and can be overridden in any class, and is supposed to return a String object:
class Test {
public String toString()
{
return "Class Test";
}
public static void main(String [] s)
{
Test t1 = new Test();
System.out.println(t1);
}
}
Output will be:
Class Test
By implementing its "toString" method, any object can be treated as a String object and has a proper string behaviour. However, because primitives are not objects and have no methods, if you return a number to where a string is expected, compiler will refuse to make the conversion:
public class Test {
private int id = 0;
public String toString()
{ return id; }
}
In this case, simply wrap the numbers in associate wrappers, because they have proper-implemented "toString" methods:
public class Test {
private int id = 0;
public String toString()
{ return (new Integer(id)).toString(); }
}
All Java collection classes have a toString method, which calls each element's toString method one by one. Therefore, if the element object's toString method is properly implemented, you can treat a collection as a String object too. Suppose c1 is a collection object:
System.out.println("The collection is: \n" + c1);
A simple way to create a collection which performs compile-time type checking is to create a class which contains a normal collection as a composition object, and receives objects with a handle of a specific type.
Because all collections in Java hold only Object handles, and in most cases the objects held by the collection have more interfaces than Object, you may find it necessary in most cases when using Java collections that you have to use down-casting.
To create a container class with a advanced sorting method, we create a class which inherits from Vector, and add one method sort( ) to sort the vector's elements, which compares the vector's elements and sort them with an advanced algorithm.
If it is in C++ we would end up here. Because C++ container classes are parameterized. For any type which is to be stored in this container, it should have already overloaded its "<" and "=" operator, so that the sorting algorithm can directly use them.
In Java, however, all containers can only hold Object handles. Class Object only have a equals method but does not have "less than" or "more than" method. Therefore, even if you add such interfaces in your concrete class, from that sortable container class you still can not access them. Of course you can use down-casting in that class, but then it means that the sortable container class can only be used to hold a certian type of objects.
import java.util.*;
public class SortableContainer1 extends Vector {
private Compare compare;
public SortableContainer1(Compare c) // Initialize Compare handle
{ compare = c; }
public void sort()
{
Object temp;
for(int i = 0; i < (size() - 1); i++)
for (int j = i + 1; j < size(); j++)
if( compare.lessThan(elementAt(i), elementAt(j)) )
{
temp = elementAt(i);
setElementAt(elementAt(j), i);
setElementAt(temp, j);
}
}
}
public interface Compare {
public boolean lessThan(Object o1, Object o2);
}
public class Worker {
private int id;
public Worker(int i)
{ id = i; }
public String toString()
{ return "Worker ID: " + id + "\n"; }
public int id()
{ return id; }
}
public class CompareWorker implements Compare {
public boolean lessThan(Object o1, Object o2)
{ return (((Worker)o1).id() < ((Worker)o2).id()); }
}
public class Test {
public static void main(String [] s)
{
Worker [] w1 = new Worker[5];
Compare c1 = new CompareWorker();
SortableContainer1 v1 = new SortableContainer1(c1);
for(int i = 0; i < 5; i++)
{ w1[i] = new Worker(i); }
v1.addElement(w1[3]);
v1.addElement(w1[2]);
v1.addElement(w1[0]);
v1.addElement(w1[1]);
v1.addElement(w1[4]);
System.out.println(v1);
v1.sort();
System.out.println("\n \n" + v1);
}
}
The call back approach is used when the real-life class (e.g. Worker) is an existing class which we could not modify but have to reuse. It looks wierd and twisted. If we can write the real-life class ourselves, there is a better way to solve this sorting problem: instead of letting the sortable container hold an Compare handle and call back to it, we let all objects held by this container inherit from Compare and implement its lessThan method. Then in the sortable container class we can just cast the objects to Compare and directly call its lessThan method.
import java.util.*;
public interface Compare {
public boolean LT(Object obj);
}
public class SortableContainer1 extends Vector {
public void sort()
{
Object temp;
for(int i = 0; i < (size() - 1); i++)
for (int j = i + 1; j < size(); j++)
if( ((Compare)elementAt(i)).LT(elementAt(j)) )
{
temp = elementAt(i);
setElementAt(elementAt(j), i);
setElementAt(temp, j);
}
}
}
public class Worker implements Compare {
private int id;
public Worker(int i)
{ id = i; }
public String toString()
{ return "Worker ID: " + id + "\n"; }
public int id()
{ return id; }
public boolean LT(Object obj) // "less than" method implemented
{ return id < ((Worker)obj).id(); }
}
public class Test {
public static void main(String [] s)
{
SortableContainer1 v1 = new SortableContainer1();
Worker [] w1 = new Worker[5];
for(int i = 0; i < 5; i++)
{ w1[i] = new Worker(i); }
v1.addElement(w1[3]);
v1.addElement(w1[2]);
v1.addElement(w1[0]);
v1.addElement(w1[1]);
v1.addElement(w1[4]);
System.out.println(v1);
v1.sort();
System.out.println("\n \n" + v1);
}
}
Comparing this example from the previous one, we can see that by enabling the real-world class (Worker) to compare itself, both the sortable container and the client implementation become evidently simpler and more natural. That's why I call this method natural comparison method. Here interface Compare works as an enhanced Object class, with added lessThan method.
In both solutions the sortable container class works as an enhanced container class with added sorting functionality. Java 1.3 provides two standard classes with sorting and searching function (plus some other methods): Arrays and Collections.
In C++, iterators belongs to different types of collections, e.g. Vector, Set, Map, etc. When you create an iterator, you have to specify the collection type. This prevents the abstraction from collection type.
In contrast, in Java there is only one type of iterators represented by interface java.util.Iterator. All collections has a method iterator, which returns an implemented Iterator pointing to its first element.
Interface Iterator has two methods:
With these features, you can write a method which receives an iterator and iterate through an completely unknown collection:
import java.util.*;
public class Test {
public static void main(String[] s)
{
Vector v = new Vector();
for(int j = 0; j<10; j++)
{ v. add(new Integer(j)); }
Iterator it = v. iterator();
print(it);
}
public static void print(Iterator i) // This method knows nothing about
{ // the collection it is working on
while(i. hasNext())
System.out.println(i. next());
}
}
There are two kinds of containers which implemets interface java.util.Collection and java.util.Map.
- List: interface, organizes elements through indexes.
- - ArrayList: concrete, rapid random access, expensive when inserting/deleting in middle
- - LinkedList: concrete, convenient deletion/inserting in middle, slower random access
- Set: interface, can not hold duplicated elements.
- - HashSet: concrete, primary choice, much faster but not in order
- - TreeSet: concrete, kept in order
- - HashMap: concrete, primary choice, much faster but not in order
- - TreeMap: concrete, kept in order
Besides, there are still widely used legacy containers such as Vector (can be replaced by ArrayList), stack (can be replaced by LinkedList) and Hashmap.
JGL was developed by ObjectSpace company following the design of C++'s STL closely, with powerful collections and algorithms. Freely available on www.objectspace.com.
Interface java.util.Collection has the following abstract methods:
boolean add(Object) boolean remove(Object) Return true if element removed Iterator iterator() boolean addAll(Collection) Return true if any element is added void clear() boolean contains(Object) boolean containsAll(Collection) Return true if all elements are contained boolean isEmpty() boolean removeAll(Collection) Return true if any element removed boolean retainAll(Collection) Retain only elements in the argument. Returns true if any change occurred. int size() Object[] toArray()
Interface java.util.List extends Collection, and organizes the elements through indexes. From the following extra List methods you can see that most of the extra methods are making use of the indexes of elements.
Used on List, ListIterator inherits from Iterator, and allows traversing in both forward and backward direction.
List has two concrete sub classes:
Because ArrayList and LinkedList (and legacy class Vector, which is equivalent to ArrayList) all implement List, they will produce the same result, only performance is different.
boolean add (int i, Object o) Insert object at location i boolean addAll(int i, Collection c) Insert Collection c at location i Object get(int i) Return element at location i int indexOf(Object o) Return the index of first object o int indexOf(Object o, int i) Return the index of object o after location i int lastIndexOf(Object o) Return last match int lastIndexOf(Object o, int i) Return last match after location i boolean remove(int i) Remove element at location i boolean removeRange(int i1, int i2) Remove elements from location i1 to i2 void set(int i, Object o) Set element at location i to Object o ListIterator listIterator() Return a ListIterator ListIterator listIterator(int i) Return a ListIterator starting from location i
boolean hasPrevious() Corresponding to hasNext( ) int nextIndex() int previousIndex() Object previous() Corresponding to next( )
void addFirst(Object o) void addLast(Object o) Object removeFirst() Object removeLast()
Interface java.util.Set extends Collection. Unlike List and its implementation ArrayList and LinkedList, Set and its implementation HashSet and TreeSet doesn't have any extra methods than Collection. They only implement Collection's methods in different ways.
Set does not hold objects with "equal" values. Whether two objects are equal is decided by their method equals. Now look back at Collection's add methods, and you will understand why the return type is boolean instead of void - it is needed to indicate whether the insertion is successful, because when the actual type is Set it may reject to add one object in, because there is already an object with "equal" value in the Set.
There are two concrete implementations of Set:
The behavior of a tree is such that it's always in order and doesn't have to be specially sorted.
import java.util.*;
public class Test {
public static void main(String[] s)
{
TreeSet h = new TreeSet();
for(int i = 0; i<30; i+=3)
h. add(new Integer(i));
h. add(new Integer(6));
h. add(new Integer(18));
System.out.println(h);
}
}
Output will be:
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]
Compared with List and Set, each element of a Map is a pair of objects: a value object, and a key object used as index to search for the value.
HashMap is faster while TreeMap keeps keys in order. For HashMap, performance can be adjusted by passing capacity and load factor to its constructor. By default the capacity is 101, which is in most cases enough.
Map's methods are
void put(Object key, Object value) insert a pair Object get(Object key) return the value corresponding to the key Collection keySet() return the key Set Collection values() return the value Set Boolean containsKey(Object key )
Notice that the Collection returned by keySet and values are not separate copies of the keys and values. They are only a Collection of handles pointing to the elements in the Map. If you modify the Collection, the Map will be changed.
import java.util.*;
public class Test {
public static void main(String[] s)
{
TreeMap m = new TreeMap();
for(int i = 1; i<20; i+=2)
m. put(new Integer(i), new Integer(i+1));
m. put(new Integer(2), new Integer(2222));
Collection key = m. keySet();
System.out.println("The map: \n" + m);
key. remove(new Integer(2));
System.out.println("\n The map after deleting key 2:\n" + m);
if(m. containsKey(new Integer(5)))
{
System.out.println("\n Map contains key 5");
System.out.println("Its value is " + m. get(new Integer(5)));
}
}
}
Output will be:
The map:
{1=2, 2=2222, 3=4, 5=6, 7=8, 9=10, 11=12, 13=14, 15=16, 17=18, 19=20}
The map after deleting key 2:
{1=2, 3=4, 5=6, 7=8, 9=10, 11=12, 13=14, 15=16, 17=18, 19=20}
Map contains key 5
Its value is 6
Another example:
import java.util.*;
public class TestHashMap {
public static void main(String [] argus) throws IOException
{
Map m1 = new HashMap();
m1.put("key1", "value1");
m1.put("key2", "value2");
m1.put("key3", "value3");
System.out.println(m1.toString());
m1.remove("key2");
System.out.println(m1.toString());
}
}
Legacy class Vector, Stack and Hashtable in package java.util are version 1.1 collections. In version 1.2 they are kept only for consistency. So it is better not to use them for new codes.
One characteristic of these legacy classes is that it is synchronized, while all new collections (Lists, Sets and Maps) are not.
Vector is created by Java's early version. It is equivalent to and can be replaced by ArrayList. It has following methods:
void addElement (Object o1) add object o1 into the vector
Object elementAt(int i) return the object at location i
void setElementAt(Object o1, int i) set the element at location i to object o1
import java.util.*;
public class Test {
public static void main(String [] args)
{
Vector v = new Vector();
Integer ii = null;
for(int i = 0; i < 10; i++)
{
ii = new Integer(i);
v.addElement(ii);
}
Iterator i = v.iterator();
while(i.hasNext())
System.out.println(i.next());
for(int j = 0; j < v.size(); j++)
System.out.println(v.elementAt(j));
}
}
A BitSet is a Vector of a minimum of 64 bits. It allows you to set, clear and check each bit separately. It has three methods:
void set(int i) set bit i void clear(int i) reset bit i boolean get(int i) return true if bit i is 1
The following example is to convert a decimal integer into a binary number held by a BitSet, than check whether the conversion is correct:
import java.util.*;
class Test {
static int power(int a, int b)
{
int result = 1;
for(int i = 1; i <= b; i++)
result *= a;
return result;
}
public static void main(String [] s)
{
int a = 170;
BitSet b1 = new BitSet();
for(int i = 0; i<8; i++) // Convert decimal to binary
if( ((1 << i) & a) != 0 )
b1.set(i);
else
b1.clear(i);
int result = 0;
for(int i = 0; i < 8; i++) // convert the BitSet back to an integer
if(b1.get(i))
result += power(2, i);
System.out.println("Result is (should be 170): " + result);
}
}
Stack can be replaced by LinkedList. It is inherited from Vector, so it has all the methods of Vector such as addElement and elementAt, and two more methods:
Void push(Object ) push one object into the collection Object pop() return the latest pushed object
With the two methods, a Stack can achieve last-in-first-out (LIFO).
Dictionary is an abstract class created by Java's early version which is similar to a Map.
The abstract interfaces of Dictionary are:
int size( ) number of elements in the Dictionary
boolean isEmpty( ) return true if the Hashtable is empty
void put(Object key, Object value) add one pair of objects into the Hashtable
Object get(Object key) return the value object according to the key
void remove(Object key) remove the pair of objects from the Hashtable
Enumerator keys( ) returns an enumerator of the key objects
Enumerator elements( ) return an enumerator of the value objects
Created by Java's early version, Hashtable implements Dictionary. It uses hash code instead of vector's linear method to search for a key, in order to speed up the searching process. Hash code is a method to extract some information from the object in question and turn it into a "relatively unique" int for that object, and use it somewhat as the object's address.
Every objects has a hash code. Root class Object has a method hashcode( ) which returns the object's hashcode, and a method equals( ) to judge whether the hash codes of two objects are equal. Hashtable call these two methods of its key objects to arrange and search for the keys.
Object's hashcode( ) method returns the address of two objects. Therefore, two objects with identical members will not have the same hash code. Object's equals( ) method compares two object's addresses. Therefore two identical objects will not be regarded equal. In most cases, this implementation is not appropriate for your own classes used as keys. You may have to implement yourself these two methods in your class so that two identical objects will have identical hash codes (two different objects, however, may not necessarily have different hash codes), and be regarded as equal. Standard library classes such as Integer has already implemented properly these two methods.
In the equals( ) method, two checks must be done: whether the received handle is a null handle and whether the received object is of the expected type. To check the type, use keyword instanceof.
import java.util.*;
class Key {
private int member;
public Key(int i)
{ member = i; }
public String toString()
{ return "Key = " + member + " "; }
public int hashCode()
{ return member; }
public boolean equals(Object o1)
{
if((o1 != null) && (o1 instanceof Key) && (member == ((Key)o1).member))
return true;
else
return false;
}
}
class Value {
private int member;
public Value(int i)
{ member = i * i; }
public String toString()
{ return "Value = " + member + "\n"; }
}
class Test {
public static void main(String [] s)
{
Hashtable h1 = new Hashtable();
for(int i = 1; i<10; i++)
{
Key k1 = new Key(i);
Value v1 = new Value(i);
h1.put(k1, v1);
}
System.out.println("Size of the Hashtable: " + h1.size() + '\n' + h1);
Key k1 = new Key(3);
if(h1.containsKey(k1))
System.out.println("The value under key 3 is " + h1.get(k1));
}
}
Output will be:
The size of the Hashtable is now 9
{ Key = 9 =Value = 81
, Key = 8 =Value = 64
...
, Key = 1 =Value = 1
}
The value under key 3 is Value = 9
Down-casting is needed to cast the Object handle to the expected type.
Different Collection-based collections ArrayList, TreeList, HashSet, TreeSet can be converted to each other through constructor:
import java.util.*;
public class Test {
public static void main(String [] s)
{
HashSet h = new HashSet();
for(int i = 0; i<10; i++)
{ h. add(new Integer(i)); }
ArrayList a1 = new ArrayList(h);
System.out.println(a1);
}
}
By Andrew Binstock & John Rex, Addison-Wesley 1995.
The Collection interface, as well as some other interfaces in the new collection library, contain "optional" methods, which might not be "supported" in the concrete classes which implement it. Calling the unsupported method will cause an UnsupportedOperationException to be thrown.
However, this will very rarely happen, because the classes which you will be using for 99% of the time -- ArrayList, LinkedList, HashSet, and HashMap, as well as other concrete implementations -- support all of the operations.
Java 1.2 provides two standard classes to perform the functions of the SortableContainer class we created ourselves in 8.5, plus lots of extra methods: java.util.Arrays for arrays, and java.util.Collections for Lists.
void sort(array) - sort array elements using their natural comparison method
void sort(array, Comparator c) - sort array elements with passed Comparator
int binarySearch(array, Object o) - return the location of object o, using natural comparison method
int binarySearch(array, Object o, Comparator c ) - return the location of object o, using passed Comparator
void sort(List) - sort List elements using their natural comparison method
void sort(List, Comparator c) - sort List elements with passed Comparator
int binarySearch(List, Object o) - return the location of object o, using natural comparison method
int binarySearch(List, Object o, Comparator c) - return the location of object o, using passed Comparator
Enumeration enumeration(Collection) - return a legacy enumeration of the argument collection
Object max(Collection) - return the maximum element of the argument Collection, using the object's natural comparison method.
Object max(Collection, Comparator) - return the maximum element of the argument collection, using the passed Comparator
Object min(Collection) - return the minimum element of the argument Collection, using the object's natural comparison method.
Object min(Collection, Comparator) - return the minimum element of the argument collection, using the passed Comparator
List nCopies(int n, Object o) - return a List of size n, which its handles all pointing to object o
List subList(List, int min, int max) - return a sub List of the argument List, from index min to max
You can see from above that the basic sorting and searching methods of Arrays and Collections are almost identical.
Here two key concepts are natural comparison method (interface Comparable) and interface Comparator.
As we have seen in " Sorting Techniques: Call Back", there are two methods to compare user-defined objects using a generic method:
Both compare( ) and compareTo( ) return a positive, zero or negative integer if the left object is larger, equal to or smaller than the right object.
Matured Java classes such as Integer are already inherited from interface Comparable and have already implemented their compareTo( ) method.
The algorithm in Arrays and Collections can compare primitive objects.
One important rule is: before you call binarySearch( ) to search for an object, the array must already be in sorted order, otherwise unpredictable results including infinite loop may happen.
import java.util.*;
public class Worker1 {
private int id = 0;
public Worker1(int i)
{ id = i; }
public int id()
{ return id; }
public String toString()
{ return "" + id; }
}
public class CompWorker1 implements Comparator {
public int compare(Object o1, Object o2)
{ return (((Worker1)o1).id() - ((Worker1)o2).id()); }
}
public class Worker2 implements Comparable {
private int id = 0;
public Worker2(int i)
{ id = i; }
public int id()
{ return id; }
public int compareTo(Object obj)
{ return id - ((Worker2)obj).id(); }
public String toString()
{ return "" + id; }
}
public class Test {
public static void main(String [] s)
{
ArrayList l1 = new ArrayList();
ArrayList l2 = new ArrayList();
for(int i = 0; i<10; i++)
{
l1.add(new Worker1(i));
l2.add(new Worker2(i));
}
Worker1 w1 = new Worker1(333);
Worker2 w2 = new Worker2(333);
l1.set(3, w1);
l2.set(3, w2);
System.out.println("Original Lists: \n" + l1 + "\n" + l2);
CompWorker1 c = new CompWorker1();
Collections.sort(l1, c);
Collections.sort(l2);
System.out.println("After sorting: \n" + l1 + "\n" + l2);
int loc1 = Collections.binarySearch(l1, w1, c);
int loc2 = Collections.binarySearch(l2, w2);
System.out.println("Location of worker(3) are " + loc1 + ", " + loc2);
}
}
Output will be:
Original Lists: [0, 1, 2, 333, 4, 5, 6, 7, 8, 9] [0, 1, 2, 333, 4, 5, 6, 7, 8, 9] After sorting: [0, 1, 2, 4, 5, 6, 7, 8, 9, 333] [0, 1, 2, 4, 5, 6, 7, 8, 9, 333] Location of worker(3)are 9, 9
Class Collections has four more methods which return a unmodifiable collection:
Collection unmodifiableCollection(Collection) List unmodifiableList(List) Set unmodifiableSet(Set) Map unmodifiableMap(Map)
You can use these tools to return to outside callers a unmodifiable collection, while inside your class you can still modify it.
Any attempt to modify the container will produce a UnsupportedOperationException.
Unlike legacy collection Vector, Stack and Hashtable, new collections (Lists, Sets and Maps) are unsynchronized, because it was recognized that collections are frequently used in a way that synchronization provides no benefit, such as single-thread use, read-only use, and used as a part of a larger data object which does its own synchronization. So there is no sense to spend performance on useless features. If you want to use the synchronized features, you can use synchronization wrappers to transform any kind of collection into synchronized collection.
Class Collections has four static methods which return a synchronized container:
Collection synchronizedCollection(Collection) List synchronizedList(List) Set synchronizedSet(Set) Map synchronizedMap(Map)
The new collections library incorporates a fail fast mechanism, which looks for any modification made to the container from other parties other than your responsible process. Once it detects it, it immediately produce a ConcurrentModificationException, instead of detecting it later or using a more complex method.