Collections

Слайд 7

Java Collection Framework
The Collection in Java is a framework that provides

an architecture to store and manipulate the group of objects.
Java Collections can achieve all the operations that you perform on a data such as searching, sorting, insertion, manipulation, and deletion.
Java Collection means a single unit of objects and its main advantage is grow as necessary.

Слайд 8

Collections in Java
Java Collection framework provides many interfaces (Set, List, Queue,

Deque) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet).
All collections frameworks contain the following:
interfaces
implementations
algorithms (there are the methods such as searching and sorting)

Слайд 9

Benefits of collections
reduces programming effort
increases program speed and quality
allows interoperability among

unrelated APIs
reduce effort to design new APIs
helps to reuse the code

Слайд 10

Interfaces
There are data types that represent collections.
Classes that implement interfaces
List

and Set, implement the interface Iterable.

Слайд 11

Collections in Java
List – a list of objects. Objects can be

added to the list (the method add()), replace the list (method set()), removed from the list (the method remove()), extract (method get()). There is the ability to pass on the list of organizations with an iterator.
Set – a set of objects. The same features as that of the List, but the object can be part of set only once. Double addition of one and the same object in the set is not change the set.
Map – a map or associative array. In Map we add pair of objects (key, value). Accordingly, the search operation is a key value. Adding a couple with an existing key in the Map leads to the replacement, not to upload it. From Map can be obtain key and a list of values.

Слайд 12

Collections in Java
The interface Collection defined methods:
boolean add(E obj) –

adds obj to the collection, it returns true, if the object is added;
boolean addAll(Collection c) – adds all the elements;
void clear() – removes all items from the collection;
boolean contains(Object obj) – returns true, if the collection contains an element of obj;
boolean equals(Object obj) – returns true, if the collections are equivalent;

Слайд 13

Collections in Java
boolean isEmpty() – returns true, if the collection is

empty;
Iterator iterator() – retrieves the iterator;
boolean remove(Object obj) – removes the object from the collection;
int size() – the number of items in the collection;
Object[] toArray() – copies the collection to an array of objects;
T[] toArray(T a[]) – copies the elements of the collection to an array of objects of a particular type.

Слайд 14

Interfaces

Слайд 15

Implementations
There are the implementations of the collection interfaces. In essence, they

are reusable data structures

Слайд 16

Interface List
A Lists are Ordered Collections (sometimes called a sequence).
Lists

can contain duplicate elements.
The user of a List generally has precise control over where in the list each element is inserted and can access elements by their integer index (position).

Слайд 17

Class ArrayList
Array Lists use a dynamic array to store the

duplicate element of different data types.
The Array List maintains the insertion order.
The elements stored in the Array List can be randomly accessed.

Слайд 18

Class LinkedList
Linked Lists use a references to maintain an ordered lists

of “nodes”.
The “head” of the list references the first node.
Each node has a value and a reference to the next and previous node.

Слайд 19

List
Since List is an interface you need to instantiate a concrete

implementation of the interface in order to use it.
There are two general-purpose List implementations — java.util.ArrayList and java.util.LinkedList

Here are a few examples of how to create a List instance:
List listArr = new ArrayList(); or List listArr = new ArrayList(15);
List listLink = new LinkedList();
Capacity of ArrayList by default capacity = 10
For new arrayList capacity = (oldCapacity * 3) / 2 + 1

Слайд 20

List
Adding elements
List list = new ArrayList<>();
list.add("First element");
list.add("Second element");
list.add(0, "One more first

element");
Access through index
String element2 = list.get(1);
Access through new for-loop
for(Object object : list) {
String element = (String) object;
// do something
}

Слайд 21

List
Removing Elements
remove(Object element) or remove(int index)
Cleaning a list
list.clear();
List size
int size =

list.size();
Generic List
List myType = new ArrayList( );
myType.add(new MyType( ));
MyType my = myType.get(0);

Слайд 22

List
LinkedList has the same functionality as the ArrayList.
Different way of implementation

and efficiency of operations.
Adding to the LinkedList is faster
Pass through the list is almost as effective as the ArrayList,
Arbitrary removal from the list is slower than ArrayList.

Слайд 23

Interface Set
A Sets are Unordered Collection that cannot contain duplicate elements.

This interface models the mathematical set abstraction and is used to represent sets, such as the cards comprising a poker hand, the courses making up a student's schedule, or the processes running on a machine.

Слайд 24

Interface Set
Element that are put in a set must override equals()

method to establish uniqueness
Can contain null

Слайд 25

Interface Set
The HashSet class
Uses Hash Tables to speed up finding, adding,

and removing elements.
The TreeSet class
Uses a Binary Tree to speed up finding, adding, and removing elements.
The LinkedHashSet class
Uses Hash Tables to storing elements and provides the order of insertion.

Слайд 26

Class HashSet
HashSet is unsorted and unordered set
uses hashcode of the object

being inserted; the more efficient hashCode() implementation, the better access performance
use this when you want no duplicates and don’t care about order when you iterate through the elements

Слайд 27

Class LinkedHashSet
LinkedHashSet is an ordered version of HashSet
maintains doubly-linked list across

all elements
if you care about iteration order, use this
it lets you iterate through in the order in which elements were inserted(or added)
when using HashSet or LinkedHashSet, you must override hashCode(), otherwise uniqueness of objects is not guaranteed

Слайд 28

Class TreeSet
TreeSet is one of the two sorted collections (the other

being TreeMap)
uses Red-Black tree structure (special binary search tree with minimum possible height)
guarantees that the elements will be in ascending order according to natural order
lets you specify your own ordering rules by using Comparable or Comparator as of java 6, TreeSet also implements NavigableSet

Слайд 29

Example
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);
}
}

Слайд 30

equals() and hashCode() Contract
The contract between equals() and hashCode() methods

is:
If two objects are equal, then they must have the same hash code.
If two objects have the same hash code, they may or may not be equal (Hash Code Collisions).

Слайд 31

Iterator
Iterator – a helper object. Used to iterate over collection of

objects.
Iterators are based on the interface
boolean hasNext() – checks whether there are elements in the collection
Object next() – shows the next item in the collection
void remove() – removes the last selected item from the collection
Collection interface has a method Iterator iterator();

Слайд 32

List Iterator
When traversing a LinkedList collection, use a ListIterator class.
List names

= new ArrayList<>(); names.add("Mike"); names.add("Nick"); names.add("Sara");
ListIterator iterator = names.listIterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); }
names.listIterator(names.size());
while (iterator.hasPrevious()) { System.out.println(iterator.previous()); }

Mike
Nick
Sara

Sara
Nick
Mike

Слайд 33

Set Iterator
Iterators are also used when processing sets, but sets don’t

support ListIterator class.
Instead, for sets you must use Iterator class.

Set names = new HashSet<>(); names.add("Mike"); names.add("Nick"); names.add("Sara"); Iterator iterator = names.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); }

Mike
Nick
Sara

Слайд 34

Iterator and Loop
Iterators are often used in while and “for-each” loops.
hasNext()

method returns true if there is a next element.
next() method returns a reference to the value of the next element.
Where is the iterator in the “for-next” loop? It is used “behind the scenes”.

Set names = new HashSet<>(); names.add("Mike"); names.add("Nick"); names.add("Sara"); for (String name : names) { System.out.println(name); }

Mike
Nick
Sara

Слайд 35

Interface Map
Map
The Map is an object that maps keys to values.
Map

cannot contain duplicate keys and each key can map to at most one value.
both key and value are objects
relies on equals() to determine two keys are same or not

Слайд 36

Interface Map
A Map stores keys, values, and the associations between them.
Keys

- provides an easy way to represent an object.
Values - the actual object that is associated with the key.

Слайд 37

Map
The most commonly used Map implementations are HashMap and TreeMap.
Map mapA

= new HashMap();
Map mapB = new TreeMap();
Adding elements
mapA.put("key1", "one");
mapA.put("key2", "two");
mapA.put(1,3);
mapA.put(student1, room1);
String value2 = (String) mapA.get("key2");
Removing element
mapA.remove(Object key);

Слайд 38

Classes HashMap and TreeMap
A Map allows you to associate elements from

a key set with elements from a value collection.
The HashMap and TreeMap classes both implement the Map interface.

Book book = new Book(); UUID uuid = UUID.randomUUID(); Map books = new HashMap<>(); books.put(UUID.randomUUID().toString(), book); books.put(uuid.toString(), new Book()); books.put(UUID.randomUUID().toString(), book); book = books.get(uuid);

Слайд 39

Map’s Iterator
To iterate through the map, use a entrySet() method and

object of Iterator class:
Or get the entry set use entrySet() method:
Or get values use the values() method:

Iterator iter = books.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry = (Map.Entry)iter.next(); System.out.println(entry.getKey() + "->" + entry.getValue()); }

for (Map.Entry entry : books.entrySet()) { System.out.println(entry.getKey() + "->" + entry.getValue()); }

for (Book book : books.values()) { System.out.println(value); }

Слайд 40

Map
for (Iterator i = map.entrySet().iterator(); i.hasNext();){
Map.Entry entry = (Map.Entry) i.next();

System.out.println(entry.getKey() + " " + entry.getValue());
}

for (Map.Entry entry : map.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}

Слайд 41

Big-O Notation
In computer science, big O notation is used to classify

algorithms according to how their running time or space requirements grow as the input size grows.

Слайд 42

Big-O Notation

Слайд 43

Practical task 1
Declare collection myCollection of 10 integers and fill it

(from the console or random).
Find and save in list newCollection all positions of element more than 5 in the collection. Print newCollection
Remove from collection myCollection elements, which are greater then 20. Print result
Insert elements 1, -3, -4 in positions 2, 8, 5. Print result in the format: “position – xxx, value of element – xxx”
Sort and print collection
Use one or more of the next Collections: List, ArrayList, LinkedList

Слайд 44

Practical task 2
In the main() method declare map employeeMap of pairs

.
Add to employeeMap seven pairs (ID, name) of some persons. Display the map on the screen.
Ask user to enter ID, then find and write corresponding name from your map. If you can't find this ID - say about it to user (use function containsKey()).
Ask user to enter name, verify than you have name in your map and write corresponding ID. If you can't find this name - say about it to user (use function containsValue()).

Слайд 45

Homework
Write parameterized methods union(Set set1, Set set2) and intersect(Set set1, Set

set2), realizing the operations of union and intersection of two sets. Test the operation of these techniques on two pre-filled sets.
Create map personMap and add to it ten persons of type (lastName, firstName).
Output the entities of the map on the screen.
There are at less two persons with the same firstName among these 10 people?
Remove from the map person whose firstName is ”Orest” (or other). Print result.

Слайд 46

Homework
Write class Student that provides information about the name of the

student and his course. Class Student should consist of
properties for access to these fields
constructor with parameters
method printStudents (List students, Integer course), which receives a list of students and the course number and prints to the console the names of the students from the list, which are taught in this course (use an iterator)
methods to compare students by name and by course
In the main() method
declare List students and add to the list five different students
display the list of students ordered by name
display the list of students ordered by course.

Collections

Содержание

AGENDAArrays in JavaCollections in JavaListSetMap

Arrays

Arrays in Javaclass Car{ }; // minimal dummy classCar[ ] cars1;

Arrays in JavaMost efficient way to hold references to objects.AdvantagesAn array

Collections

Java Collection FrameworkThe Collection in Java is a framework that provides

Collections in JavaJava Collection framework provides many interfaces (Set, List, Queue,

Benefits of collectionsreduces programming effortincreases program speed and qualityallows interoperability among

InterfacesThere are data types that represent collections.Classes that implement interfaces List

Collections in JavaList – a list of objects. Objects can be

Collections in JavaThe interface Collection defined methods: boolean add(E obj) –

Collections in Javaboolean isEmpty() – returns true, if the collection is

Interfaces

ImplementationsThere are the implementations of the collection interfaces. In essence, they

Interface ListA Lists are Ordered Collections (sometimes called a sequence). Lists

Class ArrayList Array Lists use a dynamic array to store the

Class LinkedListLinked Lists use a references to maintain an ordered lists

ListSince List is an interface you need to instantiate a concrete

ListAdding elementsList list = new ArrayList<>();list.add("First element");list.add("Second element");list.add(0, "One more first

ListRemoving Elements remove(Object element) or remove(int index)Cleaning a list list.clear();List size int size =

ListLinkedList has the same functionality as the ArrayList.Different way of implementation

Interface SetA Sets are Unordered Collection that cannot contain duplicate elements.

Interface SetElement that are put in a set must override equals()

Interface SetThe HashSet classUses Hash Tables to speed up finding, adding,

Class HashSetHashSet is unsorted and unordered setuses hashcode of the object

Class LinkedHashSetLinkedHashSet is an ordered version of HashSetmaintains doubly-linked list across

Class TreeSetTreeSet is one of the two sorted collections (the other

Exampleimport java.util.*;public class FindDups { public static void main(String args[ ]){

equals() and hashCode() Contract The contract between equals() and hashCode() methods

IteratorIterator – a helper object. Used to iterate over collection of

List IteratorWhen traversing a LinkedList collection, use a ListIterator class.List names

Set IteratorIterators are also used when processing sets, but sets don’t

Iterator and LoopIterators are often used in while and “for-each” loops.hasNext()

Interface MapMapThe Map is an object that maps keys to values.Map

Interface MapA Map stores keys, values, and the associations between them.Keys

MapThe most commonly used Map implementations are HashMap and TreeMap. Map mapA

Classes HashMap and TreeMapA Map allows you to associate elements from

Map’s IteratorTo iterate through the map, use a entrySet() method and

Mapfor (Iterator i = map.entrySet().iterator(); i.hasNext();){ Map.Entry entry = (Map.Entry) i.next();

Big-O NotationIn computer science, big O notation is used to classify

Big-O Notation

Practical task 1Declare collection myCollection of 10 integers and fill it

Practical task 2In the main() method declare map employeeMap of pairs

HomeworkWrite parameterized methods union(Set set1, Set set2) and intersect(Set set1, Set

HomeworkWrite class Student that provides information about the name of the

Похожие презентации

AGENDA
Arrays in Java
Collections in Java
List
Set
Map

Arrays in Java
class Car{ }; // minimal dummy class
Car[ ] cars1;

Arrays in Java
Most efficient way to hold references to objects.
Advantages
An array

Java Collection Framework
The Collection in Java is a framework that provides

Collections in Java
Java Collection framework provides many interfaces (Set, List, Queue,

Benefits of collections
reduces programming effort
increases program speed and quality
allows interoperability among

Interfaces
There are data types that represent collections.
Classes that implement interfaces
List

Collections in Java
List – a list of objects. Objects can be

Collections in Java
The interface Collection defined methods:
boolean add(E obj) –

Collections in Java
boolean isEmpty() – returns true, if the collection is

Implementations
There are the implementations of the collection interfaces. In essence, they

Interface List
A Lists are Ordered Collections (sometimes called a sequence).
Lists

Class ArrayList
Array Lists use a dynamic array to store the

Class LinkedList
Linked Lists use a references to maintain an ordered lists

List
Since List is an interface you need to instantiate a concrete

List
Adding elements
List list = new ArrayList<>();
list.add("First element");
list.add("Second element");
list.add(0, "One more first

List
Removing Elements
remove(Object element) or remove(int index)
Cleaning a list
list.clear();
List size
int size =

List
LinkedList has the same functionality as the ArrayList.
Different way of implementation

Interface Set
A Sets are Unordered Collection that cannot contain duplicate elements.

Interface Set
Element that are put in a set must override equals()

Interface Set
The HashSet class
Uses Hash Tables to speed up finding, adding,

Class HashSet
HashSet is unsorted and unordered set
uses hashcode of the object

Class LinkedHashSet
LinkedHashSet is an ordered version of HashSet
maintains doubly-linked list across

Class TreeSet
TreeSet is one of the two sorted collections (the other

Example
import java.util.*;
public class FindDups {
public static void main(String args[ ]){

equals() and hashCode() Contract
The contract between equals() and hashCode() methods

Iterator
Iterator – a helper object. Used to iterate over collection of

List Iterator
When traversing a LinkedList collection, use a ListIterator class.
List names

Set Iterator
Iterators are also used when processing sets, but sets don’t

Iterator and Loop
Iterators are often used in while and “for-each” loops.
hasNext()

Interface Map
Map
The Map is an object that maps keys to values.
Map

Interface Map
A Map stores keys, values, and the associations between them.
Keys

Map
The most commonly used Map implementations are HashMap and TreeMap.
Map mapA

Classes HashMap and TreeMap
A Map allows you to associate elements from

Map’s Iterator
To iterate through the map, use a entrySet() method and

Map
for (Iterator i = map.entrySet().iterator(); i.hasNext();){
Map.Entry entry = (Map.Entry) i.next();

Big-O Notation
In computer science, big O notation is used to classify

Practical task 1
Declare collection myCollection of 10 integers and fill it

Practical task 2
In the main() method declare map employeeMap of pairs

Homework
Write parameterized methods union(Set set1, Set set2) and intersect(Set set1, Set

Homework
Write class Student that provides information about the name of the