© Luxoft Training 2013 Java Collections Framework. - презентация

1 © Luxoft Training 2013 Java Collections Framework

2 © 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

3 © 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

4 © 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

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

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

7 © 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

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

9 © 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

10 © 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

11 © 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(); }

12 © 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

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

14 © 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

15 © Luxoft Training 2013 ArrayList: add an element

16 © Luxoft Training 2013 ArrayList: insert an element

17 © 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

18 © Luxoft Training 2013 LinkedList

19 © Luxoft Training 2013 LinkedList: add an element

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

21 © Luxoft Training 2013 Example: LinkedOrArrayListTutor Collections 4-21

22 © 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

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

24 © 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

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

26 © 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

27 © Luxoft Training 2013 HashSet

28 © 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

29 © 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

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

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

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

33 © Luxoft Training 2013 Example: CollectionTutor Collections 4-33

34 © Luxoft Training 2013 Example: CollectionRemoveTutor Collections 4-34

35 © 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

36 © 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

37 © 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

38 © 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

39 © 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

40 © 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

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

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

43 © 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

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

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

46 © 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

47 © 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

48 © 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

49 © 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);

50 © 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.

51 © 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.

52 © 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

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

54 © Luxoft Training 2013 Collections 4-54 Example

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

56 © 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

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

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

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

60 © 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

61 © 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

62 © 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

63 © 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

64 © 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

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

66 © 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

67 © 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

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

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