Finals – M3: JCF & Using Iterators

You're about to review your notes on the Java Collections Framework (JCF). Without looking at your notes,
(1) what is the JCF generally, and
(2) what are the main topics covered in this lecture?

(1) The JCF is Java's built-in library of data structures and algorithms. It's Java's equivalent of the OSU CSE components.
(2) Main topics covered: the key interfaces and their hierarchy (Collection, Set, List, Queue, Map),
the concept of Views (for Map and List),
attributes of certain methods like remove and iterating over Map,
data structures and their interfaces (the 3-level pattern of Interface → Abstract Class → Concrete Class),
JCF algorithms via the Collections class,
and the 8 differences between OSU CSE components and JCF.

Draw out the JCF interface hierarchy from memory. Which interface sits at the top? Which one is NOT part of the Collection hierarchy but is still considered a "collection"?

(1) What is a "view" in the JCF?
(2) What are the three views available for Map?
(3) What does "backed by" mean and what interfaces does this mainly apply to?

(1) A view is a live window into a collection — not a copy, but a subcollection manipulated in place. Changes to the view affect the original and vice versa.
(2) The three Map views are:

• keySet() → Set<K> of just the keys

• values() → Collection<V> of just the values

• entrySet() → Set<Map.Entry<K,V>> of key-value pairs

(3) "Backed by" means the view and the original collection are linked — modifying one modifies the other. This mainly applies to Map (via its three views) and List (via subList()).

(1) Why can't you iterate over a Map directly in JCF?
(2) What are the three ways to iterate over a Map?
(3) What is the danger of calling m.values().remove(42) when multiple entries share the same value?

(1) Map does not extend Iterable, so you cannot use a for-each loop on it directly.
(2) You must iterate through one of its views:

• m.keySet() — iterate over keys

• m.values() — iterate over values

• m.entrySet() — iterate over key-value pairs

(3) Since remove on a Collection removes only one copy, you cannot control which key-value pair gets removed when multiple entries share the same value.

Data Structures & Their Interfaces (JCF):
What 3-level pattern do data structures’ interfaces follow in the JCF?

Each data structure follows a 3-level pattern: 

Interface (defines method contracts)  
  ↓ 
Abstract Class (provides default code for shared methods)  
  ↓  
Concrete Class (the actual usable class with full code) 

Define HashSet and TreeSet for the Set family

• HashSet — uses hashing. Fully implements add, remove, clear. Avoid using its clone 

• TreeSet — uses a balanced binary search tree. Use when you need elements in sorted order 

Define ArrayList and LinkedList for List Family

• ArrayList — backed by an array. Best for accessing elements by index 

• LinkedList — backed by a doubly-linked list. Best for frequent insertions/deletions 

Define HashMap and TreeMap for Map Family

• HashMap — uses hashing. General purpose, most commonly used 

• TreeMap — uses a balanced binary search tree. Use when you need keys in sorted order 

Note: Map does not extend Collection, it has its own separate hierarchy 

JCF Algorithms: Collections Class Q: (1) What is the Collections class and how is it different from the Collection interface?
(2) Name at least 5 methods it provides.
(3) What is the Arrays class and what does it offer?

A: (1) Collections is a class containing methods for processing collections. It does not implement the Collection interface — they are completely separate things despite the similar name.

(2) methods for processing Collections:

• sort — sorts a list

• reverse — reverses a list

• min / max — finds min or max element

• shuffle — randomly shuffles a list

• frequency — counts occurrences of an element

(3) Arrays has useful algorithms to process arrays like: sort, fill, equals, hashCode, and toString.

OSU CSE vs JCF: The 8 Differences

Q: What are the 8 differences between OSU CSE components and the JCF? Try to name all 8 from memory.

1. Level of Formalism — JCF uses informal Javadoc comments. OSU uses explicit mathematical models and requires/ensures clauses.

2. Parameter Modes — JCF has no parameter modes (restores, updates, etc.). OSU does.

3. Aliasing — JCF rarely mentions aliasing and doesn't try to avoid it. OSU does.

4. Null — JCF permits null values in collections. OSU doesn’t.

5. Optional Methods — JCF has "optional" methods that may throw UnsupportedOperationException. OSU requires all methods to behave correctly.

6. Copy Constructors — JCF has two standard constructors: a no-argument constructor and a conversion constructor that copies references from another collection. OSU doesn’t.

7. Exceptions — JCF throws specific exceptions for precondition violations (e.g. NoSuchElementException). OSU checks assert.

8. Kernel Methods — JCF puts all methods in a single interface. OSU separates "kernel" methods and layered methods.

Basic rule when changing Set/Map entries
(for both OSU & JCF)

NEVER change entries in a Set or keys in a Map directly. MUST do it through aliases

OSU Iterator Rule

When iterating over a collection (for-each loop or explicit iterator): don't touch anything

• Don't call any methods on the collection

• Don't change the value of any elements inside it

JCF Iterator Rule

behavior is unspecified if you modify the collection during iteration EXCEPT through the iterator's own remove method.

The only two safe ways to modify a Map during iteration are:

1. Iterator.remove() — works with all three views (keySet(), values(), entrySet()). Removes the associated entry from the backing Map

2. Map.Entry.setValue() — only works with the entrySet() view. Lets you change the value associated with a key during iteration