Learning Objectives
After completing this session, you will be able to:
‰ Set Interface and Implementations
‰ List Interface and Implementations
‰ Map Interface and Implementations
‰ Queue Interface and Implementations
‰ Define Abstract Classes
‰ Explain Routine Data Manipulation
‰ Describe Searching
‰ Define Composition
“Set” Interface
The Set interface is a collection that cannot contain duplicate elements.
The Set interface models the mathematical set abstraction and is used to represent sets:
‰ Cards comprising a poker hand
‰ Courses making up the schedule of a student
‰ The processes running on a machine
The Set interface contains only methods inherited from Collection and adds the restriction to
prohibit the duplicate elements.
“Set” Interface (Java SE 5)
public interface Set<E> extends Collection<E> {
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional
Iterator<E> iterator();
// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional
boolean removeAll(Collection<?> c); //optional
boolean retainAll(Collection<?> c); //optional
void clear(); //optional
// Array Operations
Object[] toArray();
<T> T[] toArray(T[] a);
}
“equals” Operation of Set Interface
Set also adds a stronger contract on the behavior of the equals and hashCode operations,
allowing Set instances to be compared meaningfullyeven if their implementation types differ. Two
Set instances are equal if theycontain the same elements.
“SortedSet” Interface
Sorted Set interface is a set that maintains its elements in ascending order. Several additional
operations are provided to take advantage of the ordering.
Sorted sets are used for naturally ordered sets, such as word lists and membership roll.
Implementations of “Set” Interface
The implementations of Set interface are:
‰ HashSet
‰ TreeSet
‰ LinkedHashSet
HashSet
‰ HashSet is much faster than TreeSet (constant-time versus log-time for most
operations) but offers no ordering guarantees.
‰ HashSet is the mostly commonly used implementation.
Caveats of Using HashSet
Iteration is linear in the sum of the number of entries and the number of buckets (the capacity):
‰ Choosing an initial capacity that is too high, can waste both space and time
‰ Choosing an initial capacity that is too low,wastes time by copying the data structure
each time it is forced to increase its capacity
Example: Set Interface and HashSet
public class MyOwnUtilityClass {
// Note that the first parameter type is set to
// Set interface not a particular implementation
// class such as HashSet. This makes the caller of
// this method to pass instances of different
// implementations of Set interface while
// this function picks up polymorphic behavior
// depending on the actual implementation type
// of the object instance passed.
public static void checkDuplicate(Set s, String[] args){
for (int i=0; i<args.length; i++)
if (!s.add(args[i])) {
System.out.println("Duplicate detected: "+args[i]);
}
System.out.println(s.size()+" distinct words detected:
"+s);
}
}
public class SetExample {
public static void main(String[] args) {
Set s = new HashSet(); // Order is not guaranteed
MyOwnUtilityClass.checkDuplicate(s, args);
s = new TreeSet(); // Order according to values
MyOwnUtilityClass.checkDuplicate(s, args);
s = new LinkedHashSet(); // Order according to insertion
MyOwnUtilityClass.checkDuplicate(s, args);
}
}
For example, the numbers 1, 2, 3, and 4 can be added in the following ways:
‰ Set type = java.util.HashSet [3, 2, 4, 1]
‰ Set type = java.util.TreeSet [1, 2, 3, 4]
‰ Set type = java.util.LinkedHashSet [2, 3, 4, 1]
TreeSet
‰ The TreeSet is one of two sorted collections (the other being TreeMap).
‰ No duplicates, iterates in sorted order.
‰ It generally guarantees that the elements will be in ascending order, according to
natural order.
Example: Set Interface and TreeSet
public static void main(String[] args) {
Set ts = new TreeSet();
ts.add("one");
ts.add("two");
ts.add("three");
ts.add("four");
ts.add("three");
System.out.println("Members from TreeSet = " + ts);
}
Result: Members from TreeSet = [four, one, three, two]
LinkedHashSet
‰ LinkedHashSet is implemented as a hash table with a linked list running through it.
‰ It provides insertion-ordered iteration (least recently inserted to most recently) and
runs nearly as fast as HashSet.
‰ It spares its clients from the unspecified, generally chaotic ordering provided by
HashSet without incurring the increased cost associated with TreeSet.
Example: Set Interface and LinkedHashSet
public static void main(String[] args) {
Set ts2 = new LinkedHashSet();
ts2.add(2);
ts2.add(1);
ts2.add(3);
ts2.add(3);
System.out.println("Members from LinkedHashSet = " + ts2);
}
Result: Members from LinkedHashSet = [2, 1, 3]
“List” Interface
‰ List interface is an ordered collection (sometimes called a sequence).
‰ Lists can contain duplicate elements.
‰ The user of a List interface generally has precise control over where in the each list
element is inserted and can access elements by their integer index (position).
Additional Operations Supported by “List” Interface over “Collection”
The additional operations supported by List interface over Collection interface are:
‰ Positional access manipulates elements based on their numerical position in the list.
‰ Search searches for a specified object in the list and returns its numerical position.
‰ Iteration extends Iterator semantics to take advantage of the sequential nature of the
list.
‰ Range-view performs arbitrary range operations on the list.
“List” Interface
public interface List<E> extends Collection<E> {
// Positional access
E get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
boolean addAll(int index,
Collection<? extends E> c); //optional
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// Range-view
List<E> subList(int from, int to);
}
Implementations of “List” Interface
The implementations of List interface are:
‰ ArrayList:
oOffers constant-time positional access
oGives you fast iteration and fast random access
oIt is an ordered collection (by index), but not sorted
oMost commonly used implementation
‰ LinkedList:You use it frequently to add elements to the beginning of the List or
iterate over the List to delete elements from its interior
“Map” Interface
‰ Map interface handles key or value pairs.
‰ A Map interface cannot contain duplicate keys. Each key can map to at most one
value.
“Map” Interface (Java SE 5)
public interface Map<K,V> {
// Basic operations
V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
// Bulk operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Collection Views
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();
// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
“SortedMap” Interface
‰ A Map interface that maintains its mappings in ascending key order is called the
SortedMap interface. This is the Map analog of SortedSet.
‰ Sorted maps are used for naturally ordered collections of key or value pairs, such as
dictionaries and telephone directories.
Implementations of “Map” Interface
The implementations of the Map interface are:
‰ HashMap:You use this if you want maximum speed and do not want to care about
iteration order. Most commonly used implementation.
‰ TreeMap:You use this when you need SortedMap operations or key-ordered
Collection-view iteration.
‰ LinkedHashMap:Although it will be somewhat slower than HashMap for adding and
removing elements, you can expect faster iteration with a LinkedHashMap.
“Queue” Interface
‰ Queue interface is a collection used to hold multiple elements prior to processing.
‰ Besides basic Collection operations, a Queue interface provides additional insertion,
extraction, and inspection operations.
‰ Typically, but do not necessarily, Queue interface order elements in a FIFO (First-In,
First-Out) manner.
Implementations of Queue Interface
General purpose Queue implementations:
‰ LinkedList implements the Queue interface,providing FIFO queue operations for add,
poll, and so on.
‰ PriorityQueue class is a priority queue based on the heap data structure.
‰ This queue orders elements according to an order specified at construction time,
which can be the natural ordering of the elements or the ordering imposed by an
explicit Comparator.
Implementations of Queue Interface
Concurrent Queue implementations:The java.util.concurrent package contains a set of
synchronized Queue interfaces and classes. BlockingQueue extends Queue with operations that
wait for the queue to become nonempty when retrieving an element and for space to become
available in the queue when storing an element. This interface is implemented by the following
classes:
‰ LinkedBlockingQueue:An optionally bounded FIFO blocking queue backed by
linked nodes
‰ ArrayBlockingQueue:A bounded FIFO blocking queue backed by an array
‰ PriorityBlockingQueue:An unbounded blocking priority queue backed by a heap
‰ DelayQueue:A time-based scheduling queue backed by a heap
‰ SynchronousQueue:A simple rendezvous mechanism that uses the BlockingQueue
interface
Abstract Classes
Abstract classes include the following abstract implementations:
‰ AbstractCollection
‰ AbstractSet
‰ AbstractList
‰ AbstractSequentialList
‰ AbstractMap
Routine Data Manipulation
The Collections class provides five algorithms for doing routine data manipulation on List objects:
‰ reverse reverses the order of the elements in a List
‰ fill overwrites every element in a List with the specified value and this operation is useful for reinitializing a List
‰ copy takes two arguments, namely a destination List and a source List, and copies the
elements of the source into the destination, overwriting its contents. The destination
List must be at least as long as the source. If it is longer, then the remaining elements
in the destination List are unaffected.
‰ swap swaps the elements at the specified positions in a List.
‰ addAll adds all the specified elements to a Collection. The elements to be added may
be specified individually or as an array.
Searching
The Collections class has binarySearch() method for searching a specified element in a sorted List
// Set up testing data
String name[] = {
new String("Sang"),
new String("Shin"),
new String("Boston"),
new String("Passion"),
new String("Shin"),
};
List l = Arrays.asList(name);
int position = Collections.binarySearch(l, "Boston");
System.out.println("Position of the searched item = " + position);
Composition
‰ Collections.frequency(l) counts the number of times the specified element occurs in
the specified collection.
‰ Collections.disjoint(l1, l2) determines whether two Collections are disjoint that is,
whether they contain no elements in common. The Collections class has
binarySearch() method for searching a specified element in a sorted List.
Try It Out
Problem Statement:
Write a program that illustrates the usage of Set interface and its implementation class namely
HashSet.
Code:
import java.util.*;
public class SetApp {
public static void main(String args[]) {
HashSet set = new HashSet();
set.add("This");
set.add("is");
set.add("is");
set.add("a");
set.add("a");
set.add(null);
set.add("test");
displaySet(set);
}
// continued …
Refer File Name: SetApp.javato obtain soft copy of the program code
How It Works:
‰ SetApp begins by creating a HashSet object and assigning it to the set variable. It then
adds the same elements to the set as ListApp did to its list.
‰ Note that because sets are not ordered, there are no addFirst() and addLast()
methods.
‰ The displaySet() method is invoked to display the set.
‰ When you run SetApp, it displays the following results:
The size of the set is: 5
This
is
a
null
test
‰ Note that the set does not allow duplicate elements, but allows the null value as an
element.
‰ The displaySet() method uses the size() method to determine the number of elements
in the set.
‰ It uses the iterator() method to create an Iterator object.
‰ The Iterator object is used to step through and display the elements of the set.
Tips and Tricks:
Provide the implementing classes in the collection interfaces for the data structures namely
HashTable, ResizableArray, BalancedTree, and LinkedList.
Solution:
Note:Some of the operations in the collection interfaces are optional, meaning that the
implementing class may choose not to provide a proper implementation of such an operation. In
such a case, an UnsupportedOperationException isthrown when that operation is invoked.
After completing this session, you will be able to:
‰ Set Interface and Implementations
‰ List Interface and Implementations
‰ Map Interface and Implementations
‰ Queue Interface and Implementations
‰ Define Abstract Classes
‰ Explain Routine Data Manipulation
‰ Describe Searching
‰ Define Composition
“Set” Interface
The Set interface is a collection that cannot contain duplicate elements.
The Set interface models the mathematical set abstraction and is used to represent sets:
‰ Cards comprising a poker hand
‰ Courses making up the schedule of a student
‰ The processes running on a machine
The Set interface contains only methods inherited from Collection and adds the restriction to
prohibit the duplicate elements.
“Set” Interface (Java SE 5)
public interface Set<E> extends Collection<E> {
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional
Iterator<E> iterator();
// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional
boolean removeAll(Collection<?> c); //optional
boolean retainAll(Collection<?> c); //optional
void clear(); //optional
// Array Operations
Object[] toArray();
<T> T[] toArray(T[] a);
}
“equals” Operation of Set Interface
Set also adds a stronger contract on the behavior of the equals and hashCode operations,
allowing Set instances to be compared meaningfullyeven if their implementation types differ. Two
Set instances are equal if theycontain the same elements.
“SortedSet” Interface
Sorted Set interface is a set that maintains its elements in ascending order. Several additional
operations are provided to take advantage of the ordering.
Sorted sets are used for naturally ordered sets, such as word lists and membership roll.
Implementations of “Set” Interface
The implementations of Set interface are:
‰ HashSet
‰ TreeSet
‰ LinkedHashSet
HashSet
‰ HashSet is much faster than TreeSet (constant-time versus log-time for most
operations) but offers no ordering guarantees.
‰ HashSet is the mostly commonly used implementation.
Caveats of Using HashSet
Iteration is linear in the sum of the number of entries and the number of buckets (the capacity):
‰ Choosing an initial capacity that is too high, can waste both space and time
‰ Choosing an initial capacity that is too low,wastes time by copying the data structure
each time it is forced to increase its capacity
Example: Set Interface and HashSet
public class MyOwnUtilityClass {
// Note that the first parameter type is set to
// Set interface not a particular implementation
// class such as HashSet. This makes the caller of
// this method to pass instances of different
// implementations of Set interface while
// this function picks up polymorphic behavior
// depending on the actual implementation type
// of the object instance passed.
public static void checkDuplicate(Set s, String[] args){
for (int i=0; i<args.length; i++)
if (!s.add(args[i])) {
System.out.println("Duplicate detected: "+args[i]);
}
System.out.println(s.size()+" distinct words detected:
"+s);
}
}
public class SetExample {
public static void main(String[] args) {
Set s = new HashSet(); // Order is not guaranteed
MyOwnUtilityClass.checkDuplicate(s, args);
s = new TreeSet(); // Order according to values
MyOwnUtilityClass.checkDuplicate(s, args);
s = new LinkedHashSet(); // Order according to insertion
MyOwnUtilityClass.checkDuplicate(s, args);
}
}
For example, the numbers 1, 2, 3, and 4 can be added in the following ways:
‰ Set type = java.util.HashSet [3, 2, 4, 1]
‰ Set type = java.util.TreeSet [1, 2, 3, 4]
‰ Set type = java.util.LinkedHashSet [2, 3, 4, 1]
TreeSet
‰ The TreeSet is one of two sorted collections (the other being TreeMap).
‰ No duplicates, iterates in sorted order.
‰ It generally guarantees that the elements will be in ascending order, according to
natural order.
Example: Set Interface and TreeSet
public static void main(String[] args) {
Set ts = new TreeSet();
ts.add("one");
ts.add("two");
ts.add("three");
ts.add("four");
ts.add("three");
System.out.println("Members from TreeSet = " + ts);
}
Result: Members from TreeSet = [four, one, three, two]
LinkedHashSet
‰ LinkedHashSet is implemented as a hash table with a linked list running through it.
‰ It provides insertion-ordered iteration (least recently inserted to most recently) and
runs nearly as fast as HashSet.
‰ It spares its clients from the unspecified, generally chaotic ordering provided by
HashSet without incurring the increased cost associated with TreeSet.
Example: Set Interface and LinkedHashSet
public static void main(String[] args) {
Set ts2 = new LinkedHashSet();
ts2.add(2);
ts2.add(1);
ts2.add(3);
ts2.add(3);
System.out.println("Members from LinkedHashSet = " + ts2);
}
Result: Members from LinkedHashSet = [2, 1, 3]
“List” Interface
‰ List interface is an ordered collection (sometimes called a sequence).
‰ Lists can contain duplicate elements.
‰ The user of a List interface generally has precise control over where in the each list
element is inserted and can access elements by their integer index (position).
Additional Operations Supported by “List” Interface over “Collection”
The additional operations supported by List interface over Collection interface are:
‰ Positional access manipulates elements based on their numerical position in the list.
‰ Search searches for a specified object in the list and returns its numerical position.
‰ Iteration extends Iterator semantics to take advantage of the sequential nature of the
list.
‰ Range-view performs arbitrary range operations on the list.
“List” Interface
public interface List<E> extends Collection<E> {
// Positional access
E get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
boolean addAll(int index,
Collection<? extends E> c); //optional
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// Range-view
List<E> subList(int from, int to);
}
Implementations of “List” Interface
The implementations of List interface are:
‰ ArrayList:
oOffers constant-time positional access
oGives you fast iteration and fast random access
oIt is an ordered collection (by index), but not sorted
oMost commonly used implementation
‰ LinkedList:You use it frequently to add elements to the beginning of the List or
iterate over the List to delete elements from its interior
“Map” Interface
‰ Map interface handles key or value pairs.
‰ A Map interface cannot contain duplicate keys. Each key can map to at most one
value.
“Map” Interface (Java SE 5)
public interface Map<K,V> {
// Basic operations
V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
// Bulk operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Collection Views
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();
// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
“SortedMap” Interface
‰ A Map interface that maintains its mappings in ascending key order is called the
SortedMap interface. This is the Map analog of SortedSet.
‰ Sorted maps are used for naturally ordered collections of key or value pairs, such as
dictionaries and telephone directories.
Implementations of “Map” Interface
The implementations of the Map interface are:
‰ HashMap:You use this if you want maximum speed and do not want to care about
iteration order. Most commonly used implementation.
‰ TreeMap:You use this when you need SortedMap operations or key-ordered
Collection-view iteration.
‰ LinkedHashMap:Although it will be somewhat slower than HashMap for adding and
removing elements, you can expect faster iteration with a LinkedHashMap.
“Queue” Interface
‰ Queue interface is a collection used to hold multiple elements prior to processing.
‰ Besides basic Collection operations, a Queue interface provides additional insertion,
extraction, and inspection operations.
‰ Typically, but do not necessarily, Queue interface order elements in a FIFO (First-In,
First-Out) manner.
Implementations of Queue Interface
General purpose Queue implementations:
‰ LinkedList implements the Queue interface,providing FIFO queue operations for add,
poll, and so on.
‰ PriorityQueue class is a priority queue based on the heap data structure.
‰ This queue orders elements according to an order specified at construction time,
which can be the natural ordering of the elements or the ordering imposed by an
explicit Comparator.
Implementations of Queue Interface
Concurrent Queue implementations:The java.util.concurrent package contains a set of
synchronized Queue interfaces and classes. BlockingQueue extends Queue with operations that
wait for the queue to become nonempty when retrieving an element and for space to become
available in the queue when storing an element. This interface is implemented by the following
classes:
‰ LinkedBlockingQueue:An optionally bounded FIFO blocking queue backed by
linked nodes
‰ ArrayBlockingQueue:A bounded FIFO blocking queue backed by an array
‰ PriorityBlockingQueue:An unbounded blocking priority queue backed by a heap
‰ DelayQueue:A time-based scheduling queue backed by a heap
‰ SynchronousQueue:A simple rendezvous mechanism that uses the BlockingQueue
interface
Abstract Classes
Abstract classes include the following abstract implementations:
‰ AbstractCollection
‰ AbstractSet
‰ AbstractList
‰ AbstractSequentialList
‰ AbstractMap
Routine Data Manipulation
The Collections class provides five algorithms for doing routine data manipulation on List objects:
‰ reverse reverses the order of the elements in a List
‰ fill overwrites every element in a List with the specified value and this operation is useful for reinitializing a List
‰ copy takes two arguments, namely a destination List and a source List, and copies the
elements of the source into the destination, overwriting its contents. The destination
List must be at least as long as the source. If it is longer, then the remaining elements
in the destination List are unaffected.
‰ swap swaps the elements at the specified positions in a List.
‰ addAll adds all the specified elements to a Collection. The elements to be added may
be specified individually or as an array.
Searching
The Collections class has binarySearch() method for searching a specified element in a sorted List
// Set up testing data
String name[] = {
new String("Sang"),
new String("Shin"),
new String("Boston"),
new String("Passion"),
new String("Shin"),
};
List l = Arrays.asList(name);
int position = Collections.binarySearch(l, "Boston");
System.out.println("Position of the searched item = " + position);
Composition
‰ Collections.frequency(l) counts the number of times the specified element occurs in
the specified collection.
‰ Collections.disjoint(l1, l2) determines whether two Collections are disjoint that is,
whether they contain no elements in common. The Collections class has
binarySearch() method for searching a specified element in a sorted List.
Try It Out
Problem Statement:
Write a program that illustrates the usage of Set interface and its implementation class namely
HashSet.
Code:
import java.util.*;
public class SetApp {
public static void main(String args[]) {
HashSet set = new HashSet();
set.add("This");
set.add("is");
set.add("is");
set.add("a");
set.add("a");
set.add(null);
set.add("test");
displaySet(set);
}
// continued …
Refer File Name: SetApp.javato obtain soft copy of the program code
How It Works:
‰ SetApp begins by creating a HashSet object and assigning it to the set variable. It then
adds the same elements to the set as ListApp did to its list.
‰ Note that because sets are not ordered, there are no addFirst() and addLast()
methods.
‰ The displaySet() method is invoked to display the set.
‰ When you run SetApp, it displays the following results:
The size of the set is: 5
This
is
a
null
test
‰ Note that the set does not allow duplicate elements, but allows the null value as an
element.
‰ The displaySet() method uses the size() method to determine the number of elements
in the set.
‰ It uses the iterator() method to create an Iterator object.
‰ The Iterator object is used to step through and display the elements of the set.
Tips and Tricks:
Provide the implementing classes in the collection interfaces for the data structures namely
HashTable, ResizableArray, BalancedTree, and LinkedList.
Solution:
Note:Some of the operations in the collection interfaces are optional, meaning that the
implementing class may choose not to provide a proper implementation of such an operation. In
such a case, an UnsupportedOperationException isthrown when that operation is invoked.
No comments:
Post a Comment