CHAPTER 23
COLLECTION FRAMEWORK
When we start studying a programming language, we work with simple primitive data types. Then we study objects and arrays. When we start programming for real-life problems, two things happen: the size of data we handle increases and the processing also gets involved.
At this stage the program development time increases. The execution time of the program also becomes significant.
Therefore, at this stage when we want to handle huge data, we must have appropriate tools with us. Java comes with the answer––a “collection framework”.
By collection, we mean an object which groups multiple elements in a single group. The elements in general are data objects. Examples are library books, student records, and so on. The equivalent of Collections in C++ is known as Standard Template Library (STL) which offers container classes and algorithms.
A framework means a skeleton, an arrangement, or an organization. Hence, collection framework provides us a nice organization to handle large amount of data. It consists of interfaces, implementations, and algorithms.
The basic entity in this collection framework is the interface. The Java collection framework provides the following interfaces.
CollectionSetSortedSetListQueueMapSortedMap
Their hierarchical relationship is displayed in Figure 23.1.
A close look will reveal that there are two distinct groups. The Map and SortedMap belong to a separate group. A typical element of this group is a “pair of object”, while in the other group, an element is nothing but a single object.
There are many benefits of the Java collection framework. However, at this level we can appreciate only two of them.
Using collections reduces programming effort. It provides us with ready-made implementations of data structures and algorithms. In any medium-size program, one will have to devote about 70% time to these things. If we have mastered the collection framework, writing related code will settle to writing only a few lines. It means there will be substantial reduction in programming efforts.
It also increases program speed and quality. As these data structures and algorithms are implemented by experts, the chance is that programs using them will execute faster than those developed by an average programmer. Also by using collection framework, we save substantial time for program development. This time can be utilized to tune and improve the performance of the program.
Figure 23.1 Hierarchical Relationship of Collection Interfaces
It is possible to implement these interfaces using different data structures like resizable array, LinkedList, Hashtable, among others. It gives these implementations different performance parameters. It is possible to have a given interface to have different implementations. Table 23.1 illustrates general-purpose implementations of various Collection interfaces.
Table 23.1 Collection Framework: General-Purpose Implementations
These interfaces and the classes which implement them are available in the package java.util.
With this much background, let us start our detailed study with Collection interface.
23.1 Collection Interface
The Collection interface provides the basic functionality for the collection. As the name collection suggests collecting objects, we can imagine on our own what methods (for operations) this interface should support.
The basic operations we expect are as follows:
- Add an element to the collection.
- Remove the element from the collection.
- Find the number of elements in the collection.
- Move from element to element for which we need an iterator.
All the operations are supported by suitable methods. In addition to these, there are many additional methods supported by these interfaces. Table 23.2 describes various methods declared in this interface.
Table 23.2 Method Summary: Collection Interface
boolean |
add(E o) |
Ensures that this collection contains the specified element (optional operation). |
boolean |
addAll(Collection<? extends E> c) |
Adds all of the elements in the specified collection to this collection (optional operation). |
void |
clear() |
Removes all of the elements from this collection (optional operation). |
boolean |
contains(Object o) |
Returns true if this collection contains the specified element. |
boolean |
containsAll (Collection<?> c) |
Returns true if this collection contains all of the elements in the specified collection. |
boolean |
equals(Object o) |
Compares the specified object with this collection for equality. |
int |
hashCode() |
Returns the hash code value for this collection. |
boolean |
isEmpty() |
Returns true if this collection contains no elements. |
Iterator<E> |
iterator() |
Returns an iterator over the elements in this collection. |
boolean |
remove(Object o) |
Removes a single instance of the specified element from this collection, if it is present (optional operation). |
boolean |
removeAll(Collection <?> c) |
Removes all elements of this collection that are also contained in the specified collection (optional operation). |
boolean |
retainAll(Collection <?> c) |
Retains only the elements in this collection that are contained in the specified collection (optional operation). |
int |
size() |
Returns the number of elements in this collection. |
Object[] |
toArray() |
Returns an array containing all of the elements in this collection. |
<T> T[] |
toArray(T[] a) |
Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array. |
23.2 List Interface
The first interface based on Collection interface that we are going to study is List interface. Here the collection is an ordered collection. We may call it a sequence. It may be noted that duplicates are allowed in this collection.
This interface provides operations for the following tasks:
- Positional access: We can manipulate elements based on position in the list (similar to the index of an array).
- Search: We can search for a specified object in the list and get its position
- Iteration: We can iterate over the list.
- Range view: We can perform arbitrary range operations on the list.
You may want to compare the List interface with class Vector. The class Vector is a concrete implementation while list is only an interface. However, both have similar functionality. It is reported that List interface is better than Vector as it has removed some of its minor deficiencies. The class Vector has been retrofitted to implement List.
Table 23.3 describes the various methods from Interface List.
Table 23.3 Method Summary: Interface List
Java offers two general-purpose List implementations: ArrayList and LinkedList. Most of the times, programmers will be using ArrayList. We can access any element with the help of the index. The time for accessing any element is the same. This behaviour is known as “constant-time” performance. Also, the access is very fast. ArrayList is similar to legacy class Vector.
In the early days of computer science, detailed study had proved that frequent insertion and deletion taxed (burden) the computer. Hence, a data structure called LinkedList was invented. It is good for frequent insertions and/or deletions. Hence, Java supports another concrete implementation of List interface known as LinkedList.
Now, let us start our study of concrete implantations of List interface with ArrayList.
23.3 ArrayList
The class ArrayList offers all the benefits of an array with complete functionality of the List interface. Let us write a program to study it.
Problem: Write a program to demonstrate the working of an ArrayList class.
Solution: We will first create a new class myStudent. We will also develop a method getData to create data of 10 students and put it in array “A”. The main program will pick data from array “A”.
Now we will create an ArrayList with this data from array “A”. First, we will print the collection ArrayList with default option. Then we will write this data as one element on one line. (see Program 23.1).
PROGRAM 23.1 ArrayList
// alist1.java
import java.util.*;
public class alist1
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd ;
static Integer myKey ;
public static void main(String args[] ) throws Exception
{ int i ;
ArrayList< myStudent>
tab1 = new ArrayList< myStudent>();
System.out.println("<---alist1--->");
getData(A);
/* for debugging only
for (i=0;i<10;i++)
System.out.println(A[i]);
*/
// Putting all elemnets in the ArrayList
for (i=0;i<10;i++)
tab1.add(A[i]) ;
// listing all elements
System.out.println( tab1 );
System.out.println();
// line by line
for (i=0;i<tab1.size();i++)
System.out.println( tab1.get(i) ) ;
}
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[2]= new myStudent(151, "Mandar");
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422,"Dilip");
X[5]= new myStudent(501, "Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[8]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
}
class myStudent
{ public Integer BPnumber ;
public String name;
myStudent( int n, String s )
{ BPnumber = new Integer(n);
name = s;
}
public String toString()
{ return ( BPnumber + "--" + name);
}
}
If you run the program, you will get the following output.
Output alist1.out
<---alist1--->
[101--Vikas, 111--Nilesh, 151--Mandar, 301--Anil, 422--Dilip, 501--Jyotsna,
524--Payal, 635--Gurprasad, 701--porus, 801--Glenn]
101--Vikas
111--Nilesh
151--Mandar
301--Anil
422--Dilip
501--Jyotsna
524--Payal
635--Gurprasad
701--porus
801-Glenn
Notice the use of square brackets in default printout.
It is possible to construct an ArrayList in three different ways. Table 23.4 illustrates these constructors.
Table 23.4 Constructor Summary: ArrayList
ArrayList() |
Constructs an empty list with an initial capacity of 10. |
ArrayList(Collection<? extends E> c) |
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator. |
ArrayList(int initialCapacity) |
Constructs an empty list with the specified initial capacity. |
Table 23.5 illustrates various methods from the class ArrayList.
Table 23.5 Method Summary: ArrayList
23.4 LinkedList
Another concrete implementation of interface List is LinkedList. Those who have studied the subject of “Data Structure” know that this technique of organizing list offers very easy and quick insertion and deletions. If in our application the list is constantly being modified with insertions and deletions, then this is our best bet. We have already developed a linked list ourselves in a program in an earlier chapter. Let us write a small program to become familiar with this ready-made implementation.
Note: In this chapter, we will frequently talk of speed and performance. Today’s computers are very fast. If we compare implementations with moderate data of one or two thousand objects, all implementations will look equally fast. Only when the data is large and applications start needing say more than 30 seconds to run, then only we can test various hypothesis regarding performance. You can generate large data with the help of random number generator and then compare different implementations.
Problem: Write a program to demonstrate Collection Class LinkedList.
Solution: In this program, we will again use an array A to store data of class myStudent. Then we will create a linked List and also print it. Next, we will remove the first element and add it at the end. We will print the list to check the list.
PROGRAM 23.2 LinkedList
// linked1.java
import java.util.*;
public class linked1
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd ;
static Integer myKey ;
public static void main(String args[] ) throws Exception
{ int i ;
myStudent temp;
LinkedList< myStudent>
tab1 = new LinkedList< myStudent>();
System.out.println("<---linked1.java--->");
getData(A);
// Putting all elements in the LinkedList
for (i=0;i<10;i++)
tab1.add(A[i]) ;
// listing all elements line by line
for (i=0;i<tab1.size();i++)
System.out.println( tab1.get(i) ) ;
tab1.addLast(temp);
// listing again after change
System.out.println("
after change");
for (i=0;i<tab1.size();i++)
System.out.println( tab1.get(i) ) ;
}
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[2]= new myStudent(151,"Mandar");
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422, "Dilip");
X[5]= new myStudent(501, "Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[8]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
}
class myStudent
{ public Integer BPnumber ;
public String name;
myStudent( int n, String s )
{ BPnumber = new Integer(n);
name = s;
}
public String toString()
{ return ( BPnumber + "--" + name);
}
}
If you run the program, you will get the following output:
Output
<---linked1.java--->
101--Vikas
111--Nilesh
151--Mandar
301--Anil
422--Dilip
501--Jyotsna
524--Payal
635--Gurprasad
701--porus
801--Glenn
after change
111--Nilesh
151--Mandar
301--Anil
501--Jyotsna
524--Payal
635--Gurprasad
701--porus
801--Glenn
101-Vikas
Please note that record 101--Vikas moved from the first position to the last one.
Java provides two constructors for this class. They are as shown in Table 23.6.
Table 23.6 Constructor Summary: LinkedList
LinkedList() |
Constructs an empty list. |
LinkedList(Collection<? extends E> c) |
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator. |
Table 23.7 lists all the methods offered by class LinkedList.
Table 23.7 Method Summary: LinkedList
23.5 Interface Set
We have studied Sets in Mathematics. This idea is put in practice by a collection named Set. We know that a set cannot contain duplicates. The Set interface contains methods which are inherited from Collection. It also enforces the condition that there are no duplicates. To achieve this, we must define methods equals and hashCode properly.
Table 23.8 illustrates various methods from interface Set.
Table 23.8 Method Summary: Interface Set
In Java, there are three implementations of interface Set. They are HashSet, TreeSet, and LinkedHashSet. Out of these, we will be studying the first two in detail. The HashSet is used for speed while TreeSet offers the facility of ordering.
At this stage, we have to introduce the concept of an iterator.
23.5.1 Iterator
So far, we have studied two collections. We did not find any difficulty navigating them. ArrayList behaves as an Array. We could use index comfortably. LinkedList is more complex. It still supported the method get(i) to return the ith element. What about structures that are more complex? There may not be anything like the index. We need something to move from one element of object to another: enter interface Iterator. It helps to move from one object to another effortlessly. This defines three methods.
The method hasNext() returns the Boolean value true if the iteration has more elements. The method next() returns the next element in the iteration. The method remove() removes the element from the collection, returned by the iterator.
With this much introduction, we are in a position to study any complex collection. Let us start with the TreeSet.
23.6 TreeSet
The class TreeSet is a concrete implementation of the Set interface. Hence, it cannot tolerate duplicates. If we try to find an element which is already in the TreeSet, such an attempt will fail. This is the reason for using the return type Boolean for this method add(). When we retrieve the elements of this collection, we find them in (normally) ascending order.
Problem: Write a program to demonstrate Collection class TreeSet.
Solution: Let us continue with our data class myStudent. But in this example, we will face some trouble. Hence, we will use the same class but with enhancement (see Program 23.3).
PROGRAM 23.3 TreeSet
// tset2.java
import java.util.*;
public class tset2
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd,myStd1 ;
static myStudent temp;
public static void main(String args[] ) throws Exception
{ int i ;
TreeSet < myStudent>
tab1 = new TreeSet<myStudent >();
System.out.println("<---tset2--->");
getData(A);
// Putting all elements in the TreeMap
for (i=0;i<10;i++)
tab1.add(A[i]) ;
// listing all elements
System.out.println("Listing Elements");
Iterator it = tab1.iterator();
while( it.hasNext() )
{ temp =(myStudent )it.next() ;
System.out.println( temp);
}
System.out.println("No of Elements are " + tab1.size());
// Creating and adding duplicate element
myStd = new myStudent(701, "porus");//A[2];
if( tab1.add(myStd) )System.out.println("New element added");
else System.out.println("Operation failed");
}
// please note index 2 and 8 are deliberately switched
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[8]= new myStudent(151, "Mandar");
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422, "Dilip");
X[5]= new myStudent(501, "Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[2]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
final class myStudent implements Comparable <myStudent>
{
public int BPnumber ;
public String name;
myStudent( int n, String s )
{ BPnumber = n;
name = s;
}
public String toString()
{ return ( BPnumber + "--" + name);
}
public int compareTo(myStudent m)
{ if (this.BPnumber >m.BPnumber ) return +1 ;
else if (this.BPnumber == m.BPnumber ) return 0 ;
else return -1;
}
public boolean equals( Object o)
{ if (!(o instanceof myStudent))
return false;
myStudent m = (myStudent) o ;
if ( ( this.BPnumber == m.BPnumber)
&& (this.name == m.name) ) return true;
else return false;
}
public int hashCode() {
return 31*BPnumber + name.hashCode();
}
}
If you run the program, you will get the following output:
Output
<---tset2--->
Listing Elements
101--Vikas
111--Nilesh
151--Mandar
301--Anil
422--Dilip
501--Jyotsna
524--Payal
635--Gurprasad
701--porus
801--Glenn
No of Elements are 10
Operation failed
Please note that in the input elements x[2] and x[8] are interchanged. This means input data is unsorted.
In the output, the students are in ascending order (of their BPnumber). When we try to add a duplicate entry (701, “porus”) the operation fails.
We have said that TreeSet keeps elements in an ordered form. We have defined class myStudent. The compiler has no special knowledge of it. Hence, we have to tell how to compare objects of this class. Here we have added three methods, compareTo(), equals(), and hashCode(), to our class definition.
Table 23.9 illustrates the constructors from class TreeSet.
Table 23.9 Constructor Summary: Class TreeSet
TreeSet() |
Constructs a new, empty set sorted according to the natural order of the elements. |
TreeSet(Collection<? extends E> c) |
Constructs a new set containing the elements in the specified collection, sorted according to the natural order of the elements. |
TreeSet(Comparator<? super E> c) |
Constructs a new, empty set sorted according to the specified comparator. |
TreeSet(SortedSet<E> s) |
Constructs a new set containing the same elements as the specified sorted set, sorted according to the same ordering. |
Table 23.10 illustrates the methods from the class TreeSet.
Table 23.10 Method Summary: Class TreeSet
23.7 HashSet
When we want a set with very fast retrieval, we use the implementation HashSet. As the name suggest, it uses Hashing for storing and retrieval.
Problem: Write a program to demonstrate Collection class HashSet.
Solution: Let us continue with the data from class myStudent. Here we will add the data in the HashSet. Since there is no ordering, we will get the data out with the help of the iterator. Then we will create a new object and test the method contains() (see Program 23.4).
PROGRAM 23.4 HashSet
// hset1.java
import java.util.*;
public class hset1
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd ;
static Integer myKey ;
public static void main(String args[] ) throws Exception
{ int i ;
HashSet< myStudent>
tab1 = new HashSet< myStudent>();
System.out.println("<---hset1--->");
getData(A);
// Putting all elements in the HashSet
for (i=0;i<10;i++)
tab1.add(A[i]) ;
// listing all elements
Iterator it = tab1.iterator();
while( it.hasNext() )
{ myStd = (myStudent ) it.next() ;
System.out.println( myStd) ;
}
myStd = new myStudent(151, "Mandar");
// myStd = A[2]; // note2
System.out.println(myStd.hashCode());
System.out.println(A[2].hashCode());
if ( tab1.contains( myStd ) )
System.out.println( "Student found") ;
else System.out.println( "Not found") ;
}
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[2]= new myStudent(151, "Mandar");
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422, "Dilip");
X[5]= new myStudent(501, "Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[8]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
}
class myStudent
{
public Integer BPnumber ;
public String name;
myStudent( int n, String s )
{ BPnumber = new Integer(n);
name = s;
}
public String toString()
{ return ( BPnumber + "--" + name);
}
}
If you run the program, you will get the following output:
Output
<---hset1--->
101--Vikas
524--Payal
151--Mandar
111--Nilesh
701--porus
501--Jyotsna
635--Gurprasad
422--Dilip
301--Anil
27553328
19972507
Not found
Prima facie, you will be surprised by the result. Mr. Mandar is very much in the set, still it is said to be not found. The hash codes for the object in the HashSet (A[2]) and that of myStd which we check are different. Please note the line commented out as note 2. Replace the previous statement by this statement and check the result.
To your surprise, you will get the answer “Student found”. Please note that this is a set. We have put A[2] object in it. So it is found. Its copy is not found.
Now you will appreciate why we have put additional methods in Program 23.4. Try the definition of class myStudent from previous class in this program and see the result.
Table 23.11 illustrates constructors from class HashSet.
Table 23.11 Constructor Summary: HashSet
HashSet() |
Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75). |
HashSet(Collection<? extends E> c) |
Constructs a new set containing the elements in the specified collection. |
HashSet(int initialCapacity) |
Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor, which is 0.75. |
HashSet(int initialCapacity, float loadFactor) |
Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load factor. |
Table 23.12 illustrates the methods from class HashSet.
Table 23.12 Method Summary: HashSet
23.8 Interface Map
The Collection interfaces seen so far has only one parameter. Now we are going to study a new interface called Map. It has two parameters known as key and value. This interface takes the place of abstract class Dictionary. We know that a typical entry (object) in any dictionary contains a pair a word and its meaning. The word is small and is the most basic (equivalent to key or pointer). Its meaning may be given in a paragraph. A large object! A dictionary meaning of the word “program” is “descriptive notice of series of events”. Here, the word “program” is a key and its meaning is the “object”. This has been depicted in Figure 23.2.
We can understand Map as a collection of objects of type keys such that each key points uniquely to an object known as values. There is unbreakable bond between a key and its corresponding value.
In simple applications, we use an array of objects. The array index, an integer, acts as if it is a pointer to the object. If we use primitive type objects, like integer, as the key, there are many advantages. But we loose generality. Many keys in real-life applications will be strings. Since strings are objects in Java, defining keys as objects provides tremendous generality to the interface Map. We can use strings for keys. But what about the use of primitive data types? Java provides us with wrapper classes, which can effectively represent primary data types.
Table 23.13 describes the methods from interface Map.
Figure 23.2 Element of Map Interface
Table 23.13 Method Summary: Interface Map
void |
clear() |
Removes all mappings from this map (optional operation). |
boolean |
containsKey(Object key) |
Returns true if this map contains a mapping for the specified key. |
boolean |
containsValue(Object value) |
Returns true if this map maps one or more keys to the specified value. |
Set<Map. Entry<K,V>> |
entrySet() |
Returns a set view of the mappings contained in this map. |
boolean |
equals(Object o) |
Compares the specified object with this map for equality. |
V |
get(Object key) |
Returns the value to which this map maps the specified key. |
int |
hashCode() |
Returns the hash code value for this map. |
boolean |
isEmpty() |
Returns true if this map contains no key-value mappings. |
Set<K> |
keySet() |
Returns a set view of the keys contained in this map. |
V |
put(K key, V value) |
Associates the specified value with the specified key in this map (optional operation). |
void |
putAll(Map<? extends K,? extends V> t) |
Copies all of the mappings from the specified map to this map (optional operation). |
V |
remove(Object key) |
Removes the mapping for this key from this map if it is present (optional operation). |
int |
size() |
Returns the number of key-value mappings in this map. |
Collection<V> |
values() |
Returns a collection view of the values contained in this map. |
23.9 HashMap
The Map interface is implemented by concrete classes like HashMap and TreeMap. Let us first study HashMap.
Table 23.14 describes constructors for class HashMap.
Table 23.14 Constructor Summary: HashMap
HashMap() |
Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75). |
HashMap(int initialCapacity) |
Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75). |
HashMap(int initialCapacity, float loadFactor) |
Constructs an empty HashMap with the specified initial capacity and load factor. |
HashMap(Map<? extends K,? extends V> m) |
Constructs a new HashMap with the same mappings as the specified Map. |
Table 23.15 describes various methods from the class HashMap.
Table 23.15 Method Summary: HashMap
In earlier versions of Java, a concrete class known as Hashtable was supported. Now this class has been made compliant to Map interface. This class is more or less identical to HashMap. Since we are studying the Hashtable class in detail, we will not develop any program for HashMap interface at this stage. We will demonstrate it at the end of the chapter.
23.10 TreeMap
This class uses Tree. Hence, the class is suitable for getting the output in a sorted manner. This organization assures (n log n ) performance. Let us study it with a program.
Problem: Write a program to demonstrate TreeMap.
Solution: We know that when we add elements to a TreeMap, it maintains the order. To verify this fact, we need data which is unsorted. As we want to continue with our standard data, we will simply exchange any two elements say at index 2 and 8. It makes the data unsorted (see Program 23.5).
PROGRAM 23.5 TreeMap
// tmap1.java
import java.util.*;
public class tmap1
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd ;
static Integer myKey ;
public static void main(String args[] ) throws Exception
{ int i ;
TreeMap<Integer, myStudent>
tab1 = new TreeMap<Integer, myStudent>();
System.out.println("<---tmap1--->");
getData(A);
// Putting all elements in the TreeMap
for (i=0;i<10;i++)
tab1.put(A[i].BPnumber,A[i]) ;
// listing all elements
Set s1 =tab1.entrySet();
Iterator it = s1.iterator();
while( it.hasNext() )
{
Map.Entry kvpair = (Map.Entry )it.next() ;
myStd = (myStudent ) kvpair.getValue() ;
System.out.println( myStd) ;
}
}
// please note index 2 and 8 are deliberately switched
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[8]= new myStudent(151, "Mandar");
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422, "Dilip");
X[5]= new myStudent(501, "Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[2]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
}
class myStudent
{
public Integer BPnumber ;
public String name;
myStudent( int n, String s )
{ BPnumber = new Integer(n);
name = s;
}
public String toString()
{ return ( BPnumber + "--" + name);
}
}
If you run the program, you will get the following output:
Output
<---tmap1--->
101--Vikas
111--Nilesh
151--Mandar
301--Anil
422--Dilip
501--Jyotsna
524--Payal
701--porus
801--Glenn
Please note that in the input (data) index 2 and 8 were changed. The input was thus unsorted. While we iterate over the TreeMap, we get an output which is in order.
Table 23.16 describes various constructors for class TreeMap.
Table 23.16 Constructor Summary: TreeMap
TreeMap() |
Constructs a new, empty map sorted according to the natural order of the keys. |
TreeMap(Comparator<? super K> c) |
Constructs a new, empty map sorted according to the given comparator. |
TreeMap(Map<? extends K,? extends V> m) |
Constructs a new map containing the same mappings as the given map, sorted according to the natural order of the keys. |
TreeMap(SortedMap<K,? extends V> m) |
Constructs a new map containing the same mappings as the given SortedMap, sorted according to the same ordering. |
Table 23.17 describes various methods from class TreeMap.
Table 23.17 Method Summary: TreeMap
23.11 Hashtable
This class was available as a custom class even before the collection framework came into existence. However, at present it is retrofitted with the Collection framework. When our data is suitable for using the Map technique, we have a choice between TreeMap and Hashtable. We know that Hashing gives very fast response for insertion/deletion operations. It is even better than (n log n). However, this technique does not order the data. Hence, when fast operations are desirable and we are not interested in any specific (ascending or descending) ordering, we prefer Hashtable. Let us study it with a program.
Problem: Write a program to demonstrate Hashtable.
Solution: In this program, we will use our standard data. First, we will add all elements and then list them. Then we create a new object and search it in the collection (see Program 23.6).
PROGRAM 23.6 Hashtable
// hash2.java
import java.util.*;
public class hash2
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd ;
static Integer myKey ;
public static void main(String args[] ) throws Exception
{ int i ;
Hashtable<Integer, myStudent>
tab1 = new Hashtable<Integer, myStudent>();
System.out.println("<---hash2.java--->");
getData(A);
// Putting all elemnets in the hashtable
for (i=0;i<10;i++)
tab1.put(A[i].BPnumber,A[i]) ;
// listing all elements
System.out.println(" listing all elements ");
Enumeration <myStudent> allvalues = tab1.elements();
while( allvalues.hasMoreElements() )
{ myStd = allvalues.nextElement() ;
System.out.println( myStd) ;
}
// listing all keys using for each statement
System.out.println(" listing only keys ");
for( Integer N :tab1.keySet() )
System.out.println(N) ;
myStd = new myStudent(151, "Mandar");
// myStd = A[2];
System.out.println("
Hash codes for A[2] and myStd");
System.out.println(myStd.hashCode());
System.out.println(A[2].hashCode());
if ( tab1.contains( myStd ) )
System.out.println( "Student found") ;
else System.out.println( "Not found") ;
}
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[2]= new myStudent(151, "Mandar");
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422, "Dilip");
X[5]= new myStudent(501, "Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[8]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
class myStudent
{ public Integer BPnumber ;
public String name;
myStudent( int n, String s )
{ BPnumber = new Integer(n);
name = s;
}
public String toString()
{ return ( BPnumber + "--" + name);
}
}
If you run the program, you will get the following output:
Output
<---hash2.java--->
listing all elements
801--Glenn
111--Nilesh
501--Jyotsna
524--Payal
635--Gurprasad
151--Mandar
701--porus
101--Vikas
422--Dilip
301--Anil
listing only keys
801
111
501
524
635
151
701
101
422
301
Hash codes for A[2] and myStd
8567361
9584176
Not found
Please note that the new object myStd is initialized with the data which is basically same as A[2]. Still their hash codes are different. Hence, when we search for this object, it is not found. Replace the statement
myStd = new myStudent(151, "Mandar");
with the following statement
myStd = A[2];
You will be surprised to know that now you get both hash codes as identical and the object is found.
Table 23.18 describes various constructors for the class Hashtable.
Table 23.18 Constructor Summary: Hashtable
Hashtable() |
Constructs a new, empty Hashtable with a default initial capacity (11) and load factor, which is 0.75. |
Hashtable(int initialCapacity) |
Constructs a new, empty Hashtable with the specified initial capacity and default load factor, which is 0.75. |
Hashtable(int initialCapacity, float loadFactor) |
Constructs a new, empty Hashtable with the specified initial capacity and the specified load factor. |
Hashtable(Map<? extends K,? extends V> t) |
Constructs a new Hashtable with the same mappings as the given Map. |
Table 23.19 describes various methods from the class Hashtable.
Table 23.19 Method Summary: HashTable
23.12 Algorithms
After coming up with the collection framework, Java developers have also supported a lot of algorithms in the collection framework, thus helping the programmers. These are polymorphic algorithms. Please note that methods with same name operate on collection of any type, and still produce correct result. That is why the term polymorphic is used. With these in-built methods, programming has nearly become a child’s play now.
Please note that we started with study of Collection interface. Java has also defined a class with the same name Collection. This class holds all the algorithms.
Most of the algorithms apply to the class List. Some of them are listed below.
sort |
Sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.) |
shuffle |
Randomly permutes the elements in a List. |
reverse |
Reverses the order of the elements in a List. |
rotate |
Rotates all the elements in a List by a specified distance. |
swap |
Swaps the elements at specified positions in a List. |
replaceAll |
Replaces all occurrences of one specified value with another. |
fill |
Overwrites every element in a List with the specified value. |
copy |
Copies the source List into the destination List. |
binarySearch |
Searches for an element in an ordered List using the binary search algorithm. |
indexOfSubList |
Returns the index of the first sub-list of one List that is equal to another. |
lastIndexOfSubList |
Returns the index of the last sub-list of one List that is equal to another. |
Table 23.20 describes the various methods from class Collections. Many of them are actually implementations of algorithms.
Table 23.20 Method Summary: Class Collections
Now it is the time to use these in programs. Let us start with sorting of data.
23.12.1 Sorting
Java offers ready-made method sort(). It comes in two flavours. We can sort using natural order of elements. Alternately, we may specify the order ourselves. It goes without saying that computer understands the natural order for wrapper classes and strings. However, computer cannot understand what the natural order for any given object is. Hence, the objects we want to sort must define Comparable interface. Unfortunately, we may be asked to write applications for a given class which does not implement this interface. In that case, we have to define a method compare for the objects of this class. Let us study this with a program.
Problem: Write a program to sort a data consisting of objects of class myStudent.
Solution: In the class myStudent, we have a field called name which is a string. To sort the data, let us choose this string. One of the parameters of sort is Comparator. In this program, we will define the Comparator in the parameter list itself (see Program 23.7).
PROGRAM 23.7 Sorting with Strings
// sort1.java
import java.util.*;
public class sort1
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd ;
static Integer myKey ;
public static void main(String args[] ) throws Exception
{ int i ;
ArrayList< myStudent>
tab1 = new ArrayList< myStudent>();
System.out.println("<---sort1--->");
getData(A);
// Putting all elemnets in the ArrayList
for (i=0;i<10;i++)
tab1.add(A[i]) ;
// Now sorting
Collections.sort(tab1,new Comparator<myStudent>()
{ public int compare(myStudent A, myStudent B)
{ return A.name.compareTo(B.name );
}
});
// listing all elements after sort
for (i=0;i<tab1.size();i++)
System.out.println( tab1.get(i) ) ;
}
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[2]= new myStudent(151, "Mandar”);
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422, "Dilip");
X[5]= new myStudent(501, {"Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[8]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
}
class myStudent
{
public Integer BPnumber ;
public String name;
myStudent( int n, String s )
{ BPnumber = new Integer(n);
}
public String toString()
{ return ( BPnumber + "--" + name);
}
}
If you run the program, you will get the following output:
Output
<---sort1--->
301--Anil
422--Dilip
801--Glenn
635--Gurprasad
501--Jyotsna
151--Mandar
111--Nilesh
524--Payal
101--Vikas
701-porus
Let us study another algorithm.
23.12.2 Algorithm shuffle
So far, we have talked about sorting, that is moving from unordered collection to ordered collection. What about its reverse? You may wonder whether at any time we need to move from an ordered collection to a disordered collection. Well, we may if want to play cards. There will be no fun if we are dealt with the same cards in every game. Java supplies us with a general algorithm named shuffle. We can use it for applications for playing cards.
Problem: Write a program to shuffle a deck of cards.
Solution: In this program, we will use an ArrayList to hold the 52 cards. At the beginning, we will generate the list with all cards in order. (as that is most simple.) Then we will call the method shuffle() (see Program 23.8).
PROGRAM 23.8 Algorithm shuffle
// sort2.java
import java.util.* ;
import java.lang.String ;
class Card
{ private int n ;
private int suit;
private int val;
Card( int i) // constructor
{ if ( (i<0) && (i>=52) )
{ System.out.println("Invalid card ");
System.exit(1);
}
n= i;
suit = n / 13 ;
val = n % 13 ;
};
public String show()
{ String s0;
String[] s1 = { "Spade", "Heart", "Diamond", "Club"};
String[] s2 = { "A","K","Q","J","T","9",
"8","7","6","5","4","3","2"};
return s1[suit] + " " + s2[val] ;
};
};
class sort2
{ static Card crd ;
public static void main(String args[])
{ final int FiftyTwo =52;
ArrayList <Card> myDeck = new ArrayList< Card>() ;
System.out.println("<---sort2.java--->");
for( int i=0;i<FiftyTwo;i++)
{ crd = new Card(i);
myDeck.add(crd);
}
// before Shuffling
System.out.println("
Before shuffling");
System.out.println(myDeck.get(0).show());
System.out.println(myDeck.get(1).show());
System.out.println(myDeck.get(2).show());
Collections.shuffle(myDeck, new Random());
// After Shuffling
System.out.println("
after shuffling");
System.out.println(myDeck.get(0).show());
System.out.println(myDeck.get(1).show());
System.out.println(myDeck.get(2).show());
}
}
If you run the program, you will get the following output:
Output
<---sort2.java--->
Before shuffling
Spade A
Spade K
Spade Q
after shuffling
Club J
Club A
Heart K
You will agree that the collection framework, in general, and algorithms, in particular, have made our jobs much easier.
23.12.3 Binary search
For fast searching, we can use binary search algorithm. Only the pre-condition is that the data has to be sorted. With collection framework, sorting can be very simple. So will be the searching with binary search algorithm. Let us write a small program to study it.
Java is a case-sensitive language. If you type “Audioclip” in place of “AudioClip”, you will get compilation error. It is quite annoying when we know that there is such a class (Interface). If some system can tell whether such a class possibly exists, it will be great help. Let us try an elementary program for this. We will also use this program as a demonstration of algorithm search.
Problem: Write a program to demonstrate algorithm binarySearch from collection framework.
Solution: Let us collect all known Java classes and interfaces in a file named allclass.txt. We will put one name on one line so that reading this file becomes simple. We will use ArrayList, as it offers us the facility to sort as well as search the objects. Here the object is a string. We will read an input string, convert it into lower case, and then put it in the collection.
Success of binary search depends on the data being sorted. Hence, we will first sort the Collection. It then becomes a simple task. First, get the string to search, and then pass its lower-case version to the method Collections.binarySearch() (see Program 23.9).
PROGRAM 23.9 Algorithm binarySearch
// alist3.java
import java.io.* ;
import java.util.*;
public class alist3
{
public static void main(String args[] ) throws Exception
{ int i,k ;
String s1 ,toSearch;
ArrayList< String>
tab1 = new ArrayList< String >();
System.out.println("<---alist3--->");
FileReader f1 = new FileReader("allclass.txt");
BufferedReader fin = new BufferedReader(f1);
Scanner sc = new Scanner(System.in);
i=0;
while ( fin.ready() )
{ s1 = fin.readLine();
// System.out.println(i + " " +s1); for debugging
i++;
tab1.add(s1.toLowerCase());
}
fin.close();
System.out.println( i + " Stings added");
Collections.sort(tab1);
k =
Collections.binarySearch(tab1,toSearch.toLowerCase() );
if (k<0) System.out.println("Not found");
else System.out.println( "found at location" + k);
}
}
If you run the program, you will get following output.
Output
<---alist3--->
3279 Stings added
found at location227
The first few lines of file allclass.txt are shown below.
File allclass.txt
AbstractAction
AbstractBorder
AbstractButton
AbstractCellEditor
AbstractCollection
AbstractColorChooserPanel
AbstractDocument
AbstractDocument.AttributeContext
AbstractDocument.Content
AbstractDocument.ElementEdit
AbstractExecutorService
AbstractInterruptibleChannel
AbstractLayoutCache
AbstractLayoutCache.NodeDimensions
AbstractList
AbstractListModel
AbstractMap
AbstractMethodError
AbstractPreferences
AbstractQueue
AbstractQueuedSynchronizer
AbstractSelectableChannel
AbstractSelectionKey
AbstractSelector
AbstractSequentialList
AbstractSet
AbstractSpinnerModel
AbstractTableModel
AbstractUndoableEdit
AbstractWriter
23.13 HashMap
So far, we have not demonstrated the use of HashMap. Its power can be enjoyed in the backdrop of Program 23.9.
The aforementioned program was very nice but only elementary. It is not sufficient to know whether any class exists or not. If it exists, we must know how to spell it (Which characters are in upper case?). This calls for two strings: One a correct class name, and other all of its lower-case versions. These two strings are associated with each other. This is an excellent situation for a map. The second string will be the key and the first string (actual class name) will be the value.
Problem: Write a program to demonstrate class HashMap from collection framework.
Solution: Let us continue with Program 23.9. It does not help us to know whether the sting exists. If it exists, we must print both the actual class name and the string which we were searching. (See Program 23.10)
PROGRAM 23.10 HashMap
// hmap1.java
import java.io.* ;
import java.util.*;
public class hmap1
{
public static void main(String args[] ) throws Exception
{ int i ;
String s1,s2,toSearch;
HashMap< String,String>
tab1 = new HashMap< String,String >();
System.out.println("<---hmap1--->");
FileReader f1 = new FileReader("allclass.txt");
BufferedReader fin = new BufferedReader(f1);
Scanner sc = new Scanner(System.in);
i=0;
while ( fin.ready() )
{ s1 = fin.readLine();
// System.out.println(i + " " +s1); for debugging
i++;
tab1.put(s1.toLowerCase(),s1);
}
fin.close();
System.out.println( i + " Strings added");
toSearch = "Audioclip";
s2 = tab1.get( toSearch.toLowerCase() ) ;
if ( s2 == null) System.out.println("Not found");
else
{ System.out.println( " searching " + toSearch );
System.out.println( " found " + s2 );
}
}
}
If we run the program, we will get following output.
<---hmap1--->
3279 Strings added
searching Audioclip
found AudioClip
You will agree that such a program (module) will be very useful in any Java IDE.
23.14 Enhanced For Loop
You may feel that there is a sudden change in the topic. Well the discussion on collections has ended. We have discussed the enhanced for loop in Chapter 7. However, our intelligent readers must have found that the introduction as trivial. Well, the real power of enhanced for loop can be appreciated with the backdrop of HashSet.
When we add objects in HashSet, they go into a space depending on the hash code. There in no explicit indexing. Collection framework offers the facility of an iterator to get all the elements. We can even delete an object with the help of an iterator.
If we are interested in only visiting all the elements (no deletions), we can use the for loop. The generalized syntax of such a loop is
for ( type variable : collection ) { } ;
Let us take the example similar to one we had used for HashSet. The use of iterator will now be replaced by an enhanced for loop.
Problem: Write a program to demonstrate the use of enhanced for loop with the class HashSet.
Solution: See Program 23.11.
PROGRAM 23.11 Enhanced For Loop
// forhset.java
import java.util.*;
public class forhset
{ static public myStudent[] A = new myStudent[10];
static myStudent myStd ;
static Integer myKey ;
public static void main(String args[] ) throws Exception
{ int i ;
HashSet< myStudent>
tab1 = new HashSet< myStudent>();
System.out.println("<---forhset--->");
getData(A);
// Putting all elements in the HashSet
for (i=0;i<10;i++)
tab1.add(A[i]) ;
// listing all elements
for ( myStudent x : tab1 )
{ System.out.println( x );
}
}
static void getData(myStudent[] X)
{ X[0]= new myStudent(101, "Vikas");
X[1]= new myStudent(111, "Nilesh");
X[2]= new myStudent(151, "Mandar");
X[3]= new myStudent(301, "Anil");
X[4]= new myStudent(422, "Dilip");
X[5]= new myStudent(501, "Jyotsna");
X[6]= new myStudent(524, "Payal");
X[7]= new myStudent(635, "Gurprasad");
X[8]= new myStudent(701, "porus");
X[9]= new myStudent(801, "Glenn");
}
}
If we run the program, we will get following output.
Output
<---forhset--->
301--Anil
635--Gurprasad
524--Payal
501--Jyotsna
101--Vikas
111--Nilesh
701--porus
151--Mandar
422--Dilip
801-Glenn
Please note that the order is not the one in which the objects arrived. But this is natural in a HashSet.
Keywords
binary search algorithm, algorithm shuffle, ArrayList, class Collections, collection framework, Collection interface, HashMap, HashSet, Hashtable, Interface, Map, Set, Interface, List, Linked List, LinkedList, shuffle(), sort(), TreeMap, TreeSet
RuleBook
| Collection framework | Components of “collection framework” are available in the package java.util |
Set |
Set is a collection interface used to maintain unique elements. |
Review Questions
- Which two interfaces are at the top of the hierarchies in the Java collection framework?
- Which interfaces does not allow duplicate objects?
- Is
Collectionan interface or a class? - In order to sort objects in a
List, which interface and method has to be implemented by these objects?
Exercises
- A file consists of records of students. Write a program and to read the records and create a new file which does not contain duplicates.
- Create a large data file (more than 100,000 objects) using random number generator. Write a code to compare the performance of binary search algorithm with searching using Hashing.
- Write a program to generate and shuffle a deck of playing cards.
- Write a method (on your own) to reverse the elements of a given
List. Compare the performance of your method with method reverse from Java collection framework. - Write a program to demonstrate the following methods from class
ArrayList:indexOf(),lastIndexOf(), andremove(). For simplicity, use wrapper class integer as data. - Create an
ArrayListof 100,000 integers. Covert it intoHashSet. Create 50 integers using random numbers. Compare the time required to search them in the above two data structures.