18 The Collection Framework

18.1 INTRODUCTION

The Collection Framework provides a well-designed set of interfaces and classes for storing and manipulating groups of data as a single unit, a collection. The framework provides a convenient API to many of the abstract data types used in data structure curriculum: maps, sets, lists, trees, arrays, hashtables and other collections. Because of their object-oriented design, the Java classes in the collections framework encapsulate both the data structures and the algorithms associated with these abstractions. The framework provides a standard programming interface to several most common abstractions, without burdening the programmer with too many procedures and interfaces. The operations supported by the collections framework nevertheless permit the programmer to easily define higher level of abstractions, such as stacks, queues and thread-safe collections. Some of the features of collections are presented below:

1.   The implementation of the fundamental collections like dynamic arrays, linked lists, trees and hash tables is highly efficient which results in high performance.

2.   All the collections provide almost same look and feel and their way of working is similar to each other.

3.   Extending a collection is very easy, and so is adapting.

4.   Whole of the collections are designed around a set of standard interfaces (discussed shortly).

5.   Collection Framework also allows creating one's own collection, if required.

18.2 COLLECTION FRAMEWORK

The collections framework is made up of a set of interfaces for working with groups of objects. The different interfaces describes different types of groups. For the most part, once the differences are understood, understanding the framework is easy. While one always needs to create specific implementations of the interfaces, access to the actual collection should be restricted to the use of the interface methods, thus allowing a programmer to change the underlying data structure, without altering the rest of the code. Figure 18.1 shows the framework hierarchy.

Figure 18.1 Collection interface hierarchy

In mathematics, a map is just a collection of pairs. In the Collection Framework, however, the interfaces Map and Collection are distinct. The reasons for this distinction have to do with the ways that Set and Map are used in the Java libraries. The typical application of a Map is to provide access to values stored by keys. The sets of collection operations are all there, but one works with a key-value pair instead of an isolated element. Map is therefore designed to support the basic operations of get() and put(), which are not required by Set.

The following points need to be remembered regarding Collection Framework:

(i)   The Collection interface is a group of objects, with duplicates allowed.

(ii)  The Set interface extends Collection but forbids duplicates.

(iii) The List interface extends Collection, allows duplicates, and introduces positional indexing.

(iv)  The Map interface extends neither Set nor Collection.

The other interfaces of the Collection Framework are described later in the chapter. In this section, the aforesaid interfaces are discussed in detail.

18.2.1 Collection Interface

The Collection interface is used to represent any group of objects, or elements. The interface is used when a group of elements is to be worked in as general a manner as possible. This interface is implemented by all collection classes. Frequently used method of this interface is given in the Table 18.1. As the Collection method is at the root of the hierarchy, understanding all its methods is a must.

The interface supports basic operations like adding and removing. Object is added to collection using 'add' and removed using 'remove'. When an element is needed to be removed, only a single instance of the element in the collection is removed, if present. Both of the method takes object as argument; it means any type of argument can be added to the collection but it must be an object. Primitive types must first be converted to objects before they can be added to collection.

The Collection interface also supports query operations : size(). isEmpty(), contains() etc.

The iterator() method of the Collection interface returns an Iterator. With the Iterator interface methods, a collection can be traversed from start to finish and elements safely removed from the underlying Collection. It is discussed in detail later in the chapter.

The containsAll() method allows to discover if the current collection contains all the elements of another collection, a subset. The remaining methods are optional in that a specific collection might not support the altering of the collection. The addAll() method ensures all elements from another collection are added to the current collection, usually a union. The clear() method removes all elements from the current collection. The removeAll() method is like clear() but only removes a subset of elements. The retainAll() method is similar to the removeAll() method but does what might be perceived as the opposite: It removes from the current collection those elements not in the other collection, an intersection.

Table 18.1 Method of Collection interface

18.2.2 The List Interface

The List interface extends the Collection interface to define an ordered collection, permitting duplicates. The interface adds position-oriented operations, as well as the ability to work with just a part of the list. The first element in the list starts at index 0. Elements can be added and accessed by their position in the list. The method of List interface are shown in the Table 18.2.

Table 18.2 Methods of List interface

The position-oriented operations include the ability to insert an element or Collection, get an element, as well as remove or change an element. Searching for an element in a List can be started from the beginning or end and will report the position of the element, if found.

void add(int index, Object element)
boolean addAll(int index, Collection collection)
Object get(int index)
int indexOf(Object element)
int lastIndexOf(Object element)
Object remove(int index)
Object set(int index, Object element)

The List interface also provides for working with a subset of the collection, as well as iterating through the entire list in a position-friendly manner:

ListIterator listIterator()
ListIterator listIterator(int startIndex)
List subList(int fromIndex, int toIndex)

In working with subList(), it is important to mention that the element at fromIndex is in the sublist, but the element at toIndex is not. This loosely maps to the following loop test cases:

for(int i = fromIndex; i<toIndex; i++)
{
   process element at position i
}

In addition, it should be mentioned that changes to the sublist (like add(), remove() and set() calls) have an effect on the underlying List.

The ListIterator interface extends the Iterator interface to support bidirectional access, as well as adding or changing elements in the underlying collection. It will be discussed later in detail.

18.2.3 The Set Interface

The Set interface extends the Collection interface and, by definition, forbids duplicates within the collection. All the original methods are present and no new method are introduced. The concrete Set implementation classes rely on the equals() method of the object added to check for equality.

18.2.4 The SortedSet Interface

The Collection Framework provides a special Set interface for maintaining elements in a sorted order: SortedSet. The methods of this interface are shown in the Table 18.3.

Table 18.3 Method of SortedSet interface

The interface provides access methods to the ends of the set as well as to subset of the set. When working with subset of the list, changes to the subset are reflected in the source set. In addition, changes to the source set are reflected in the subset. This works because subsets are identified by elements at the end points, not indices. In addition, if the fromElement is part of the source set, it is part of the subset. However, if the toElement is part of the source set, it is not part of the subset. If a particular toelement is to be in the subset, the next element must be found. In the case of a String, the next element is the same string with a null character appended element (string"")

18.3 THE COLLECTION CLASS

In this section, all the collection classes are discussed that implement all or some of the interfaces discussed earlier. Each class will be described in detail. They are given in the Table 18.4.

Table 18.4 Collection classes

18.4 ARRAYLIST AND LINKEDLIST CLASSES

There are two general-purpose List implementations in the Collection Framework: ArrayList and LinkedList. Which of two List implementations should be used depends on the specific needs. If random access needs to be supported, without inserting or removing elements from any place other than the end ArrayList offers the optimal collection. If, however, one needs to frequently add and remove elements from the middle of the list and only access the list elements sequentially LinkedList offers the better implementation.

Each of the classes is discussed in turn:

ArrayList Class

The declaration of ArrayList class is given as:

public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

It is visible that ArrayList class extends the class AbstractList and implements the four interfaces:

List, RandomAccess, Cloneable and Serializable.

The class is resizable-array implementation of the List interface. It implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provide methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector (discussed later), except that it is unsynchronized.)

The class ArrayList is like dynamic array of objects. The elements can be added or removed dynamically. When elements are added, array list grows and when elements are removed it shrinks. The initial size of array in list is some fixed size. As this size exceeds, size is automatically increased. Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically.

The ArrayList has the following constructors:

1.   public ArrayList()
This form of constructor creates an empty list with an initial capacity of ten.

2.   public ArrayList(Collection c)
This form of constructor creates a list containing the elements of the specified collection c. The ArrayList instance has an initial capacity of 110 per cent the size of the specified collection.

3.   public ArrayList(int initialCapacity)
This form of constructor creates an empty list with the specified initial capacity.

/*PROG 18.1 DEMO OF ARRAYLIST CLASS VER 1*/

import java.util.*;
class JPS1
{
   public static void main(String args[])
   {
          ArrayList AL1 = new ArrayList();
          System.out.println("
Initial capacity of AL1:=
          "+AL1.size());
          AL1.add("one");
          AL1.add("two");
          ArrayList AL2 = new ArrayList(AL1);
          ArrayList AL3 = new ArrayList(5);
          System.out.println("Capacity of AL1:= "+AL1.size());
          System.out.println("Capacity of AL2:= "+AL2.size());
          System.out.println("Capacity of AL3:= "+AL3.size());
   }
}

OUTPUT:

Initial capacity of AL1:= 0
Capacity of AL1:= 2
Capacity of AL2:= 2
Capacity of AL3:= 0

Explanation: As stated earlier, capacity is the size of the array list, that is, the number of elements in it, so initial size of AL1 is displayed as 0. After adding two elements the size of AL1 becomes 2. The array list AL2 is initialized with AL1, that is, initializing a collection with a collection, and AL3 is constructed with initial capacity of 5 yet, size is displayed as 0.

/*PROG 18.2 DEMO OF ARRAYLIST CLASS VER 2 */

import java.util.*;
class JPS2
{
   public static void main(String args[])
   {
          ArrayList AL = new ArrayList();
          System.out.println("
Initial size of AL:= "
                              + AL.size());
          AL.add("Moon");
          AL.add("Sun");
          AL.add("Stars");
          AL.add(1, "Earth");
          System.out.println("Size of AL after additions: "
                              + AL.size());
          System.out.println("Array List contains 
"+ AL);
          AL.remove("Sun");
          AL.remove(1);
          System.out.println("After removing two elements
                 size:= " + AL.size());
                 System.out.println("Array List now contains 
"
                        + AL);
   }
}

OUTPUT:

Initial size of AL: = 0
Size of AL after additions: 4
Array List contains
[Moon, Earth, Sun, Stars]
After removing two elements size: = 2
Array List now contains
[Moon, Stars]

Explanation: This program constructs an empty array list AL and adds some elements to it using overloaded form of add method. After addition, size automatically increases. Note when displaying the array list, the reference AL is displayed which internally calls toString method. Removal of elements is done using remove method: one is through index and second is using elements itself. Note the list is displayed in its default form.

/*PROG 18.3 DEMO OF ARRAYLIST CLASS VER */

import java.util.*;
class JPS3
{
   public static void main(String args[])
   {
          ArrayList AL = new ArrayList();
          System.out.println("
Initial size of AL: "
                              + AL.size());
          AL.add(new String("Moon"));
          AL.add(new Integer(12));
          AL.add(new Date());
          AL.add(new Double(23.344));
          AL.add(new Boolean(true));
          AL.add(new Character('P'));
          System.out.println("Array List contains 
"  +AL);
   }
}

OUTPUT

Initial size of AL: 0
Array List contains
[Moon, 12, Sat Dec 20 10:19:32 PST 2008, 23.344, true, P]

Explanation: In this program, object of different types are stored into the ArrayList AL. Rest is self-explanatory. In case, the list is to be displayed in a manner different from the above one, the get method can be used as:

for(int i = 0; i<AL.size();i++)
System.out.println("Element "+i+":"+AL.get(i));

The output of this will be:

Element 0:Moon
Element 1:12
Element 2:Sat Dec 20 10:39:32 PST 2008
Element 3:23.344
Element 4:true
Element 5:P

/*PROG 18.4 DEMO OF ARRAYLIST CLASS VER 4 */

import java.util.*;
class JPS4
{
   public static void main(String args[])
   {
          ArrayList AL = new ArrayList();
          int i, t, max;
          for(i=0;i<10;i++)
          AL.add(new Integer(i+1));
          System.out.println("
Array list contains
"+AL);
          Object obarr[]=AL.toArray();
          max =((Integer)obarr[0]).intValue();
                 for(i=1;i<obarr.length;i++)
              {
                 t =((Integer)obarr[i]).intValue();
                 if(max<t)
                 max = t;
              }
          System.out.println("
Maximum of array is "+max);
   }
}

Explanation: This program demonstrates how an ArrayList instance can be converted into an array. This may prove helpful in a number of programming situations. Initially in the ArrayList instance some integer objects are put. The ArrayList instance AL is converted into an array using toArray method of ArrayList class. The array returned is of type Object class. Later the maximum of 10 integers are found out by getting integer values from object elements using intValue method. Note one has to make sure in the beginning that ArrayList contains Integer objects.

18.4.1 Maintaining the Capacity

For the management of capacity, the ArrayList class provides two functions: ensureCapacity and trimToSize()

The signature of the method ensureCapacity() is given as:

public void ensureCapacity(int minCapacity)

The method increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument. The reason for having this function is that in case one is sure in advance that minCapacity elements will be used in the ArrayList instance then this function can be used. Later when it is realized that capacity was assigned more than it was needed the capacity can be brought equal to the number of elements in the ArrayList instance using trimtoSize function. The signature of the method is given as:

public void trimToSize()

The method trims the capacity of this ArrayList instance to be the list's current size. An application can use this operation to minimize the storage of an ArrayList instance.

18.4.2 The LinkedList Class

The declaration of LinkedList class given in Java is as follows:

public class LinkedList extends AbstractSequentialList
implements List, Queue, Cloneable, Serializable

The class is a linked list implementation of the List interface. It implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue or double-ended queue (deque).

The class has got two constructors.

1.   public LinkedList()
This form of constructor creates an empty list:

2.   public LinkedList(Collection c)
This form of constructor creates a list containing the elements of the specified collection c.

The various new methods (apart from the interfaces inherited) and other methods are shown in the program given below:

/*PROG 18.5 DEMO OF LINKED LIST CLASS VER 1 */

import java.util.*;
class JPS5
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          LinkedList LL = new LinkedList();
          show("
Initial size of LL: " + LL.size());

          LL.addFirst(new Integer(1));
          LL.addFirst(new Integer(2));
          LL.addFirst(new Integer(3));
          LL.addFirst(new Integer(4));
          LL.addLast(new Float(2.5f));
          LL.addLast(new Float(12.5f));

          show("List is " + LL);
          show("First element:" + LL.getFirst());
          show("Last element:" + LL.getLast());

          show("Removed First element: "+LL.removeFirst());
          show("Removed Last element: " +LL.removeLast());

          show("List Now");
          for (int i = 0; i < LL.size(); i++)
          System.out.println("Element"+i+":"+LL.get(i));
   }
}

OUTPUT:

Initial size of LL: 0
List is [4, 3, 2, 1, 2.5, 12.5]
First element:4
Last element:12.5
Removed First element: 4
Removed Last element: 12.5
List Now
Element 0:3
Element 1:2
Element 2:1
Element 3:2.5

Explanation: The method addFirst adds the specified element at the beginning of the list, and addLast at the end of the list. Methods getLast and getFirst return as the last and the first element of the list, respectively. Methods removeLast and removeFirst remove from the list last and first element, respectively. In the end, using get method and for loop, the whole list is displayed.

/*PROG 18.6 DEMO OF LINKEDLIST CLASS VER 2 */

import java.util.*;
class JPS6
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          LinkedList LL1 = new LinkedList();
          for(int i=0;i<5;i++)
          LL1.addFirst(new Integer(i+1));
          LinkedList LL2 = new LinkedList(LL1);
          LL1.clear();
          show("
List LL2 is "+LL2);
          show("List contains 2:"+LL2.contains(new
                                     Integer(2)));
          show("Index of 2 is "+LL2.indexOf(new Integer(2)));
          show("List LL2 before "+LL2);
          LL2.set(4,new Float(99.9999));
          LL2.add(3,new String ("added"));
          show("List LL2 now after add and set "+LL2);
   }
}

OUTPUT:

List LL2 is [5, 4, 3, 2, 1]
List contains 2:true
Index of 2 is 3
List LL2 before [5, 4, 3, 2, 1]
List LL2 now after add and set [5, 4, 3, added, 2, 99.9999]

Explanation: In this program, a LinkedList instance LL1 is created and five integer objects added at the beginning of the LL1. A new LinkedList instance LL2 is then created from LL1. LL1 list is cleared using clear method. The contains method is then made use of to check whether list LL2 contains 2 as object; the method returns true. Next, the index of the object 2 is displayed. The program also demonstrates the usage of set method for setting the value at specified index. Note the addLast method is equivalent to add method seen earlier. For adding element anywhere in the list, the methods add(index, object) form can be used.

18.5 ITERATING ELEMENTS OF COLLECTION

Iterating means accessing each element of the collection one by one; that is, by using an iterator, each of the element of the collection can be cycled through. The iterator() method of the Collection interface returns an Iterator. With the Iterator methods, a collection can be traversed from start to finish. The following code shows the use of the Iterator interface for a general Collection:

Collection collection = .....;
Iterator iterator = collection.iterator();
while(iterator.hasNext())
{
  Object element = iterator.next();
  System.out.println(element);
}
}

The iterator is obtained using iterator method of Collection interface. The method hasNext() returns till there is some element in the collection. The next element from the collection is obtained through next method. Afterwards any operation can be performed over the element.

The various methods of Iterator interface are shown in the Table 18.5.

Table 18.5 Methods of Iterator interface

18.5.1 The ListIterator Interface

It is an iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list. The ListIterator interface extends the Iterator interface. A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). In a list of length n, there are n + 1 valid index values, from 0 to n, inclusive.

The various methods of this interface are given in the Table 18.6.

Table 18.6 Methods of ListIterator interface

To work with iterator the three steps has to be followed:

1.   Obtain an iterator. This is done using iterator method of the collection. For example, for an instance of ArrayList AL iterator can be obtained as:

Iterator itr = AL.iterator();

2.   Use a loop that runs as long as hasNext() returns true. This is done as:

while(itr.hasNext())

3.   Inside the loop, obtain the next element using next method.

/*PROG 18.7 DEMO OF ITERATING COLLECTION VER 1*/

import java.util.*;
class JPS7
{
   public static void main(String args[])
   {
          ArrayList AL = new ArrayList();
          for (int i = 0; i < 10; i++)
             AL.add(new Integer(i + 1));
          Iterator itr = AL.iterator();
          while (itr.hasNext())
          {
                Object E = itr.next();
                System.out.print(E + " ");
          }
                System.out.println();
          }
}

OUTPUT:

1 2 3 4 5 6 7 8 9 10

Explanation: This program creates an ArrayList instance and adds 10 Integer objects to it using for loop and add method. An iterator to the collection ArrayList instance is obtained using iterator method and stored in Iterator reference itr. In the while loop, hasNext method returns true till there is an element in the ArrayList AL. The next element is obtained using next method and stored in E. The same is displayed back.

/*PROG 18.8 DEMO OF ITERATING COLLECTION VER 2*/

import java.util.*;
class JPS8
{
   public static void main(String args[])
   {
          LinkedList LL = new LinkedList();
          for (int i = 0; i < 5; i++)
          LL.add(new Float(2.5f + i));
          System.out.println("
Accessing List in forward
                              direction");
          ListIterator itr = LL.listIterator();
          while (itr.hasNext())
          {
                Object E = itr.next();
                System.out.print(E + " ");
          }
          System.out.println();
          System.out.println("
Accessing List in backward
                              direction");
          while (itr.hasPrevious())
          {
                Object E = itr.previous();
                System.out.print(E + " ");
          }
   System.out.println();
   }
}

OUTPUT:

Accessing List in forward direction
2.5 3.5 4.5 5.5 6.5
Accessing List in backward direction
6.5 5.5 4.5 3.5 2.5

Explanation: This program demonstrates ListIterator and listIterator method. An instance of LinkedList class is created and is populated with five float objects. For accessing the list in the forward direction, the simple iterating steps can be followed. Note when list is displayed in the forward direction, the iterator will be past the end of the list. Now the list can be displayed in the reverse direction. In the while loop using hasPrevious method it is checked whether any previous element is present or not. The previous element is obtained in the body of the while loop and is displayed.

/*PROG 18.9 DEMO OF ITERATING COLLECTION VER 3 */

import java.util.*;
class JPS9
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          LinkedList LL = new LinkedList();
          for (int i = 0; i < 5; i++)
          LL.add(new Float(2.5f + i));
          show("List contents: " + LL);
          show("Modifying List using iterator");
          ListIterator itr = LL.listIterator();
          while (itr.hasNext())
          {
                Object E = itr.next();
                float val = ((Float)E).floatValue();
                LL.set(LL.indexOf(E), new Float(val + 10));
          }
          show("List after modification");
          for (itr = LL.listIterator(); itr.hasNext(); )
          show(itr.next() + " ");
   }
}

OUTPUT:

List contents: [2.5, 3.5, 4.5, 5.5, 6.5]
Modifying List using iterator
List after modification
12.5
13.5
14.5
15.5
16.5

Explanation: In this program, the contents of the LinkedList instance LL are modified. For that using a listIterator and next method, each method is obtained as Object instance E of the list. Using typecasting with Float and floatValue() method of Float class, the associated float value is obtained in val. The index of the object E is obtained by using indexOf method. At this index, a new Float object is stored with val+10 as its float value. This is done by using set method.

/*DEMO OF ITERATING COLLECTION VER 4 */

import java.util.*;
class Book
{
   String bname;
   String author;
   int price;
   Book(String bn, String a, int p){
          bname = bn;
          author = a;
          price =p;
   }
   public String toString()
   {
          String s = "Name = " + bname + "	Author=" + author;
          s = s + "	Price=" + price;
          return s;
   }
}
class JPS10{
   public static void main(String args[])
   {
          LinkedList LL = new LinkedList();
          LL.add(new Book("Sea of C ","Hari Mohan ",295));
          LL.add(new Book("Sea of C++ ","Hubbured ",100));
          LL.add(new Book("Sea Of Java","H.M.Pandey ",400));

          ListIterator itr;
          System.out.println("
******Book Details
                                      ******
");
          for(itr = LL.listIterator();itr.hasNext();)
          System.out.println(itr.next()+" ");
   }
}

OUTPUT:

********Book Details *********

Name = Sea of C        Author=Hari Mohan  Price=295
Name = Sea of C++      Author=Hubbured    Price=100
Name = Sea Of Java     Author=H.M.Pandey  Price=400

Explanation: Similar to storing the objects of built-in classes, the objects of user-defined classes can be stored. In this program, a class Book has been defined which is having three members: bname, author and price. The class is having a parameterized constructor which initializes these members. The class also overrides toString method so that it can be used for displaying objects of this class as String object. In the main, the objects of Book class is added to the LinkedList instance LL using the parameterized constructor form. The objects are displayed as usual using for/while loop.

18.6 HASHSET AND TREESET CLASSES

The Collections framework provides two general-purpose implementations of the Set interface: HashSet and TreeSet. Both are discussed in turn.

18.6.1 HashSet Class

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantee as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element. More often than not, a HashSet will be used for storing the duplicate-free collection. For efficiency, objects added to a HashSet need to implement the hashCode() method in a manner that properly distributes the hash codes. While most system classes override the default hashCode() implementation in object, when creating your own classes to add to a HashSet remember to override hashCode().

The hashcode is generated by a mechanism known as hashing. In hashing, on the basis of data a key value is generated by the use of some hashing functions. This key value is known as hashcode. The hashcode is determined internally and one should have no concern with it.

The advantage of hashing is that it allows the execution time of basic operations, such as add(), contains(), remove() and size(), to remain constant even for large sets.

Commonly used constructors of this class are shown below:

1.   public HashSet()
This form of constructor creates an empty HashSet.

2.   public HashSet(Collection c)
This form of constructors creates a new set containing the elements in the specified collection c.

3.   public HashSet(int initialCapacity)

This form of constructor creates a new, empty set that has the specified initial capacity. The class defines no new method of its own. An example of usage of HashSet is given below.

/*PROG 18.11 DEMO OF HASHSET CLASS VER 1 */

import java.util.*;
class JPS11
{
   public static void main(String args[])
   {
          HashSet HS = new HashSet();
          HS.add(new Integer(1));
          HS.add(new Integer(12));
          HS.add(new Integer(13));
          HS.add(new Integer(24));
          HS.add(new Integer(50));
          HS.add(new Integer(50));
          HS.add(new Integer(24));
          System.out.println("
Contents of HashSet HS:"+HS);
   }
}

OUTPUT:

Contents of HashSet HS: [50, 1, 24, 12, 13]

Explanation: This program is simple to understand. One important thing to note here is that elements of HashSet are not ordered and duplicate elements are displayed only once.

18.6.2 TreeSet Class

This class implements the Set and SortedSet interface. As the name implies, the class uses the tree for storage of its elements. The TreeSet implementation is useful when one needs to extract elements from a collection in a sorted manner. In order to work properly, elements added to a TreeSet must be sortable. A tree knows how to keep elements of the java.lang wrapper classes sorted. It is generally faster to add elements to a HashSet, and then convert the collection to a TreeSet for sorted traversal.

The class defines the following constructors:

1.   public TreeSet()
This form of constructor creates a new empty set, sorted according to the elements' natural order. All elements inserted into the set must implement the Comparable interface. Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) must not throw a ClassCastException for any element e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint (e.g., the user attempts to add a string element to a set whose elements are integers), the add(object) call will throw a ClasscastException.

2.   public TreeSet(Collection c)
This form of constructor creates a new set containing the elements in the specified collection c, sorted according to the elements' natural order.

3.   public TreeSet(Comparator c)
This form of constructor creates a new, empty set, sorted according to the specified comparator (discussed later).

4.   public TreeSet(SortedSet s)
This form of constructor creates a new set containing the same elements as the specified sorted set, sorted according to the same ordering.

The new methods of TreeSet classes are given in the Table 18.7.

Table 18.7 Methods of TreeSet class

See few programming examples of usage of TreeSet.

/*PROG 18.12 DEMO OF TREESET CLASS VER 1*/

import java.util.*;
class JPS12
{
   public static void main(String args[])
   {
          TreeSet TS = new TreeSet();
          TS.add(new Integer(1));
          TS.add(new Integer(12));
          TS.add(new Integer(13));
          TS.add(new Integer(24));
          TS.add(new Integer(50));
          TS.add(new Integer(50));
          TS.add(new Integer(24));
          System.out.println("
Contents of TreeSet TS:"+TS);
   }
}

OUTPUT:

Contents of TreeSet TS: [1, 12, 13, 24, 50]

Explanation: This program is simple to understand. Important thing to note here is that duplicate elements are not present and elements are sorted in ascending order.

/*PROG 18.13 DEMO OF TREESET CLASS VER 2 */

import java.util.*;
class JPS13
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          TreeSet TS = new TreeSet();
          TS.add(new Integer(1));
          TS.add(new Integer(12));
          TS.add(new Integer(13));
          TS.add(new Integer(24));
          TS.add(new Integer(20));
          TS.add(new Integer(60));
          TS.add(new Integer(56));

          Iterator itr;
          show("
Elements of TS");
          for(itr = TS.iterator();itr.hasNext();)
          System.out.print(itr.next()+" ");
          show("
First element:"+TS.first());
          show("
Last element:"+TS.last());
          show("
Sub set of TS");

          SortedSet SS = TS.subSet(new Integer(12),
                         new Integer(24));
          for (itr = SS.iterator(); itr.hasNext(); )
               System.out.print(itr.next() + " ");

          show("
Head set of TS");
          SS = TS.headSet(new Integer(24));
          for(itr = SS.iterator();itr.hasNext();)
          System.out.print(itr.next()+" ");
          show("
Tail set of TS");
          SS = TS.tailSet(new Integer(24));
          for(itr = SS.iterator();itr.hasNext();)
          System.out.print(itr.next()+" ");
   }
}

OUTPUT:

Elements of TS
1 12 13 20 24 56 60
First element:1
Last element:60
Sub set of TS
12 13 20
Head set of TS
1 12 13 20
Tail set of TS
24 56 60

Explanation: This program demonstrates some of the methods of TreeSet class. After adding elements to the TreeSet instance TS, they are displayed using iterator. The first element (lowest) is returned using first() method and last() method returns the last (highest) element from the TS. The method subset returns the number of elements between the specified two arguments. The first argument is inclusive but second is not. In the output, all elements between 12 and 24 are displayed. As mentioned in the description part of this method, the set returned is part of the original set; no new set is returned. The method headSet returns all elements greater than the specified element. The method tailSet returns all elements smaller than the specified element.

/*PROG 18.14 DEMO OF TREESET CLASS VER 3*/

import java.util.*;
class JPS14
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          HashSet HS = new HashSet();
          HS.add("Hari");
          HS.add("Hemangi");
          HS.add("Varsha");
          HS.add("Malvika");
          HS.add("Deshmukh");

          show("
The HashSet elements
");
          show(HS + " ");

          TreeSet TS = new TreeSet(HS);
          show("
The TreeSet elements
");
          show(TS + " ");
   }
}

OUTPUT:

The HashSet elements
[Varsha, Deshmukh, Hemangi, Malvika, Hari]
The TreeSet elements
[Deshmukh, Hari, Hemangi, Malvika, Varsha]

Explanation: In this program, a HashSet instance HS is created and populated with some String objects. The elements of HS are then displayed. An instance TS of TreeSet is then constructed using HS as argument for the TreeSet constructor. In general programming, this is a preferred method of creating an ordered set.

18.7 WORKING WITH MAPS

A map is used to store key-value pairs, with the values retrieved using key. For each given key, there will be a corresponding value. In essence, each element of the map is stored as a (key, value) pair. Given a key, a value can be retrieved. This is the most powerful feature of map. Both key and value are objects. The keys must be unique but values may be duplicated.

The Collection Framework defines Map, Map.Entry and SortedMap interfaces to work with map.

18.7.1 The Map Interface

The Map interface is not an extension of the Collection interface. Instead, the interface starts off its own interface hierarchy for maintaining key-value associations. The interface describes a mapping from keys to values, without duplicate keys, by definition. The methods of this interface are given in the Table 18.8.

Table 18.8 Methods of Map interface

The interface methods can be broken down into three sets of operations: altering, querying and providing alternative views.

The alteration operations allow one to add and remove key-value pairs from the map. Both the key and value can be null. However, a Map should not be added to itself as a key or value.

Object put(object key, Object value)
Object remove(Object key)
void putAll(Map mapping)
void clear()

The query operations allow one to check on the contents of the map:

Object get(Object key)
boolean containskey(Object key)
boolean containsValue(Object value)
int size()
boolean isEmpty()

The last set of methods allows one to work with the group of keys or values as a collection.

public Set keySet()
public Collection values()
public Set entrySet()

Because the collection of keys in a map must be unique, a Set back is obtained. Because the collection of values in a map should not be unique, a Collection back is obtained. The last method returns a set of elements that implements the Map.Entry interface.

18.7.2 Map.Entry Interface

The entrySet() method of Map returns a collection of objects that implements the Map.Entry interface. Each object in the collection is a specific key-value pair or Map.entry object in the underlying Map. The methods of this interface are given in the Table 18.9.

Table 18.9 Methods of Map.Entry interface

Iterating through this collection, the key or value can be obtained, and the value of each entry can be changed as well. However, the set of entries becomes invalid, causing the iterator behaviour to be undefined, if the underlying Map is modified outside the setValue() method of the Map.Entry interface.

18.7.3 The SortedMap Interface

The SortedMap interface extends Map interface. It is a map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys (see the Comparable interface), or by a comparator provided at sorted map creation time. The interface provides access method to the ends of the Map as well as to subsets of the Map. Working with a SortedMap is just like a SortedSet, except the sort is done on the Map keys. The implementation class provided by the Collections Framework is a TreeMap.

The methods of this interface are given in the Table 18.10.

Table 18.10 Methods of SortedMap interface

18.8 WORKING WITH MAP CLASSES

The interfaces discussed in the previous section are implemented by the following Map classes: AbstractMap, HashMap, TreeMap and WeakHashMap. All these classes are discussed below.

1. AbstractMap class
This class provides a skeletal implementation of the Map interface, to minimize the efforts required to implement this interface. The AbstractMap class is the base class for all the other three classes.

2. HashMap and TreeMap classes
The Collection Framework provides two general-purpose Map implementations: HashMap and TreeMap. As with all the concrete implementations, which implementation is being used depends on the specific needs. For inserting, deleting and locating elements in a Map, the HashMap offers the best alternative. If, however, the keys need to be traversed in a sorted order TreeMap is the better alternatives. Depending on the size of the collection, it may be faster to add elements to a HashMap convert the map to a TreeMap for sorted key traversal. Using a HashMap requires that the class of key added have a well-defined hashCode() implementation. With the TreeMap implementation, elements added to the map must be sortable.

The base class of HashMap class is the AbstractMap class and it implements Serializable, Cloneable and Map interface.

The class HashMap defines following constructor:

1.   public HashMap()
This form of constructor creates an empty HashMap with the default initial capacity (17) and the default load factor (0.75).

2.   public HashMap(Map m)
This form of constructor creates a new HashMap with the same mappings as the specified Map. The HashMap is created with default load factor (0.75) and an initial capacity sufficient to hold the mappings in the specified Map.

3.   public HashMap(int initialCapacity)
This form of constructor creates an empty HashMap with the specified initial capacity and the default load factor (0.75).

4.   public hashMap(int initialCapacity, float loadFactor)
This form of constructor creates an empty HashMap with the specified initial capacity and load factor.

Similar to a HashSet, a HashMap does not store its elements in sorted order.

/*PROG 18.15 DEMO OF HASHMAP CLASS VER 1 */

import java.util.*;
class JPS15
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          HashMap HM = new HashMap();
          HM.put("Hari Mohan", new Integer(101));
          HM.put("Man Mohan ", new Integer(102));
          HM.put("Ranjana ", new Integer(103));
          HM.put("Anjana ", new Integer(104));
          Set s = HM.entrySet();
          show("The elements of the Map are 
");
          Iterator itr = s.iterator();
          show("KEY 		 VALUES");
          while (itr.hasNext())
          {
                Map.Entry me = (Map.Entry)itr.next();
                show(me.getKey() + "	" + me.getValue());
          }
   }
}

OUTPUT:

The elements of the Map are
KEY              VALUES
Hari Mohan       101
Anjana           104
Ranjana          103
Man Mohan        102

Explanation: This program creates an instance of HashMap and using put method puts the key and values into the map instance HM. The values are the String objects, that is, names and keys are points obtained during a game. The collection of all the map entries as a Set is returned using entrySet method. As stated earlier in the description of methods, each entry of this set is an object of type Map.Entry. Next elements of set s are displayed using an iterator itr. The while loop runs till there is an element in the set s. The reference of the object returned through next method is typecasted by Map.Entry interface and stored in me of type Map.Entry. Then using getValue and getKey methods of Map.Entry interface the elements are displayed.

/*PROG 18.16 DEMO OF HASHMAP CLASS VER 2 */

import java.util.*;
class JPS16
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          HashMap HM = new HashMap();
          HM.put(" Hari Mohan", new Integer(101));
          HM.put(" Man Mohan ", new Integer(102));
          HM.put(" Ranjana ", new Integer(103));
          HM.put(" Anajana ", new Integer(104));

          Set s = HM.keySet();
          Iterator itr;
          show("
 Keys of Map
");
          for (itr = s.iterator(); itr.hasNext(); )
               show(itr.next() + " ");
          Collection C = HM.values();

          show("
 Values of Map
");
          for (itr = C.iterator(); itr.hasNext(); )
               show(itr.next() + " ");
   }
}

OUTPUT:

Keys of Map
Hari Mohan
Ranjana
Man Mohan
Anajana
Values of Map

101
103
102
104

Explanation: The elements of HashMap HM are the same as in the previous program. Here keys and values are obtained separately using the keySet and values method, respectively. The keySet method returns all the keys as a set. These are then displayed using an iterator to the set s. The values method returns a reference of Collection type. This is stored in C and then displayed using iterator values.

3. The TreeMap class

The base class of the TreeMap is the AbstractMap class and it implements SortedMap, Cloneable and Serializable interface. This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class. This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

The class defines the following constructors:

1.   public TreeMap()
This form of constructor creates a new, empty map, sorted according to the key's natural order. All keys inserted into the map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any elements k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint (e.g., the user attempts to put a string key into a map whose keys are integers), the put (Object key, Object value) call will throw a ClassCastException.

2.   public TreeMap(Comparator c)
This form of constructor creates a new empty map, sorted according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator: comparator. compare(k1,k2) must not throw a ClassCastException for any keys k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint, the put(Object key, Object value) call will throw a ClassCastException.

3.   public TreeMap(Map m)
This form of constructor creates a new map containing the same mappings as the given map, sorted according to the key's natural order.

4.   public TreeMap(SortedMap m)
This form of constructor creates a new map containing the same mappings as the given SortedMap, sorted according to the same ordering.

/*PROG 18.17 DEMO OF TREEMAP CLASS VER 1 */

import java.util.*;
class JPS17
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          TreeMap TM = new TreeMap();
          TM.put("CS02", "Hari");
          TM.put("CS01", "Man");
          TM.put("CS04", "Ranjana");
          TM.put("CS03", "Anjana");

          Set s = TM.entrySet();
          show("
The elements of the Map are 
");
          Iterator itr = s.iterator();
          show("KEY	 VALUES");
          while (itr.hasNext())
          {
                Map.Entry me = (Map.Entry)itr.next();
                show(me.getKey() + "	" + me.getValue());
          }
   }
}

OUTPUT:

The elements of the Map are

KEY       VALUES
CS01      Man
CS02      Hari
CS03      Anjana
CS04      Ranjana

Explanation: This program is similar to the earlier programs of HashMap. Note that output of the program is in sorted order.

/*PROG 18.18 DEMO OF TREEMAP CLASS VER 2*/

import java.util.*;
class JPS18
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          TreeMap TM = new TreeMap();
          for(int i=101;i<105;i++)
          TM.put(new Integer(i), new Integer(100));

          Set s = TM.entrySet();
          Iterator itr = s.iterator();
          Map.Entry me = (Map.Entry)itr.next();
          me.setValue(new Integer(95));
          Object obj = TM.get(new Integer(101));
          show("
Value is "+obj);

          boolean k = TM.containsKey(new Integer(106));
          boolean v = TM.containsKey(new Integer(100));

          show("
k = "+k+"	v= "+v);
          TM.remove(new Integer(101));
          show("
Size of TreeMap instance TM is
                 "+TM.size());
   }
}

OUTPUT:

Value is 95
k = false v= false
Size of TreeMap instance TM is 3

Explanation: This program shows some of the methods of TreeMap class. Initially some elements are put in the TreeMap instance TM. Both key and value are Integer objects. Assume key is the roll number and values are marks; the first element of the TM is obtained using iterator. Its values are changed using setValue method of Map.Entry interface. The same value is then obtained using get method. The method containsKey and containsValue checks whether a key and value supplied as argument are within the map. If they are within the map, the method returns true else, returns false. The remove method removes the given object from the map and size method gives number of elements in the map.

/*PROG 18.19 DEMO OF TREEMAP CLASS VER 3 */

import java.util.*;
class JPS19
{
static void show(String s)
{
   System.out.println(s);
   }
          public static void main(String args[])
   {
          TreeMap TM = new TreeMap();
          TM.put(new Integer(101), new Double(34.56));
          TM.put(new Integer(102), new Double(44.56));
          TM.put(new Integer(105), new Double(35.77));
          TM.put(new Integer(106), new Double(45.78));
          TM.put(new Integer(104), new Double(30.59));
          TM.put(new Integer(107), new Double(28.75));
          TM.put(new Integer(103), new Double(25.90));

          show("
First key:" + TM.firstKey());
          show("Last key:" + TM.lastKey());

          SortedMap SM = TM.headMap(new Integer(104));
          Iterator itr;
          Set s = SM.entrySet();

          show("
KEY	VALUES for key <104");
          for (itr = s.iterator(); itr.hasNext(); )
          {

                Map.Entry me = (Map.Entry)itr.next();
                show(me.getKey() + "	" + me.getValue());
          }
          SM = TM.tailMap(new Integer(104));
          s = SM.entrySet();
          show("
KEY	VALUES for key >104");
          for (itr = s.iterator(); itr.hasNext(); )
          {

                Map.Entry me = (Map.Entry)itr.next();
                show(me.getKey() + "	" + me.getValue());
          }
   }
}

OUTPUT:

First key:101
Last key:107

KEY       VALUES for key <104
101       34.56
102       44.56
103       25.9

KEY       VALUES for key >104
104       30.59
105       35.77
106       45.78
107       28.75

Explanation: This program shows few methods of SortedMap interface. The firstKey and lastKey method returns the first and last key of the specified map. The headMap returns a map where all the keys of map entries are less than the specified key. The tailMap does the reverse of headMap.

18.9 THE COMPARATOR INTERFACE

The Comparator interface is a type of comparison function, which imposes a total ordering on some collection of objects. By default, Java uses the natural ordering of the elements for the comparison purpose, that is, 8 comes before 9, C comes before D and so on. The natural order can be altered for comparison purpose. Comparators can be passed to a sort method to allow precise control over the sort order. Comparator can also be used to control the order of certain data structures (such as TreeSet or TreeMap). The interface defines two methods: compare and equals.

The signature of compare method is given as:

int compare(Object O1, Object O2)

The method compares its two arguments for order. It returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. The method can throw a ClassCasrException if the types of the objects are not compatible for comparison. Overriding compare method lets one alter the natural ordering, for example, printing elements in reverse order.

The signature of equals method is given as:

boolean equals(Object Obj)

The method indicates whether some other object is "equal to" this Comparators. If it is, it returns true else, returns false. This method can return true only if the specified Object is also a comparator and it imposes the same ordering as this comparator. This method is usually not overridden.

The following example helps to better understand the usage of Comparator interface.

/*PROG 18.20 DEMO OF COMPARATOR INTERFACE VER 1 */

import java.util.*;
class MyComp implements Comparator
{
   public int compare(Object a, Object b)
   {
          Integer ia, ib;
          ia = (Integer)a;
          ib = (Integer)b;
          return ib.compareTo(ia);
   }
}
class JPS20
{
   public static void main(String args[])
   {
          TreeSet TS = new TreeSet(new MyComp());
          TS.add(new Integer(10));
          TS.add(new Integer(18));
          TS.add(new Integer(105));
          TS.add(new Integer(210));
          TS.add(new Integer(149));
          TS.add(new Integer(330));
          TS.add(new Integer(75));

          System.out.println("
The sorted elements are
");
          Iterator itr;
          for (itr = TS.iterator(); itr.hasNext(); )
                 System.out.print(itr.next() + " ");
          System.out.println();
   }
}

OUTPUT:

The sorted elements are
330 210 149 105 75 18 10

Explanation: To make use of Comparator, a class must be created and Comparator interface implemented. In this program, a class MyComp is created that implements Comparator interface. In the class, the compare method is overridden. The default compare method uses compareTo method for comparison of two objects. As stated earlier, the default method uses natural ordering. But in this program, the ordering for comparing of two Integer objects is reversed. Note in the default form first object calls the compareTo method and passes second object as argument but in this case the order is reversed. Furthermore, depending on the type of object the compare method typecasting has to be done. Here the Object is typecasted to Integer.

In the main, when creating an instance of TreeSet, in the constructor an object of MyComp class is passed. This causes to use own comparator for comparison purpose. Note the output is in reverse order and the default order is ascending.

/*PROG 18.21 DEMO OF COMPARATOR INTERFACE VER 2 */

import java.util.*;
class MyComp implements Comparator
{
   public int compare(Object a, Object b)
   {
          String ia, ib;
          ia = ((String)a).toLowerCase();
          ib = ((String)b).toLowerCase();
          return ib.compareTo(ia);
   }
}
class JPS21
{
   public static void main(String args[])
   {
          TreeSet TS = new TreeSet(new MyComp());
          TS.add("Hari");
          TS.add("Vijay");
          TS.add("Madhuri");
          TS.add("Man");
          TS.add("Vikas");
          System.out.println("
Sorted names are
");

          Iterator itr;
          for (itr = TS.iterator(); itr.hasNext(); )
                System.out.print(itr.next() + " ");
          System.out.println();
   }
}

OUTPUT:

Sorted names are
Vikas Vijay Man Madhuri Hari

Explanation: In this program, the compare method is overridden so two String objects are compared irrespective of their case, that is, 'Hari' and 'hari' will be treated as same. For that, both the strings are converted to lower case and compareTo method is applied. Note the output without using own comparator will be:

Vikas Vijay Man Madhuri Hari

/*PROG 18.22 DEMO OF COMPARATOR INTERFACE 3 */

import java.util.*;
class MyComp implements Comparator
{
   public int compare(Object a, Object b)
   {
          Integer ia, ib;
          ia = (Integer)a;
          ib = (Integer)b;
          return ib.compareTo(ia);
   }
}
class JPS22
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          TreeMap TM = new TreeMap(new MyComp());
          TM.put(new Integer(101), "Hari");
          TM.put(new Integer(104), "Man");
          TM.put(new Integer(210), "Ravi");
          TM.put(new Integer(150), "Vijay");
          TM.put(new Integer(340), "Hemangi");

          Iterator itr;
          Set S = TM.entrySet();
          show("
KEY	VALUES");
          for (itr = S.iterator(); itr.hasNext(); )
          {
                Map.Entry me = (Map.Entry)itr.next();
                show(me.getKey() + "	" + me.getValue());
          }
          show(" ");
      }
}

OUTPUT:

KEY          VALUES
340          Hemangi
210          Ravi
150          Vijay
104          Man
101          Hari

Explanation: This program is similar to the previous one but in this case a comparator for the TreeMap instance is written. The default comparator does the sorting on the basis of natural ordering but the natural ordering is reversed. This is quite clear from the output of the program.

18.10 HISTORICAL COLLECTION CLASSES

The historical collection classes are those classes supplied with the earlier version of Java. Though the Collection Framework provides a number of classes which can be used in different programming situations, at times one still needs to use some of the original collections capabilities. This section reviews some of the capabilities of working with arrays, vectors, hashtables, enumerations and other historical capabilities.

1. The Enumeration interface
The Enumeration interface allows one to iterate through all the elements of a collection. In the Collection Framework, this interface has been superseded by the Iterator interface. However, not all libraries support the newer interface, so Enumeration may have to be used from time to time.

An object that implements the Enumeration interface generates a series of elements, one at a time. Successive calls to the nextElement method return successive elements of the series.

For example, to print all elements of a vector V the following can be written :

for(Enumeration e = V.element();e.hasMoreElements();)
   System.out.println(e.nextElement());

The interface defines only two methods:

1.   boolean hasMoreElements()
The method tests if this enumeration contains more elements. It returns true if enumeration contains more elements else, false.

2.   Object nextElement()
The method returns the next element of this enumeration if this enumeration object has at least one more element to provide.

2. The Vector class
The vector class implements a growable array of objects, but can store heterogeneous data elements. Like an array, it contains components that can be accessed using an integer index. However, the size of a vector can grow or shrink as needed to accommodate adding and removing items after the vector has been created. With the Java 2 SDK, version 2, the Vector class has been retrofitted into the Collections Framework hierarchy to implement the List interface.

When transitioning from Vector to ArrayList, one key difference is that the arguments have been reversed to positionally change an element's value:

(i)  From original Vector class void setElementAt(Object element, int index)

(ii) From List interface void set(int index, Object element)

One more difference to note is that Vector is synchronized but ArrayList is not.

Each vector tries to optimize storage management by maintaining a capacity and a capacityIncrement. The capacity is always at least as large as the vector size; it is usually large because as components are added to the vector, the vector's storage increases in chunks the size of capacityIncrement. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation.

The Vector class defines the following constructors:

1.   public Vector()
This form of constructor creates an empty vector so that its internal data array has size 10 and its standard capacity increment is zero.

2.   public Vector(int initialCapacity
This form of constructor creates an empty vector with the specified initial capacity and with its capacity increment equal to zero.

3.   public Vector(int initialCapacity, int CapacityIncrement)
This form of constructor creates an empty vector with the specified initial capacity and capacity increment.

4.   public Vector(Collection c)
This form of constructor creates a vector containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Apart from the above four constructors, the Vector class defines the following data members. Table 18.11

protected int capacityIncrement
It is the amount by which the capacity of the vector is automatically incremented when its size becomes greater than its capacity. If the capacity increment is less than or equal to zero, the capacity of the vector is doubled each time it needs to grow.

protected Object[]elementData
It is the array buffer into which the components of the vector are stored. The capacity of the vector is the length of this array buffer, and is at least large enough to contain all the vector's elements. Any array elements following the last element in the Vector are null.

protected int elementCount
It is the number of valid components in this Vector object. Components elementData[0] through elementData[elementCount-1] are the actual items.

Table 18.11 Methods of Vector class

/*PROG 18.23 DEMO OF VECTOR CLASS VER 1 */

import java.util.*;
class JPS23{
   static void show(String s){
          System.out.println(s);
   }
   public static void main(String args[])
   {
          Vector V = new Vector();
          show("
Vector size := " + V.size());
          show("Vector capacity := " + V.capacity());

          V.addElement(new Integer(12));
          V.addElement("Vector_Demo");
          V.addElement(new Double(14.54));
          V.addElement(new Boolean(true));
          V.addElement("Element");
          V.addElement(new Character('V'));

          show("
First Element := " + V.firstElement());
          show("Last Element := " + V.lastElement());

          show("Vector size now := " + V.size());
          show("Vector Capacity now := " + V.capacity());

          Enumeration E;
          show("
Elements of Vector V");
          for (E = V.elements(); E.hasMoreElements(); )
                   show(E.nextElement() + " ");
          show(" ");
   }
}

OUTPUT:

Vector size            := 0
Vector capacity        := 10
First Element          := 12
Last Element           := V
Vector size now        := 6
Vector Capacity now    := 10
Elements of Vector V
12
Vector_Demo
14.54
true
Element
V

Explanation: This program creates an instance V of the Vector class. The initial size and capacity of the V is 0 and 10, respectively. Elements are added to the V. using addElement method. The method firstElement and lastElement returns the first and last element of the vector V.

For listing all the elements Enumeration is used. A reference E of this interface is created and initialized to V.elements() that returns a reference to Enumeration type. Till the vector V has got more elements (which is checked using method hasMoreElements) these elements are displayed using nextElement() method. This is similar to iterating all the elements of a collection using iterator interface and iterator method.

/*PROG 18.24 DEMO OF VECTOR CLASS VER 2 */

import java.util.*;
class JPS24
{
   static void show(String s)
   {
          System.out.print(s);
   }
   public static void main(String args[])
   {
          Vector V = new Vector(10);
          for(int i =1; i<=5;i++)
          V.addElement(new Integer(i));
          V.addElement("Joy");
          V.addElement("Fun");
          V.addElement("cool");
          V.addElement("Laugh");
          show("
Vector size: "+V.size()+"
");
          show("
Vector capacity: "+V.capacity()+"
");
          Object obj[] = new Object[V.size()];
          V.copyInto(obj);
          show("
Contents of array
");
          for(int i = 0;i<obj.length;i++)
          show(obj[i]+ " " );

          show("
V contains "cool":"
                 +V.contains("cool")+"
");
          show("
Elements at location 6 is "
                 +V.elementAt(6)+"
");

          V.removeElementAt(2);
          V.remove(new Integer(1));
          V.remove("cool");
          V.insertElementAt("Added",2);

          obj = new Object[V.size()];
          V.copyInto(obj);
          show("
Contents of array now
");
          for(int i=0;i<obj.length;i++)
          show(obj[i]+" ");
          show("
");

          V.removeAllElements();
          show("
After removing all elements 
");
          show("V.isEmpty() returns :"+V.isEmpty()+"
");
   }

}

OUTPUT:

Vector size: 9
Vector capacity: 10
Contents of array
1 2 3 4 5 Joy Fun cool Laugh
V contains "cool": true

Elements at location 6 is Fun

Contents of array now
2 4 Added 5 Joy Fun Laugh

After removing all elements
V.isEmpty() returns :true

Explanation: This program makes use of various methods of Vector class. For copying a vector into an Object array copyInto method can be used. In this program, first an Object array of vector size is created, then copyInto method is used for copying all elements into Object array obj. The contains method checks whether specified element is in the vector or not. The elementAt method returns the element at the specified location. The remove method removes the specified object from the vector and removeElementAt removes object at the specified location. The insertElementAt inserts the element at the specified location. The removeAllElements is equivalent to clear method which removes all the elements from the vector. The method isEmpty returns true if the vector is empty.

3. The Stack class
The stack class represents a last-in-first-out (LIFO) stack of objects. It extends Vector class with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top. They are shown in the Table 18.12.

Table 18.12 Methods of Stack class

When a stack is first created, it contains no items.

An EmptyStackException is thrown if pop() is called when the invoking stack is empty.

Because the Stack class extends the Vector class, a Stack can still be accessed or modified with the inherited Vector methods.

/*PROG 18.25 DEMO OF STACK CLASS VER 1 */

import java.util.*;
class JPS25
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          Stack S = new Stack();
          S.push(new Integer(5));
          S.push(new Integer(7));
          S.push(new Integer(3));

          show("
Stack contents");
          show(S + " ");
          show("
First item popped: " + S.pop());

          S.push("Two");
          S.push("One");
          S.push("Zero");
          show("
After adding some elements");
          show("Stack contents
");
          show(S + " ");

          show("
First item popped:" + S.pop());
          show("
First item peeked:" + S.peek());

          show("
Stack contents");
          show(S + " ");
          int pos = S.search(new Integer(6));
          if (pos != -1)
                 show("
From top offset of 6 is:" + pos);
          else
                 show("
Element is not in stack");
   }
}

OUTPUT:

Stack contents
[5, 7, 3]
First item popped: 3

After adding some elements
Stack contents

[5, 7, Two, One, Zero]

First item popped: Zero
First item peeked: One
Stack contents
[5, 7, Two, One]
Element is not in stack

Explanation: In this program, Stack instance S is created. In the beginning, some Integer objects are pushed and then the contents of the Stack instance S displayed. The top element is then popped from the stack. Further elements are added to the Stack S and then first item is popped. Next first item is only peeked and displayed. The Integer object 6 is searched in the Stack S using search method. The method returns the offset of the element from the top in case the element exists in the Stack S else, it returns -1.

4. The Dictionary class
The dictionary class is the abstract parent of any class, such as HashTable, which maps keys to values. Every key and every value is an object. In any one Dictionary object, every key is associated with at most one value. Given a Dictionary and a key, the associated element can be looked up. Thus, like a map, a dictionary can be considered as a list of key-value pairs. Any non-null object can be used as a key and as a value. The Dictionary class is completely full of abstract methods. In other words, it should have been an interface. It forms the basis for a key-value pair collections in the historical collection classes, with its replacement being Map in the new framework. The class is now obsolete so it will not be discussed in detail.

5. The HashTable class
This class implements a hashTable, which maps keys to values. Any non-null object can be used as a key or as a value. The Hashtable implementation is a generic dictionary that permits storing any object as its key or value (besides null). With the Java 2 SDK, version 1.2, the class has been reworked into the Collections Framework to implement the Map interface. So the original HashTable methods or the newer Map method can be used. For a synchronized Map, using Hashtable is slightly faster than using a synchronized HashMap.

In Hashtable, hashing is applied onto the key and a hash code is returned. The hash code is used as the index at which the value is stored within the table. To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method. Fortunately, many of Java's built-in classes already implement the hashCode() method. For example, the most common type of Hashtable uses a String object as the key. String implements both hashCode() and equals().

The Hashtable class defines the following constructors:

1.   public Hashtable()
This form of constructor creates a new, empty hashtable with a default initial capacity(11) and load factor, which is 0.75.

2.   public Hashtable(int intialCapacity)
This form of constructor creates a new, empty hashtable with the specified initial capacity and default load factor, which is 0.75.

3.   public Hashtable(int initialCapacity, float loadFactor)
This form of constructor creates a new, empty hashtable with the specified initial capacity and the specified load factor.

4.   public Hashtable(Map t)
This form of constructor creates a new hashtable with the same mappings as the given Map. The hashtable is created with an initial capacity sufficient to hold the mappings in the given Map and a default load factor, which is 0.75.

The historical methods of the HashTable class are shown in the Table 18.13.

Table 18.13 Methods of Hashtable class

/*PROG 18.26 DEMO OF HASHTABLE CLASS VER 1 */

import java.util.*;
class JPS26
{
   public static void main(String args[])
   {
          Hashtable HT = new Hashtable();
          HT.put(new Integer(101), "Hari");
          HT.put(new Integer(104), "Man");
          HT.put(new Integer(310), "Hemangi");
          HT.put(new Integer(140), "Ruchika");
          HT.put(new Integer(320), "Veeneta");

          Enumeration E;
          System.out.println("
KEYS	VALUES");
          for (E = HT.keys(); E.hasMoreElements(); )
          {
                 Object obj = E.nextElement();
                 System.out.println(obj + "	" + HT.get(obj));
          }
   }
}

OUTPUT:

KEYS         VALUES
140          Ruchika
104          Man
310          Hemangi
101          Hari
320          Veeneta

Explanation: An Enumeration for the keys is obtained using keys method of Hashtable. For each key the corresponding value is obtained using get method. Rest is simple to understand.

/*PROG 18.27 DEMO OF HASHTABLE CLASS VER 2 */

import java.util.*;
class JPS27
{
   static void show(String s){
          System.out.println(s);
   }
   public static void main(String args[])
   {
          Hashtable HT = new Hashtable();

          HT.put(new Integer(101), "Hari");
          HT.put(new Integer(104), "Ranjana");
          HT.put(new Integer(210), "Anjana");
          HT.put(new Integer(140), "Vijay");
          HT.put(new Integer(310), "Madhuri");

          Iterator itr;
          System.out.println("
KEYS	VALUES");
          Set S = HT.entrySet();
          for (itr = S.iterator(); itr.hasNext(); )
          {
                Map.Entry me = (Map.Entry)itr.next();
                show(me.getKey() + "	" + me.getValue());
          }
   }
}

OUTPUT:

KEYS       VALUES
140        Vijay
104        Ranjana
310        Madhuri
101        Hari
210        Anjana

Explanation: As the class implements the Map interface the set-view of the Hashtable can be obtained using the entrySet method of the Map interface. Once obtained, then using iterator and MapEntry interface all the keys and values of the Hashtable can be displayed. One more method using the keySet method and iterator is given as:

Iterator itr;
System.out.println("
KEYS	VALUES");
Set S = HT.entrySet();
for (itr = S.iterator(); itr.hasNext(); )
{
 Object obj = itr.next();
 System.out.println(obj+ "	"+HT.get(obj));
}

Here using the keySet method a set of keys is obtained, and using Iterator and get method all the elements are displayed.

6. The Properties class
The Properties implementation is a specialized Hashtable for working with text strings. While values retrieved from a Hashtable have to be cast, the Properties class allows to get text values without casting. In Properties the key is a String and the value is also a String. The class also supports loading and saving property settings from an input stream or to an output stream.

The most commonly used set of properties is the system properties list, retrieved by

System.getProperties()

The class defines the following constructors:

1.   public Properties()
This form of constructor creates an empty property list with no default values.

2.   public Properties(Properties defaults)
This form of constructor creates an empty property list with the specified defaults.

Apart from the above two constructors, the class defines one protected member defaults whose declaration is given as:

protected Properties defaults

It is a property list that contains default values for any keys not found in this property list.

The various methods of Properties class are given in the Table 18.14.

Table 18.14 Methods of Properties class

Following is a small example of Properties class.

/*PROG 18.28 DEMO OF PROPERTIES CLASS VER 1*/

import java.util.*;
class JPS28
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          Properties P = new Properties();
          P.put("LINUX","OS1");
          P.put("UNIX", "OS2");
          P.put("Java", "Prog.Lanugage");
          P.put("DDK", "System Software");
          Iterator itr;
          System.out.println("
KEYS		VALUES");
          Set S = P.keySet();
          for (itr = S.iterator(); itr.hasNext(); )
          {
          String obj = (String)itr.next();
          System.out.println(obj+"		"+P. getProperty(obj));
          }
   }
}

OUTPUT:

KEYS         VALUES
Java         Prog.Lanugage
LINUX        OS1
UNIX         OS2
DDK          System Software

Explanation: This program is simple to understand. In this program, keys have been used as some computer system tools and values are their brief description. Using keySet method the set-view of the keys is taken and stored in the Set instance S. Then using iterator and for loop each key in turn is extracted using next method and the corresponding value is obtained using getProperty method of Properties class.

/*PROG 18.29 DEMO OF PROPERTIES CLASS VER 2 */

import java.util.*;
class JPS29
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          Properties def = new Properties();
          def.put("XYZ", "don't know");
          Properties P = new Properties(def);

          P.put("LINUX", "OS");
          P.put("Java", "Prog.Language");

          show(P.getProperty("LINUX"));
          show(P.getProperty("XYZ"));

          String temp = P.getProperty("pqr", "What is this");
          show(temp);
   }
}

OUTPUT:

OS
don't know
What is this

Explanation: When a value is not associated with any of the key specified then a default value can be set for a Properties instance. There are two methods to do this. In the first method, default values can be stored for a Properties instance and the instance is passed as a parameter when creating new Properties instance. This is shown in the program. A Properties instance def is created and just one key 'xyz' with value 'don't know' is stored in it. This def is passed as an argument to the Properties constructor when creating Properties instance P. Now when line

show(P.getProperty("xyz"));

executes, JVM looks for a value associated with 'xyz'. As there is no key named 'xyz' in the P, default Properties instance def is searched. There key 'xyz' is found and value is returned.

The second method is to use getProperty method but with two String arguments. First argument is the key and second is its default value. In this program, the key 'pqr' is not found in P, so its default value 'What's this' is returned.

/*PROG 18.30 DEMO OF PROPERTIES CLASS VER 3 */

import java.util.*;
import java.io.*;
class JPS30
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
          {
             try
          {
                 String name, mnum;
                 Properties P = new Properties();
                 FileOutputStream fout = null;
                 Scanner sc = new Scanner(System.in);
                 fout = new FileOutputStream("mbook.txt");
                 while(true)
                 {
                       show("Enter the name");
                       name = sc.next();
                       if (name.equals("exit") == true)
                              break;
                       show("Enter the mobile number");
                       mnum = sc.next();
                       P.put(name, mnum);
                 }
                    P.store(fout, "Mobile Book");
                    fout.close();
                 }
                 catch (Exception e)
                 {
                 System.out.println("Error in file handling");
          }
   }
}

OUTPUT:

Enter the name
H.M.Pandey
Enter the mobile number
9923598540

Enter the name
Lala
Enter the mobile number
9423347619

Enter the name
exit

Explanation: The store method of the Properties class can be used to store the contents of the Properties instance to a file. The program is having a Properties instance P in which name and mobile number of few persons are stored. Both the name and mobile number are taken from console. After storing few entries into the Properties instance all entries of P are written to the file 'mbook.txt' which is opened earlier using FileOutputStream. The second argument in the store method is a String object. It is like giving description of the file.

The store method writes this property list (key and element pairs) in this Properties table to the output stream in a format suitable for loading into a Properties table using the load method. If the second argument is not null, an ASCII# character, the string (second argument), and a line separator are first written to the output stream. Next, a comment line is always written, consisting of an ASCII# character, the current date and time and a line separator. Then every entry in this Properties table is written out, one per line. For each entry the key string is written, then an ASCII =, then the associated element string.

#Mobile Book
#Sat Jan 10 17:02:24 PST 2009
H.M.Pandey=9923598540
Lala=9423347619

/*PROG 18.31 DEMO OF PROPERTIES CLASS VER 4 */

import java.io.*;
import java.util.*;
class JPS31
{
   public static void main(String args[])
   {
          try
          {

            Properties P = new Properties();
            FileInputStream fin = null;
            fin = new FileInputStream("mbook.txt");
            if (fin != null)
              {
                P.load(fin);
                Iterator itr;
                System.out.println("
Contact details are");
                System.out.println("
NAME		MOBILE NO.");
                Set S = P.keySet();
                for (itr = S.iterator(); itr.hasNext(); )
              {
                String obj = (String)itr.next();
                System.out.println(obj+"		"+P.
                 getProperty(obj));
              }
   }
   fin.close();
   }
     catch (Exception e)
     {
          System.out.println("Error in file handling ");
     }
   }
}

OUTPUT:

Contact details are
NAME       MOBILE NO.
Hari       9923598540
Man        9745659019
Lala       9423347619
Ritu       9923781210

Explanation: In this program, the load method of Properties class is used for loading of entries from the file into an instance of Properties class. Here the file 'mbook.txt' is first opened using FileInputStream class. If the file successfully opened, the entries are to be loaded into P using load method. Once loaded, reset of the code simply displays the name and mobile numbers of the person. This has been explained earlier.

18.11 ALGORITHM SUPPORT

The Collection class available as part of the Collection Framework, provides support for various algorithms with the collection classes, both new and old. This class exclusively consists of static methods that operate on or returns collections. It contains polymorphic algorithms that operate on collections, 'wrappers', which returns a new collection backed by a specified collection and a few others. The methods of this class all throws a NullPointerException if the collection or class objects provided to them are null. One more execution, UnsupportedOperationException, occurs when an attempt is made to modify an unmodified collection.

The various methods of this class are shown in the Table 18.15.

Table 18.15 Algorithms supported by Collection framework

All the methods which start with synchronized are thread-safe methods. Recall the Collections framework does not provide any synchronized collections. Using the synchronized method the synchronization can be achieved among multiple threads accessing the collections. It is imperative that the user manually synchronize on the returned collection when iterating over it, that is, while iterating a collection it must be written inside a synchronized block.

All the methods which start with unmodifiable return immutable collections, that is, they cannot be modified once created.

Apart from the above methods, the class Collections provides three static fields:

(i)   public static final List EMPTY_LIST
The EMPTY_LIST represents the empty list (immutable).

(ii)  public static final Set EMPTY_SET
The EMPTY_SET represents the empty set (immutable).

(iii) public static final Set EMPTY_MAP
The EMPTY_MAP represents the empty map (immutable).

The following programs make use of these methods:

/*PROG 18.32 DEMO OF FEW ALGORITHMS OF COLLECTION VER 1 */

import java.util.*;
import java.io.*;
class JPS32
{
   static void show(String s)
   {
          System.out.print(s);
   }
   public static void main(String args[])
   {
          ArrayList AL = new ArrayList();
          AL.add(new Integer(20));
          AL.add(new Integer(35));
          AL.add(new Integer(5));
          AL.add(new Integer(135));
          AL.add(new Integer(467));
          AL.add(new Integer(8));

          show("
Min element of list:"
                 + Collections.min(AL) + "
");
          show("
Max element of list:"
                 + Collections.max(AL) + "
");

          Collections.sort(AL);

          Iterator itr;

          show("
List in sorted order

");
          for (itr = AL.iterator(); itr.hasNext(); )
                 show(itr.next() + " ");
          show("
");
          Collections.reverse(AL);
          show("
List in reverse order

");
          for (itr = AL.iterator(); itr.hasNext(); )
                 show(itr.next() + " ");
          show("
");
          Collections.shuffle(AL);
          show("
List after shuffling

");
          for (itr = AL.iterator(); itr.hasNext(); )
                 show(itr.next() + " ");
          show("
");

          Collections.fill(AL, "Filled");
          show("
List after fill 

");
          for (itr = AL.iterator(); itr.hasNext(); )
                 show(itr.next() + " ");
          show("
");
   }
}

OUTPUT:

Min element of list: 5
Max element of list: 467
List in sorted order
5 8 20 35 135 467
List in reverse order
467 135 35 20 8 5
List after shuffling
8 35 467 20 135 5
List after fill
Filled Filled Filled Filled Filled Filled

Explanation: This program is simple to understand. Simply observe how various Collections methods are used.

/*PROG 18.33 DEMO OF FEW ALGORITHMS OF COLLECTION VER 2 */

import java.io.*;
import java.util.*;
class JPS33
{
   static void show(String s)
   {
          System.out.print(s);
   }
   public static void main(String args[])
   {
          List LL =Collections.nCopies(5,new Integer(10));
          //LL.set(0, new Integer(20));line generates error;
          List UML = Collections.unmodifiableList(LL);
          //LL.set(2, "Changed");line generates error;
          Comparator cm = Collections.reverseOrder();
          LinkedList LL1 = new LinkedList();

          LL1.add(0, "one");
          LL1.add(1, "two");
          LL1.add(2, "three");
          LL1.add(3, "four");

          Collections.sort(LL1, cm);
          Iterator itr;

          show("
List in reverse sorted order using
                 comparator
");

          for (itr = LL1.iterator(); itr.hasNext(); )
          show(itr.next() + " ");
          show("
");

          Collections.fill(LL1, new Integer(5));
          int freq = Collections.frequency(LL1, new
                 Integer(5));
          show("
Frequency of Integer object 5 is:"
                 +freq"
");
   }
}

OUTPUT:

List in reverse sorted order using comparator
two three one four
Frequency of Integer object 5 is: 4

Explanation: The method nCopies returns an immutable list after filling the list with 5 integer objects of value 10 each. Note the list cannot be modified so the line in comment generates run time error. Similarly, the method unmodifiableList creates an immutable list that cannot be modified.

The method reverseOrder returns a comparator that is sorted in cm. This cm is used for sorting the contents of list LL1 in reverse order.

/*PROG 18.34 DEMO OF FEW CONSTANTS OF COLLECTION VER 3 */

import java.util.*;
import java.io.*;
class JPS34
{
   static void show(String s)
   {
          System.out.println(s);
   }
   public static void main(String args[])
   {
          List LL = Collections.EMPTY_LIST;
          //LL.add(0,"hello");line generates error
          show("
LL.isEmpty():" + LL.isEmpty());

          Set S = Collections.EMPTY_SET;
          //S.add("hello");line generates error
          show("
S.isEmpty():" + S.isEmpty());
          Map M = Collections.EMPTY_MAP;
          //M.put("hello","bye");line generates error
          show("
M.isEmpty():" + M.isEmpty());
   }
}

OUTPUT:

LL.isEmpty():true
S.isEmpty():true
M.isEmpty():true

Explanation: The static constants EMPTY_LIST, EMPTY_SET and EMPTY_MAP represent empty immutable list, set and map, respectively. Rest is simple to understand.

18.12 PONDERABLE POINTS

1.   The Collection Framework provides a well-designed set of interfaces and classes for storing and manipulating groups of data as a single unit, a collection. The framework provides a convenient API to many of the abstract data types used in data structure curriculum: maps, sets, lists, trees, arrays, hashtables and so on.

2.   The Collections Framework is made up of a set of interfaces for working with groups of objects. The different interfaces describe different types of groups.

3.   The Collection interface is a group of objects with duplicates allowed.

4.   The Set interface extends Collection but forbids duplicates.

5.   The List interface extends Collection, allows duplicates, and introduces positional indexing.

6.   The Map interface extends neither Set nor Collection.

7.   There are two general-purpose List implementations in the Collection Framework: ArrayList and LinkedList.

8.   Iterating means accessing each element of the collection one by one, that is, using an iterator each of the elements of the collection can be cycled through. The iterator() method of the Collection interface returns an Iterator. With the Iterator interface methods, a collection can be traversed from start to finish.

9.   The Collections Framework provides two general-purpose implementations of the Set interface: HashSet and TreeSet.

10. A Map is used to store key-value pairs, with the values retrieved using the key. For each given key there will be a corresponding value. In essence, each element of the map is stored as a (key, value) pair. Given a key, a value can be retrieved. This is the most powerful feature of map. Both key and value are objects. The keys must be unique but values may be duplicates.

11. The Comparator interface is a type of comparison function, which imposes a total ordering on some collection of objects.

12. The historical collection classes are those classes which were supplied with the earlier version of Java. They are Vector, Stack, etc.

13. The Vector class implements a growable array of objects, but can store heterogeneous data elements. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

14. The Enumeration interface allows one to iterate through all the elements of a collection.

15. The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. They are push, pop empty, search and peek.

16. The class Hashtable implements a hashtable, which maps keys to values. Any non-null object can be used as a key or as a value. The Hashtable implementation is a generic dictionary that permits storing any object as its key or value (besides null).

17. The Properties implementation is a specialized Hashtable for working with text strings. In Properties the key is a String and the value is also a String. The class also supports loading and saving property settings from an input stream or to an output stream.

18. The Collection class available as part of the Collections Framework provides support for various algorithms with the collection classes, both new and old. This class consists, exclusively, of static methods that operate on or returns collections.

REVIEW QUESTIONS

1.   What is Java Collection Framework?

2.   What are the four main types defined in the Java Collection Framework?

3.   What is legacy class?

4.   Which collection classes are implemented with an indexed structure (i.e., a simple array)?

5.   Which collection classes are implemented with a linked structure?

6.   What is an ArrayList object?

7.   What is a LinkedList object?

8.   What is the Collection interface?

9.   What set-theoretic methods are supported by the Java Collection Framework?

10. What is an iterator?

int chars(List<String>strings)
//returns the total number of
characters in all the srtings

11. How are iterators similar to array indexes?

12. How are iterators different from array indexes?

13. How can the Array class be used to initialize a collection?

14. How can the Collections class be used to initialize a collection?

15. What is a generic class?

16. What is a generic method?

17. What is generic type parameter?

18. What is a constrained generic type parameter?

19. What is generic type argument?

20. What is auto boxing?

21. Write and test this method:

22. Write an test this method using an iterator:

void print(Collection C)
//prints all the elements of the
collection c

23. Write and test this generic method:

<E>int frequency(Collection<E>c, E
e){
//returns the number of occur-
rences of e in c

(a) Using an iterator.

(b) Using an enhanced for loop

24. Write and test this generic method:

<E>E      getElementAt(List<E>list,
int index){
//returns the list element at the
specified index

(a) Using an iterator.

(b) Using an enhanced for loop.

Multiple Choice Questions

1.   A hash table can store a maximum of 10 records. Currently there are records in location 1, 3, 4, 7, 8, 9, and 10. The probability of a new record going into location 2, with a hash function resolving collisions by linear probing is:

(a) 0.6

(b) 0.1

(c) 0.2

(d) 0.5

2.   The HashMap class automatically resizes its hash table when the load factor reaches a specific threshold. This threshold value can be set by:

(a) public HashMap (int initialCa-pacity, float loadFactor)

(b) public HashMap (int initial size, float loadFactor)

(c) public HashMap (int initial size, float (Capacity)

(d) None of the above.

3.   Which of the following statements is true:

I. The size of the hash table is the actual number of elements in the table.

II. The capacity of the table is the number of components that hash table has.

III. The HashMap class automatically resizes its hash table when the load factor reaches a specific threshold.

IV. The ratio of the size of the hash table to the capacity of the table is called as load factor.

(a) I and II

(b) II and IV

(c) III and IV

(d) All are correct.

4.   Java defines Hashtable class in ________ package.

(a) java.awt

(b) java.util

(c) java.io

(d) java.lang

5.   A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is:

(a) (x-1)(x-2).(x-(m-2))(m-1)/x ^m-1

(b) (x-1)(x-2).(x-(m-1))(m-1)/x ^m-1

(c) (x-1)(x-2).(x-(m-2))(m-1)/x ^m

(d) (x-1)(x-2).(x-(m-1))(m-1)/x ^m

6.   If the hashing function is the remainder on division, the clustering is more likely to occur if the storage space is divided into 40 sectors rather than 41. This conclusion is:

(a) More likely to be false

(b) More likely to be true

(c) Is always false

(d) None of the above

7.   A hash function f defined as f(key) = key mod 7, with linear probing, is used to insert the keys 37, 72, 48, 98, 11, 56, into a table indexed from 0 to 6. 11 will be stored at the location:

(a)3

(b) 4

(c) 5

(d) 6

8.   Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8. If a collision occurs at position 4, which of the following locations will never be adopted?

(a)4

(b)5

(c) 8

(d) 2

9.   Java defines four implementations of its Map interface: the AbstractMap class, the HashMap class, the TreeMap class and the WeakHashMap class. Here, AbstractMap class works as:

(a) Inherited class for all the other three classes

(b) Base class for all the other three classes

(c) Inner class for all the other three classes

(d) None of the above

10. Trace the following code

 1. import java.util.*;
 2. class JPS
 3. {
 4. static void show(String s)
 5. {
 6. System.out.println(s);
 7. }
 8.  public static void main(String args[])
 9. {
10. HashMap HM=new HashMap();
11. HM.put("PEARSON", new Integer(201));
12. HM.put("Noida", new Integer(202));
13. Set s=HM.entrySet();
14. show("Map elements
");
15. Iterator itr=s.iterator();
16. show("Key	 Value");
17. while(itr.hasNext())
18. {
19. Map.Entry me=(Map.Entry) itr.next();
20. show(me.getkey())+" t"+me.getValue());
21. }
22. }
23. }

(a) Map elements
Key                   Value
EARSON          201
Noida                202

(b) Map elements
Key                   Value
Noida                201
PEARSON       202

(c) Map elements
Key                   Value
PEARSON        202
Noida                201

(d) None of the above

KEY FOR MULTIPLE CHOICE QUESTIONS

1.   a

2.   a

3.   d

4.   b

5.   a

6.   b

7.   c

8.   d

9.   b

10. a