Computer Science 15-111 (Sec A+B), Spring 2007

ii. Collection framework = “a unified architecture for representing and manipulating collections, allowing them to be manipulated independently of the details of their representation.”

b. Advantages of a Collections Framework:

i. Reduces programming effort

ii. Increases performance

iii. Provides interoperability

iv. Reduces effort to learn API’s

v. Reduces effort to design and implement API’s

vi. Fosters software reuse

c. The Java Collections Framework consists of:

i. Collection interfaces

ii. Collection implementations

1. General-purpose

2. Legacy (Vector, Hashtable)

3. Special-purpose

4. Concurrent

5. Wrapper (such as for synchronization)

6. Convenience

7. Abstract (partial implementations)

iii. Algorithms (such as sorting a list)

iv. Infrastructure (such as iterator interfaces, and the RandomAccess interface)

v. Array Utilities

d. Collection Interfaces properties

i. Immutable / Unmodifiable (we will not distinguish these cases)

ii. Fixed-size or variable-sized

iii. Random-access or Sequential-access

iv. Element restrictions

1. Be of a particular type.

2. Be non-null.

3. Obey some arbitrary predicate.

e. Design Goals

i. Keep API small in size and “conceptual weight”

ii. Complement existing API’s

iii. Yet be powerful

iv. General API with optional methods

v. To keep it small, only include a method if either:

1. It is truly a “fundamental operation” or

2. There is a compelling performance reason why an important implementation would want to override it.

vi. Arrays

1. Cannot implement Collection interface without changing the language

2. Thus, include methods to:

a. Convert Collections into Arrays

b. View Arrays as Collections

f. General-Purpose Implementations

i. Support all optional operations

ii. Have no restrictions on elements

iii. Are unsynchronized (but can be used with synchronization wrappers)
Set s = Collections.synchronizedSet(new HashSet(...));

		Implementations
		Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List
Interfaces	Set	HashSet		TreeSet		LinkedHashSet
	List		ArrayList		LinkedList
	Map	HashMap		TreeMap		LinkedHashMap

2. In brief…

a. Iterable interface

b. Collection interface

c. List interface

d. Iterator interface

e. ListIterator interface

f. RandomAccess interface

g. Serializable interface

h. Cloneable interface

i. ArrayList

j. Vector

k. LinkedList

l. Stack

m. Queue interface (as LinkedList)

3. Sets

a. Set interface

i. A collection with no duplicate elements

ii. Behavior is undefined if elements are mutable

iii. A Java set may not contain itself

1. Aside: no worries about Russell’s Paradox

b. HashSet

i. Set backed by a HashMap (see below)

ii. Constant-time add, remove, contains (assuming a good hash function)

iii. Unordered (and order can change over time)

c. SortedSet interface

i. A set that further guarantees that its iterator will traverse the set in ascending element order

1. Natural order defined by Comparable; or

2. By a Comparator provided when the set is first created.

d. TreeSet

i. SortedSet backed by a TreeMap (see below)

ii. O(logn)-time add, remove, contains

iii. Stored in ascending order

4. Maps

a. Map interface

i. Map: An object that maps keys to values.

ii. A map cannot contain duplicate keys

iii. Each key can map to at most one value.

iv. Provides collection views over

1. keySet(): A set of keys,

2. values(): A collection of values, or

3. entrySet(): A set of key-value mappings.

v. Behavior is undefined if keys are mutable

vi. A Java map may not contain itself as a key

vii. But a Java map may contain itself as a value, but this is cautioned against.

b. HashMap

i. Map backed by a hash table.

ii. Constant-time get, put (assuming a good hash function)

iii. Unordered (and order can change over time)

iv. Instances have two parameters affecting performance

1. Initial Capacity

2. Load Factor

a. Rehash when (# of elements) > (capacity) x (load factor)

c. SortedMap interface

i. A map that further guarantees that its iterator will traverse the map in ascending key order

1. Natural order defined by Comparable; or

2. By a Comparator provided when the map is first created.

d. TreeMap

i. SortedMap backed by a (red-black) tree

1. Self-balancing binary search tree

2. See Wikipedia entry on Red-Black Trees
(Though you need not know much about them, at least not yet, beyond what is mentioned here.)

ii. O(logn)-time containsKey, get, put and remove

5. Collections class

6. Arrays class