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

1 © Luxoft Training 2013 Java Collections API

2 © Luxoft Training 2013 Collections hierarchy

3 © Luxoft Training 2013 Collections hierarchy 4-3

4 © Luxoft Training 2013 Collection methods 4-4

5 © Luxoft Training 2013 Iterator interface boolean hasNext() Object next() return the next element void remove() removes the element returned by next() remove() is a safe way to remove element 4-5

6 © Luxoft Training 2013 Use of iterator 4-6 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(); }

7 © Luxoft Training 2013 List interface List keep the order of elements List is indexed from 0 List is alike array, but can change the size List methods: 4-7

8 © Luxoft Training 2013 ArrayList 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 4-8

9 © Luxoft Training 2013 ArrayList: add an element

10 © Luxoft Training 2013 ArrayList: insert an element

11 © Luxoft Training 2013 LinkedList

12 © Luxoft Training 2013 LinkedList: add an element

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

14 © Luxoft Training 2013 Example: LinkedOrArrayListTutor List 4-14

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

16 © Luxoft Training 2013 Set interface Set has no order – just a set of elements Set cannot have duplicate elements On adding the existing element add() returns false and doesnt insert element To compare elements set use equals(), not == 4-16

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

18 © Luxoft Training 2013 Collections The java.util.HashSet implementation stores elements in special hash set. You cant predict the order in which the elements will be returned by iterator() 4-18 java.util.HashSet implementation

19 © Luxoft Training 2013 java.util.HashSet implementation 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-19

20 © Luxoft Training 2013 HashSet The acces to the element in HashSet occupies a constant time HashSet keep elements in the buckets grouped by value of hashCode() The order of elements is not determined. 4-20

21 © Luxoft Training 2013 HashSet

22 © Luxoft Training 2013 java.util.TreeSet implementation 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-22

23 © Luxoft Training 2013 java.util.TreeSet implementation The java.util.SortedSet interface extends java.util.Set 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-23

24 © Luxoft Training 2013 java.util.TreeSet implementation At the same time we should define the method for comparison of collection elements (well examine it later) One of the implementations of java.util.SortedSet is the java.util.TreeSet 4-24

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

26 © Luxoft Training 2013 Examples: CollectionTutor CollectionRemoveTutor Collections 4-26

27 © Luxoft Training 2013 Compare elements 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-27

28 © Luxoft Training 2013 Comparable interface 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-28

29 © Luxoft Training 2013 Comparable interface 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-29

30 © Luxoft Training 2013 Comparable interface 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-30

31 © Luxoft Training 2013 Comparable interface 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-31

32 © Luxoft Training 2013 Comparator interface 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-32

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

34 © Luxoft Training 2013 Collections Natural ordering Comparable paradigm and Comparators mechanism are used not only in TreeSet sorting, but also when sorting arrays and other data structures The purpose of these tools is to make it possible to compare objects of given type 4-34 java.lang.Comparator

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

36 © Luxoft Training 2013 Collections diagram 4-36

37 © Luxoft Training 2013 java.util.Map interface 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-37

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

39 © Luxoft Training 2013 The java.util.Map implementations 4-39

40 © 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-40 java.util.Map implementations

41 © 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-41 java.util.Map implementations

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

43 © Luxoft Training 2013 Collections 4-43 Example

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

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

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

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

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