© Luxoft Training 2013 Java Collections Framework

© Luxoft Training 2013 Collections Many programs need to keep track of groups of related data items Arrays have some limitations: You cannot change the size of an array after construction Arrays provide very simple mechanism for storing and accessing the data 4-2 Introduction

© Luxoft Training 2013 Collections Complex data structures are created with the help of Java Collections Framework Collections are a mechanism for manipulating object references. Arrays are capable of storing primitives or references, collections are not. 4-3 Introduction

© Luxoft Training 2013 Collections The central interfaces of Java Collection Framework are: java.util.Collection java.utils.List (extends java.util.Collection ) java.utils.Set (extends java.util.Collection ) java.utils.Map (does not extend java.util.Collection ) 4-4 Introduction

© Luxoft Training 2013 Collections 4-5 Hierarchy of central interfaces

© Luxoft Training 2013 Collections 4-6 Hierarchy of central interfaces

© Luxoft Training 2013 Collections The java.util.Collection interface is a core interface in the hierarchy Collection is a group of objects called as elements Some collections allow duplicate elements and others do not Some are ordered and others are unordered 4-7 The java.util.Collection interface

© Luxoft Training 2013 Collections 4-8 The java.util.Collection interface

© Luxoft Training 2013 Collections java.util.Collection extends interface java.util.Iterable that defines the iterator() method This method returns the instance of java.util.Iterator Iterator allows to sort the elements of the collection and takes the place of the legacy class Enumeration that was used with the same purpose 4-9 The java.util.Iterator interface

© Luxoft Training 2013 Collections boolean hasNext() returns true if there are more elements Object next() returns the next element void remove() removes the last element returned by next() Safe way of removing elements during the iteration 4-10 The java.util.Iterator interface

© Luxoft Training 2013 Collections 4-11 The java.util.Iterator interface public void dumpCollection(Collection c) { System.out.println("Collection has" + c.size() + " elements."); Iterator iter = c.iterator(); while (iter.hasNext()) { Object elem = iter.next() System.out.println("Next element is" + elem); if (getClause(elem)) { iter.remove(); }

© Luxoft Training 2013 Collections A List keeps it elements in the order in which they were added Each element of a List has an index, starting from 0 List is something like an array that grows as needed 4-12 The java.util.List interface

© Luxoft Training 2013 Collections 4-13 Additional java.util.List methods

© Luxoft Training 2013 Collections 4-14 java.util.List implementations ArrayList – array-based list implementation Quick search Slow growth, because array have to be copied for the growth Slow removal, because array have to be

© Luxoft Training 2013 ArrayList: add an element

© Luxoft Training 2013 ArrayList: insert an element

© Luxoft Training 2013 Collections java.util.LinkedList is a double- linked list implementation Slow search Quick growth, as new elements can be added without recopying right in the end of a queue 4-17 java.util.List implementations

© Luxoft Training 2013 LinkedList

© Luxoft Training 2013 LinkedList: add an element

© Luxoft Training 2013 LinkedList: add to the middle of the list

© Luxoft Training 2013 Example: LinkedOrArrayListTutor Collections 4-21

© Luxoft Training 2013 Time of work for arrayList add(): 55 1 bln. Time of work for linkedList add(): 2481 bln. Time of work for arrayList get(): 1100 thousands. Time of work for linkedList get(): thousands. Time of work for arrayList remove(): Time of work for linkedList remove(): Time of work for arrayList insert in the middle: Time of work for linkedList insert in the middle: Time of work for arrayList contains(): Time of work for linkedList contains(): Comparision of ArrayList and LinkedList iterations

© Luxoft Training 2013 Collections Sets have no concept of order Sets may not contain duplicate elements 4-23 The java.util.Set interface

© Luxoft Training 2013 Collections If you try to add an object to a Set that already contains that object, the add() call will return false and the Set will not be changed Sets use the equals() method, not the == operator, to check for duplication of elements 4-24 The java.util.Set interface

© Luxoft Training 2013 Collections 4-25 The java.util.Set interface

© Luxoft Training 2013 Collections No matter how many elements a HashSet contains, it basic operations will always execute in constant time HashSet stores elements in buckets grouped by hashCode() value 4-26 java.util.HashSet implementation

© Luxoft Training 2013 HashSet

© Luxoft Training 2013 Collections The java.util.TreeSet implementation guarantees that elements enumerated by iterator() will always be presented in sorted order Amount of time required to access elements is log(n), where n is the number of elements in the set 4-28 java.util.TreeSet implementation

© Luxoft Training 2013 Collections The java.util.SortedSet interface extends java.util.Se t and presents sorted set of elements Elements added to such a set are resorted; java.util.SortedSet allows to receive elements in a certain order 4-29 java.util.TreeSet implementation

© Luxoft Training 2013 TreeSet: binary tree Collections balanced treeunbalanced tree

© Luxoft Training 2013 TreeSet: Red-black tree Collections Self-balancing binary tree

© Luxoft Training 2013 Collections 4-32 The java.util.SortedSet methods

© Luxoft Training 2013 Example: CollectionTutor Collections 4-33

© Luxoft Training 2013 Example: CollectionRemoveTutor Collections 4-34

© Luxoft Training 2013 Collections As far as TreeSet class supports elements sorting it needs the mechanism that would allow to compare two objects The following interfaces can be used for comparison: java.lang.Comparable java.util.Comparator 4-35 Compare elements

© Luxoft Training 2013 Collections java.lang.Comparable defines public int compareTo(Object x) method returns a positive number if the current object is greater than х and a negative number if the current object isless than х, and 0 if the current object is equal to х 4-36 Java.lang.Comparable

© Luxoft Training 2013 Collections All elements inserted to java.util.TreeSet must implement the Comparable java.util.TreeSet allows for any Object subclass to be inserted. However, if the element doesnt implement Comparable the runtime will throw ClassCastException 4-37 Java.lang.Comparable

© Luxoft Training 2013 Collections Many Core Java classes implement Comparable (String, Date, Integer) Implementation of Comparable must define so called natural ordering For instance, lexicographical order for strings 4-38 Java.lang.Comparable

© Luxoft Training 2013 Collections For the Student class the natural order is not so evident, as students can be sorted by names, last names, grades, year of enrollment, etc. When natural order cant be used or some other way of elements comparison is needed use java.util.Comparator 4-39 Java.lang.Comparable

© Luxoft Training 2013 Collections You can also define a class implementing the java.util. Comparator interface that compares objects of the given type Corresponding Comparator can be passed to TreeSet using special constructor int compare(Object o1, Object o2) compares two objects 4-40 java.lang.Comparator

© Luxoft Training 2013 Collections 4-41 java.lang.Comparator

© Luxoft Training 2013 Example: ComparableTutor Collections java.lang.Comparator 4-42

© Luxoft Training 2013 Collections java.util.Map combines two collections, called keys and values Map associates exactly one value (it can be null ) with each key Each key is used in Map only once Good example is a dictionary 4-43 The java.util.Map interface

© Luxoft Training 2013 Collections 4-44 The java.util.Map interface

© Luxoft Training 2013 Collections 4-45 java.util.Map implementations

© Luxoft Training 2013 Collections java.util.HashMap iterates keys in an unpredictable order. Keys are quickly accessed The hashCode() method must be overridden and must return uniformly distinct integers The equals() method is used to check if the elements are equal (not ==) 4-46 java.util.Map implementations

© Luxoft Training 2013 With use of indexFor (hash, tableLength), defined the position in the array, where element will be put: static int indexFor ( int h, int length) { return h & (length - 1); } Collections Interior of HashMap cell address hash code 5345 hash code 5345 key object length – amount of cells

© Luxoft Training 2013 Collections Interior of HashMap With a large number of elements one bucket accumulates a lot of values, which reduces the efficiency of HashMap. Storage initialization in constructor. Capacity has initial value 16

© Luxoft Training 2013 Collections HashMap: rehashing loadFactor load coefficient. Default value 0.75 is a good compromise between access time and volume of the stored data; threshold Maximal number of elements at which the size of hash table is increased in 2 times. Calculated using formula (capacity * loadFactor);

© Luxoft Training 2013 Collections HashMap: rehashing void resize(int newCapacity) { Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } The method of transfer() iterates over all the elements, recounts their indices (based on the new size) and redistributes the elements to the new array.

© Luxoft Training 2013 HashMap: removing elements Collections A HashMap has the same "problem" as ArrayList – on delete the array size table[] is not reduced. ArrayList method provides trimToSize() method, but HashMap does not have such method.

© Luxoft Training 2013 Collections java.util.TreeMap iterates keys in natural order. Implements the java.util.SortedMap interface Keys must implement the java.lang.Comparable interface Or pass the instance of java.util.Comparator to HashMap constructor 4-52 java.util.Map implementations

© Luxoft Training 2013 Collections Interface java.util.SortedMap extends java.util.Map 4-53 Интерфейс java.util.SortedMap

© Luxoft Training 2013 Collections 4-54 Example

© Luxoft Training 2013 Example: MapTutor Collections java.util.Map 4-55

© Luxoft Training 2013 Collections There are two support classes that provide static methods that operate on collections and arrays: java.util.Collections java.util.Arrays 4-56 Support classes

© Luxoft Training 2013 Collections 4-57 Some java.util.Collections methods

© Luxoft Training 2013 Collections 4-58 Some java.util.Arrays methods

© Luxoft Training 2013 Example: CollectionUtilitiesTutor Collections Some java.util.Arrays methods 4-59

© Luxoft Training 2013 Collections Java Collections Framework was introduced in Java 1.2 Before similar data structures existed but their behavior wasnt unified All of their methods were synchronized, which decreased performance 4-60 Legacy collections

© Luxoft Training 2013 Collections The Vector class implements List. Use ArrayList instead of Vector The Stack class, a subclass of Vector supports stack operations: push(), pop(), peek() The Hashtable class implements the Map interface. Use the HashMap class instead of Hashtable 4-61 Legacy collections

© Luxoft Training 2013 Collections Each of this collections has the elements() method that returns Enumeration object, which allows to iterate elements in an iterator-like fashion However, this class is not compatible with Iterator That is why it is not recommended to use Enumeration 4-62 Legacy collections

© Luxoft Training 2013 Collections All collections of Collections Framework arent synchronized. In other words, class methods are not labeled as synchronized This boosts the performance of single- threaded program 4-63 Synchronizing collections

© Luxoft Training 2013 Collections To get an instance of a synchronized collection, invoke Collections.synchronizedXXX(), where XXX is an interface: Set, List, Map, Collection, etc. At the same time a primitive delegate class is created. All of its methods are synchronized and delegate the invocation to proxied collection 4-64 Synchronizing collections

© Luxoft Training 2013 Collections 4-65 Synchronizing collections. Example

© Luxoft Training 2013 Collections From the point of view of data encapsulation it is incorrect to return a collection instance from the class method, as the client code can modify this collection One way to solve this problem is to return a collections copy. Only shallow copy will be returned, without the contents 4-66 Unmodifiable collections

© Luxoft Training 2013 Collections Another option is to call Collections. unmodifiableXXX that returns simple proxy class delegating the invocations to unmodifiable methods ( get(), size() ) of the corresponding collection and throwing UnsupportedOperationException for methods that modify the collection (e.g. add(), remove() ) 4-67 Unmodifiable collections

© Luxoft Training 2013 Collections 4-68 Unmodifiable collections. Example

© Luxoft Training 2013 Exercises 4-69 Exercise Bank Application Using collections