OOP: Collections 1
Collections in Java
• Arrays n Has special language support • Iterators n Iterator (i) • Collections (also called containers) n Collection (i) n Set (i), u HashSet (c), TreeSet (c) n List (i), u ArrayList (c), LinkedList (c) n Map (i), u HashMap (c), TreeMap (c)
OOP: Collections 2
Array • Most efficient way to hold references to objects.
• Advantages n An array know the type it holds, i.e., compile-time type checking. n An array know its size, i.e., ask for the length. n An array can hold primitive types directly. • Disadvantages n An array can only hold one type of objects (including primitives). n Arrays are fixed size.
2
Car 3 4 5
Car 6 7
Car 1
Car 0index data
OOP: Collections 3
Array, Example
• Helper class java.util.Arrays n Search and sort: binarySearch(), sort() n Comparison: equals() (many overloaded) n Instantiation: fill() (many overloaded) n Conversion: asList()
class Car{}; // minimal dummy class Car[] cars1; // null reference Car[] cars2 = new Car[10]; // null references
for (int i = 0; i < cars2.length; i++) cars2[i] = new Car();
// Aggregated initialization Car[] cars3 = {new Car(), new Car(), new Car(), new Car()}; cars1 = {new Car(), new Car(), new Car()};
OOP: Collections 4
Overview of Collection • A collection is a group of data manipulate as a single object. Corresponds to a bag.
• Insulate client programs from the implementation. n array, linked list, hash table, balanced binary tree • Like C++'s Standard Template Library (STL) • Can grow as necessary. • Contain only Objects (reference types). • Heterogeneous. • Can be made thread safe (concurrent access). • Can be made not-modifiable.
OOP: Collections 5
Collection Interfaces • Collections are primarily defined through a set of interfaces. n Supported by a set of classes that implement the interfaces
• Interfaces are used of flexibility reasons n Programs that uses an interface is not tightened to a specific implementation of a collection. n It is easy to change or replace the underlying collection class with another (more efficient) class that implements the same interface.
[Source: java.sun.com]
OOP: Collections 6
Collection Interfaces and Classes
[Source: bruceeckel.com]
OOP: Collections 7
The Iterator Interface • The idea: Select each element in a collection n Hide the underlying collection
Iterator hasNext() next() remove()
Collection isEmpty() add() remove() ...
list
• Iterators are fail-fast n Exception thrown if collection is modified externally, i.e., not via the iterator (multi-threading).
OOP: Collections 8
The Iterator Interface, cont.
// an example public static void main (String[] args){ ArrayList cars = new ArrayList(); for (int i = 0; i < 12; i++) cars.add (new Car());
Iterator it = cats.iterator(); while (it.hasNext()) System.out.println ((Car)it.next());
}
// the interface definition Interface Iterator { boolean hasNext(); Object next(); // note "one-way" traffic void remove(); }
OOP: Collections 9
The Collection Interface
public interface Collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator();
// Bulk Operations boolean containsAll(Collection c); boolean addAll(Collection c); // Optional boolean removeAll(Collection c); // Optional boolean retainAll(Collection c); // Optional void clear(); // Optional
// Array Operations Object[] toArray(); Object[] toArray(Object a[]); }
OOP: Collections 10
The Set Interface • Corresponds to the mathematical definition of a set (no duplicates are allowed).
• Compared to the Collection interface n Interface is identical. n Every constructor must create a collection without duplicates. n The operation add cannot add an element already in the set. n The method call set1.equals(set2) works at follows u set1 ⊆ set2, and set2 ⊆ set1
OOP: Collections 11
Set Idioms
• set1 ∪ set2 n set1.addAll(set2) • set1 ∩ set2 n set1.retainAll(set2) • set1 − set2 n set1.removeAll(set2)
OOP: Collections 12
HashSet and TreeSet Classes • HashSet and TreeSet implement the interface Set.
• HashSet n Implemented using a hash table. n No ordering of elements. n add, remove, and contains methods constant time complexity O(c).
• TreeSet n Implemented using a tree structure. n Guarantees ordering of elements. n add, remove, and contains methods logarithmic time complexity O(log (n)), where n is the number of elements in the set.
OOP: Collections 13
HashSet, Example
// [Source: java.sun.com] import java.util.*; public class FindDups { public static void main(String args[]){ Set s = new HashSet(); 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); } }
OOP: Collections 14
The List Interface • The List interface corresponds to an order group of elements. Duplicates are allowed.
• Extensions compared to the Collection interface n Access to elements via indexes, like arrays u add (int, Object), get(int), remove(int), set(int, Object) (note set = replace bad name for the method) n Search for elements u indexOf(Object), lastIndexOf(Object) n Specialized Iterator, call ListIterator n Extraction of sublist u subList(int fromIndex, int toIndex)
OOP: Collections 15
The List Interface, cont. Further requirements compared to the Collection Interface • add(Object)adds at the end of the list. • remove(Object)removes at the start of the list. • list1.equals(list2)the ordering of the elements is taken into consideration. • Extra requirements to the method hashCode. n list1.equals(list2) implies that list1.hashCode()==list2.hashCode()
OOP: Collections 16
The List Interface, cont.
public interface List extends Collection { // Positional Access Object get(int index); Object set(int index, Object element); // Optional void add(int index, Object element); // Optional Object remove(int index); // Optional abstract boolean addAll(int index, Collection c); // Optional
// Search int indexOf(Object o); int lastIndexOf(Object o);
// Iteration ListIterator listIterator(); ListIterator listIterator(int index);
// Range-view List subList(int from, int to); }
OOP: Collections 17
ArrayList and LinkedList Classes • The classes ArrayList and LinkedList implement the List interface.
• ArrayList is an array based implementation where elements can be accessed directly via the get and set methods. n Default choice for simple sequence.
• LinkedList is based on a double linked list n Gives better performance on add and remove compared to ArrayList. n Gives poorer performance on get and set methods compared to ArrayList.
OOP: Collections 18
ArrayList, Example
// [Source: java.sun.com] import java.util.*;
public class Shuffle { public static void main(String args[]) { List l = new ArrayList(); for (int i = 0; i < args.length; i++) l.add(args[i]); Collections.shuffle(l, new Random()); System.out.println(l); } }
OOP: Collections 19
LinkedList, Example
import java.util.*; public class MyStack { private LinkedList list = new LinkedList(); public void push(Object o){ list.addFirst(o); } public Object top(){ return list.getFirst(); } public Object pop(){ return list.removeFirst(); }
public static void main(String args[]) { Car myCar; MyStack s = new MyStack(); s.push (new Car()); myCar = (Car)s.pop(); } }
OOP: Collections 20
The ListIterator Interface
public interface ListIterator extends Iterator { boolean hasNext(); Object next();
boolean hasPrevious(); Object previous();
int nextIndex(); int previousIndex();
void remove(); // Optional void set(Object o); // Optional void add(Object o); // Optional }
OOP: Collections 21
The Map Interface • A Map is an object that maps keys to values. Also called an associative array or a dictionary.
• Methods for adding and deleting n put(Object key, Object value) n remove (Object key) • Methods for extraction objects n get (Object key) • Methods to retrieve the keys, the values, and (key, value) pairs n keySet() // returns a Set n values() // returns a Collection, n entrySet() // returns a set
OOP: Collections 22
The MAP Interface, cont. public interface Map { // Basic Operations Object put(Object key, Object value); Object get(Object key); Object remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk Operations void putAll(Map t); void clear(); // Collection Views public Set keySet(); public Collection values(); public Set entrySet(); // Interface for entrySet elements public interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); } }
OOP: Collections 23
HashMap and TreeMap Classes • The HashMap and HashTree classes implement the Map interface.
• HashMap n The implementation is based on a hash table. n No ordering on (key, value) pairs.
• TreeMap n The implementation is based on red-black tree structure. n (key, value) pairs are ordered on the key.
OOP: Collections 24
HashMap, Example
import java.util.*;
public class Freq { private static final Integer ONE = new Integer(1); public static void main(String args[]) { Map m = new HashMap();
// Initialize frequency table from command line for (int i=0; i < args.length; i++) { Integer freq = (Integer) m.get(args[i]); m.put(args[i], (freq==null ? ONE : new Integer(freq.intValue() + 1))); }
System.out.println(m.size()+ " distinct words detected:"); System.out.println(m); } }
OOP: Collections 25
Static Methods on Collections • Collection n Search and sort: binarySearch(), sort() n Reorganization: reverse(), shuffle() n Wrappings: unModifiableCollection, synchonizedCollection
OOP: Collections 26
Collection Advantages and Disadvantages Advantages • Can hold different types of objects. • Resizable Disadvantages • Must cast to correct type • Cannot do compile-time type checking.
OOP: Collections 27
Summary
• Array n Holds objects of known type. n Fixed size.
• Collections n Generalization of the array concept. n Set of interfaces defined in Java for storing object. n Multiple types of objects. n Resizable.
• Queue, Stack, Deque classes absent n Use LinkedList.
Collections in Java
• Arrays n Has special language support • Iterators n Iterator (i) • Collections (also called containers) n Collection (i) n Set (i), u HashSet (c), TreeSet (c) n List (i), u ArrayList (c), LinkedList (c) n Map (i), u HashMap (c), TreeMap (c)
OOP: Collections 2
Array • Most efficient way to hold references to objects.
• Advantages n An array know the type it holds, i.e., compile-time type checking. n An array know its size, i.e., ask for the length. n An array can hold primitive types directly. • Disadvantages n An array can only hold one type of objects (including primitives). n Arrays are fixed size.
2
Car 3 4 5
Car 6 7
Car 1
Car 0index data
OOP: Collections 3
Array, Example
• Helper class java.util.Arrays n Search and sort: binarySearch(), sort() n Comparison: equals() (many overloaded) n Instantiation: fill() (many overloaded) n Conversion: asList()
class Car{}; // minimal dummy class Car[] cars1; // null reference Car[] cars2 = new Car[10]; // null references
for (int i = 0; i < cars2.length; i++) cars2[i] = new Car();
// Aggregated initialization Car[] cars3 = {new Car(), new Car(), new Car(), new Car()}; cars1 = {new Car(), new Car(), new Car()};
OOP: Collections 4
Overview of Collection • A collection is a group of data manipulate as a single object. Corresponds to a bag.
• Insulate client programs from the implementation. n array, linked list, hash table, balanced binary tree • Like C++'s Standard Template Library (STL) • Can grow as necessary. • Contain only Objects (reference types). • Heterogeneous. • Can be made thread safe (concurrent access). • Can be made not-modifiable.
OOP: Collections 5
Collection Interfaces • Collections are primarily defined through a set of interfaces. n Supported by a set of classes that implement the interfaces
• Interfaces are used of flexibility reasons n Programs that uses an interface is not tightened to a specific implementation of a collection. n It is easy to change or replace the underlying collection class with another (more efficient) class that implements the same interface.
[Source: java.sun.com]
OOP: Collections 6
Collection Interfaces and Classes
[Source: bruceeckel.com]
OOP: Collections 7
The Iterator Interface • The idea: Select each element in a collection n Hide the underlying collection
Iterator hasNext() next() remove()
Collection isEmpty() add() remove() ...
list
• Iterators are fail-fast n Exception thrown if collection is modified externally, i.e., not via the iterator (multi-threading).
OOP: Collections 8
The Iterator Interface, cont.
// an example public static void main (String[] args){ ArrayList cars = new ArrayList(); for (int i = 0; i < 12; i++) cars.add (new Car());
Iterator it = cats.iterator(); while (it.hasNext()) System.out.println ((Car)it.next());
}
// the interface definition Interface Iterator { boolean hasNext(); Object next(); // note "one-way" traffic void remove(); }
OOP: Collections 9
The Collection Interface
public interface Collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator();
// Bulk Operations boolean containsAll(Collection c); boolean addAll(Collection c); // Optional boolean removeAll(Collection c); // Optional boolean retainAll(Collection c); // Optional void clear(); // Optional
// Array Operations Object[] toArray(); Object[] toArray(Object a[]); }
OOP: Collections 10
The Set Interface • Corresponds to the mathematical definition of a set (no duplicates are allowed).
• Compared to the Collection interface n Interface is identical. n Every constructor must create a collection without duplicates. n The operation add cannot add an element already in the set. n The method call set1.equals(set2) works at follows u set1 ⊆ set2, and set2 ⊆ set1
OOP: Collections 11
Set Idioms
• set1 ∪ set2 n set1.addAll(set2) • set1 ∩ set2 n set1.retainAll(set2) • set1 − set2 n set1.removeAll(set2)
OOP: Collections 12
HashSet and TreeSet Classes • HashSet and TreeSet implement the interface Set.
• HashSet n Implemented using a hash table. n No ordering of elements. n add, remove, and contains methods constant time complexity O(c).
• TreeSet n Implemented using a tree structure. n Guarantees ordering of elements. n add, remove, and contains methods logarithmic time complexity O(log (n)), where n is the number of elements in the set.
OOP: Collections 13
HashSet, Example
// [Source: java.sun.com] import java.util.*; public class FindDups { public static void main(String args[]){ Set s = new HashSet(); 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); } }
OOP: Collections 14
The List Interface • The List interface corresponds to an order group of elements. Duplicates are allowed.
• Extensions compared to the Collection interface n Access to elements via indexes, like arrays u add (int, Object), get(int), remove(int), set(int, Object) (note set = replace bad name for the method) n Search for elements u indexOf(Object), lastIndexOf(Object) n Specialized Iterator, call ListIterator n Extraction of sublist u subList(int fromIndex, int toIndex)
OOP: Collections 15
The List Interface, cont. Further requirements compared to the Collection Interface • add(Object)adds at the end of the list. • remove(Object)removes at the start of the list. • list1.equals(list2)the ordering of the elements is taken into consideration. • Extra requirements to the method hashCode. n list1.equals(list2) implies that list1.hashCode()==list2.hashCode()
OOP: Collections 16
The List Interface, cont.
public interface List extends Collection { // Positional Access Object get(int index); Object set(int index, Object element); // Optional void add(int index, Object element); // Optional Object remove(int index); // Optional abstract boolean addAll(int index, Collection c); // Optional
// Search int indexOf(Object o); int lastIndexOf(Object o);
// Iteration ListIterator listIterator(); ListIterator listIterator(int index);
// Range-view List subList(int from, int to); }
OOP: Collections 17
ArrayList and LinkedList Classes • The classes ArrayList and LinkedList implement the List interface.
• ArrayList is an array based implementation where elements can be accessed directly via the get and set methods. n Default choice for simple sequence.
• LinkedList is based on a double linked list n Gives better performance on add and remove compared to ArrayList. n Gives poorer performance on get and set methods compared to ArrayList.
OOP: Collections 18
ArrayList, Example
// [Source: java.sun.com] import java.util.*;
public class Shuffle { public static void main(String args[]) { List l = new ArrayList(); for (int i = 0; i < args.length; i++) l.add(args[i]); Collections.shuffle(l, new Random()); System.out.println(l); } }
OOP: Collections 19
LinkedList, Example
import java.util.*; public class MyStack { private LinkedList list = new LinkedList(); public void push(Object o){ list.addFirst(o); } public Object top(){ return list.getFirst(); } public Object pop(){ return list.removeFirst(); }
public static void main(String args[]) { Car myCar; MyStack s = new MyStack(); s.push (new Car()); myCar = (Car)s.pop(); } }
OOP: Collections 20
The ListIterator Interface
public interface ListIterator extends Iterator { boolean hasNext(); Object next();
boolean hasPrevious(); Object previous();
int nextIndex(); int previousIndex();
void remove(); // Optional void set(Object o); // Optional void add(Object o); // Optional }
OOP: Collections 21
The Map Interface • A Map is an object that maps keys to values. Also called an associative array or a dictionary.
• Methods for adding and deleting n put(Object key, Object value) n remove (Object key) • Methods for extraction objects n get (Object key) • Methods to retrieve the keys, the values, and (key, value) pairs n keySet() // returns a Set n values() // returns a Collection, n entrySet() // returns a set
OOP: Collections 22
The MAP Interface, cont. public interface Map { // Basic Operations Object put(Object key, Object value); Object get(Object key); Object remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk Operations void putAll(Map t); void clear(); // Collection Views public Set keySet(); public Collection values(); public Set entrySet(); // Interface for entrySet elements public interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); } }
OOP: Collections 23
HashMap and TreeMap Classes • The HashMap and HashTree classes implement the Map interface.
• HashMap n The implementation is based on a hash table. n No ordering on (key, value) pairs.
• TreeMap n The implementation is based on red-black tree structure. n (key, value) pairs are ordered on the key.
OOP: Collections 24
HashMap, Example
import java.util.*;
public class Freq { private static final Integer ONE = new Integer(1); public static void main(String args[]) { Map m = new HashMap();
// Initialize frequency table from command line for (int i=0; i < args.length; i++) { Integer freq = (Integer) m.get(args[i]); m.put(args[i], (freq==null ? ONE : new Integer(freq.intValue() + 1))); }
System.out.println(m.size()+ " distinct words detected:"); System.out.println(m); } }
OOP: Collections 25
Static Methods on Collections • Collection n Search and sort: binarySearch(), sort() n Reorganization: reverse(), shuffle() n Wrappings: unModifiableCollection, synchonizedCollection
OOP: Collections 26
Collection Advantages and Disadvantages Advantages • Can hold different types of objects. • Resizable Disadvantages • Must cast to correct type • Cannot do compile-time type checking.
OOP: Collections 27
Summary
• Array n Holds objects of known type. n Fixed size.
• Collections n Generalization of the array concept. n Set of interfaces defined in Java for storing object. n Multiple types of objects. n Resizable.
• Queue, Stack, Deque classes absent n Use LinkedList.
No comments:
Post a Comment