Collections Java Collections Framework

• A collection (called a container in C++) is an – Algorithms: methods that perform useful

object that groups multiple elements into a computations, like searching and sorting,
single unit. on objects that implement collection
• Collections are used to store, retrieve and interfaces.
manipulate data, and to transmit data from
• Algorithms are said to be polymorphic
one method to another.
because the same method can be used on
• Collections hold: many different implementations of the
– A specific data type appropriate collections interface.
– A generic data type
• Reusable functionality.

Java Collections Framework Java Collections Framework

• The Java Collections Framework provides – Provided in java.util package.
– Interfaces: abstract data types representing – This is known as the Standard Template
collections.
• allow collections to be manipulated independently of
Library (STL) in C++.
the details of their representation.
– Implementations: concrete implementations of
the collection interfaces.
• reusable data structures.

1
 Why Use It? Sets
• A group of unique items.
• There are many benefits to using the Java – the group contains no duplicates
Collections Framework: • Some examples
– Reduces programming effort. – The set of uppercase letters ‘A’ through ‘Z’
– Increases program speed and quality. – The set of nonnegative integers { 0, 1, 2, … }
– Allows interoperability among unrelated APIs. – The empty set {}
– Reduces the effort to learn and use new APIs. • The basic properties of sets
– Reduces effort to design new APIs. – Contain only one instance of each item
– Fosters software reuse. – May be finite or infinite
– Can define abstract concepts

The Interfaces Sets

• When are two sets equal?
– Is {1, 2, 3} == {1, 3, 4} ?
– Is {A, a, c} == {A, a, c} ?

Note: Some of the material on these slides was taken from the Java
Tutorial at http://www.java.sun.com/docs/books/tutorial

2
 Other Types of Sets Lists
– HashSet: implements the Set interface, backed • An ordered collection of elements.
by a hash table.
• May contain duplicates.
• does not guarantee that the order will remain
constant over time. • Elements are accessed with regard to
• Near constant time performance. their position in the list.
• Capacity – number of buckets in the hash table
• First element is index zero.
• Load factor – Ratio of number of elements stored to
the tables current capacity.

Other Types of Sets Maps

– TreeSet: implements the Set interface, • A map is a special kind of set.
backed by a TreeMap instance. – A set of pairs, each pair mapping from a set of
• guarantees that the sorted set will be in key objects to a set of value objects.
ascending element order.
• A TreeMap is a Red-Black tree implementation
– Each key maps to one value.
of the SortedMap interface. • Only one key but possibly multiple values.
• Some examples
– A map of keys to database records
– A dictionary (words mapped to meanings)
– The conversion from base 2 to base 10

3
 What Is The Real Difference? The Collection Interface
• Collections • Optional methods throw
– You can add, remove, lookup isolated items in UnsupportedOperationException if the implementing
the collection. class does not support the operation.
• Maps • Bulk operations perform some operation on an
– The collection operations are available but they entire Collection in a single shot
work with a key-value pair instead of an • The toArray methods allow the contents of a
isolated element. Collection to be translated into an array.
– The typical use of a Map is to provide access to
values stored by key.

Collection
Another Way to Look At It // Basic Operations
size():int;
isEmpty():boolean;
contains(Object):boolean;
• The Collection interface is a group of add(Object):boolean; // Optional
remove(Object):boolean; // Optional
objects, with duplicates allowed. iterator():Iterator;
• Set extends Collection but forbids duplicates.
// Bulk Operations
• List extends Collection and allows duplicates containsAll(Collection):boolean;
addAll(Collection):boolean; // Optional
and positional indexing. removeAll(Collection):boolean;// Optional
• Map extends neither Set nor Collection. retainAll(Collecton):boolean; // Optional
clear():void; // Optional

// Array Operations
toArray():Object[];
toArray(Object[]):Object[];

4
 Set Interface More on Lists
• A Set is a Collection that does not contain • In addition to the operations inherited from
duplicate elements. Collection, the List interface includes
– Set models the mathematical set abstraction. operations for:
• The Set interface extends Collection and – Positional Access
contains no methods other than those – Search
inherited from Collection. – List Iteration
– Range-view

List
Set Bulk Operations // Positional Access
get(int):Object;
set(int,Object):Object; // Optional
• The bulk operations perform standard set- Do NOT use the add(int, Object):void; // Optional
remove(int index):Object; // Optional
algebraic operations. Suppose s1 and s2 are Vector class! addAll(int, Collection):boolean; // Optional
Sets.
// Search
– s1.containsAll(s2): Returns true if s2 is a subset int indexOf(Object);
of s1. int lastIndexOf(Object);

– s1.addAll(s2): Transforms s1 into the union of s1 // Iteration

listIterator():ListIterator;
and s2. listIterator(int):ListIterator;
– s1.retainAll(s2): Transforms s1 into the
// Range-view List
intersection of s1 and s2. subList(int, int):List;

5
 Map Interface
Map Examples
// Basic Operations
put(Object, Object):Object;
get(Object):Object; • HashSet Example – UniqueWordsHash.java
remove(Object):Object;
containsKey(Object):boolean; • Sorted output order:
containsValue(Object):boolean; EntrySet
size():int; – Using TreeSet – UniqueWordsTree.java
getKey():Object;
isEmpty():boolean;
getValue():Object; – Using HashSet – UniqueWordsHashOrdered.java
setValue(Object):Object;
// Bulk Operations
void putAll(Map t):void;
void clear():void; • All of the above use the file testFile.txt.
// Collection Views
keySet():Set;
values():Collection;
entrySet():Set;

Implementation Classes Iterator

Interface Implementation Historical • An object that
Set HashSet TreeSet implements the Iterator
interface generates a
List ArrayList LinkedList Vector series of elements, one Iterator
Stack at a time hasNext():boolean;
Map HashMap TreeMap HashTable – Successive calls to the next():Object;
Properties next() method returns remove():void;
successive elements of
the series.
Note: When writing programs think about interfaces and not
• The remove() method
implementations. This way the program does not become dependent on
any added methods in a given implementation, leaving the programmer
removes from the
with the freedom to change implementations. underlying Collection the
last element that was
returned by next.

6
 Examples
• Iterators – UniqueWordsIter.java
• Maps – UniqueWordsMap.java

• All of the above use the file testFile.txt.