Java Collections Framework

Содержание

Слайд 2

Agenda Data Structure What is JCF? The Collection Interfaces Collections Implementations

Agenda

Data Structure
What is JCF?
The Collection Interfaces
Collections Implementations
Ordering and Sorting
The Legacy

Collections Type
The Collections Toolbox
Other implementations in the API
Слайд 3

Lecture Objectives To understand the concepts of Java collections Framework To

Lecture Objectives

To understand the concepts of Java collections Framework
To be able

to implement Java programs based on Collections
Слайд 4

Store of Data Structure Arrays - a linear data structure and

Store of Data Structure

Arrays - a linear data structure and it's

mainly used to store similar data. An array is a particular method of storing elements of indexed data.
Слайд 5

Store of Data Structure (cont.) Linked list is a data structure

Store of Data Structure (cont.)

Linked list is a data structure consisting

of a group of nodes. Each node is composed of a datum and a reference to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence.
Слайд 6

Store of Data Structure (cont.) If each node has a reference

Store of Data Structure (cont.)

If each node has a reference to

the next and previous nodes it’s called Doubly Linked List.
Слайд 7

Store of Data Structure (cont.) Binary tree is a tree data

Store of Data Structure (cont.)

Binary tree is a tree data structure

in which each node has at most two child nodes, usually distinguished as "left" and "right".
Слайд 8

Store of Data Structure (cont.) A hash table, or a hash

Store of Data Structure (cont.)

A hash table, or a hash map,

is a data structure that associates keys with values.
Слайд 9

The Limitation of Arrays An array is a very useful type

The Limitation of Arrays

An array is a very useful type in

Java but it has its restrictions:
once an array is created it must be sized, and this size is fixed;
it contains no useful pre-defined methods.
Java comes with a group of generic collection classes that grow as more elements are added to them, and these classes provide lots of useful methods.
This group of collection classes are referred to as the Java Collections Framework.

AND SO

Слайд 10

What is a Collections Framework? A unified architecture for representing and

What is a Collections Framework?

A unified architecture for representing and manipulating

collections.
Includes:
– Interfaces: A hierarchy of abstract data types.
– Implementations
– Algorithms: The methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces.
Слайд 11

Hierarchy of interfaces

Hierarchy of interfaces

Слайд 12

Exception Conventions UnsupportedOperationException ClassCastException IllegalArgumentException IllegalStateException NoSuchElementException NullPointerException IndexOutOfBoundsException

Exception Conventions
UnsupportedOperationException
ClassCastException
IllegalArgumentException
IllegalStateException
NoSuchElementException
NullPointerException
IndexOutOfBoundsException

Слайд 13

Iterators Iterator is an object that enables a programmer to traverse

Iterators

Iterator is an object that enables a programmer to traverse a

container, particularly lists.
public interface Iterator {
boolean hasNext();
E next();
void remove(); //optional
}

public void removeLongStrings (Collection coll, int maxLen) {
Iterator it = coll.iterator();
while (it.hasNext()) {
CharSequence str = it.next();
if (str.length() > maxLen) it.remove();
}
System.out.println(coll);
}

Слайд 14

Collection public interface Collection extends Iterable { // Basic operations int

Collection

 public interface Collection extends Iterable {
// Basic operations
int size();

boolean isEmpty();
boolean contains(Object element);
boolean add(E 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();
T[] toArray(T[] a);
}
Слайд 15

Set Set — a collection that cannot contain duplicate elements This

Set

Set — a 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
Слайд 16

Set (methods) public interface Set extends Collection { // Basic operations

Set (methods)

public interface Set extends Collection {
// Basic operations
int

size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E 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();
T[] toArray(T[] a);
}
Слайд 17

List List — an ordered collection (sometimes called a sequence) Lists can contain duplicate elements

List

List — an ordered collection (sometimes called a sequence)
Lists can

contain duplicate elements
Слайд 18

List (methods) public interface List extends Collection { // Positional access

List (methods)

public interface List extends Collection {
// Positional access
E

get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
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);
}
Слайд 19

ListIterators A ListIterator extends Iterator to treat the collection as a

ListIterators

A ListIterator extends Iterator to treat the collection as a list,

allowing
– access to the integer position (index) of elements
– forward and backward traversal
– modification and insertion of elements
Слайд 20

ListIterator (methods) public interface ListIterator extends Iterator { boolean hasNext(); E

ListIterator (methods)

public interface ListIterator extends Iterator {
boolean hasNext();
E next();
boolean

hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove(); //optional
void set(E e); //optional
void add(E e); //optional
}
Слайд 21

ListIterator ListIterator it = list.listIterator(list.size()); while (it.hasPrevious()) { String obj =

ListIterator

ListIterator it = list.listIterator(list.size());
while (it.hasPrevious()) {
String obj = it.previous();
//

… use obj ….
}
Слайд 22

Queue Queue — a collection used to hold multiple elements prior

Queue

Queue — a collection used to hold multiple elements prior to

processing. Besides basic Collection operations, a Queue provides additional insertion, extraction, and inspection operations
Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner
Слайд 23

Queue (methods) public interface Queue extends Collection { E element(); //throws

Queue (methods)

public interface Queue extends Collection {
E element(); //throws
E peek(); //null
boolean

add(E e); //throws
boolean offer(E e); //null
E remove(); //throws
E poll(); //null
}
Слайд 24

Queue In addition to the inherited core services offered by Collection,

Queue

In addition to the inherited core services offered by Collection, queue

offers following methods in two flavors:
Слайд 25

Deque A linear collection that supports element insertion and removal at

Deque

A linear collection that supports element insertion and removal at both

ends
When a Deque is used as a queue, FIFO (First-In-First-Out) behavior results
Deques can also be used as LIFO (Last-In-First-Out) stacks
Слайд 26

Deque (methods) public interface Deque extends Queue { element() add(E e)

Deque (methods)

public interface Deque extends Queue {
element()
add(E e) (addLast(E e))
offer(E

e) (offerLast(E e)), offerFirst(E e)
peek()* (peekFirst()), peekLast()
getFirst(), getLast()
remove() (removeFirst()), removeFirstOccurrence(Object o),
removeLast(), removeLastOccurrence(Object o)
poll() (pollFirst()), pollLast()
contains(Object o)
iterator()
descendingIterator()
size()
pop() (removeFirst())
push(E e) (addFirst(E e))
}
from Queue, from Stack
Слайд 27

SortedSet SortedSet — a Set that maintains its elements in ascending

SortedSet

SortedSet — a Set that maintains its elements in ascending order.

Several additional operations are provided to take advantage of the ordering. Sorted sets are used for naturally ordered sets, such as word lists and membership rolls
Слайд 28

SortedSet (methods) public interface SortedSet extends Set { // Range-view SortedSet

SortedSet (methods)

public interface SortedSet extends Set {
// Range-view
SortedSet subSet(E

fromElement, E toElement);
SortedSet headSet(E toElement);
SortedSet tailSet(E fromElement);
// Endpoints
E first();
E last();
// Comparator access
Comparator comparator();
}
Слайд 29

Map An object that maps keys to values. A map cannot

Map

An object that maps keys to values. A map cannot contain

duplicate keys; each key can map to at most one value
The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings
Слайд 30

Map (methods) public interface Map { // Basic operations V put(K

Map (methods)

public interface Map {
// Basic operations
V put(K key,

V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
// Bulk operations
void putAll(Map m);
Слайд 31

Map (methods) void clear(); // Collection Views public Set keySet(); public

Map (methods)

void clear();
// Collection Views
public Set keySet();
public

Collection values();
public Set> entrySet();
// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
}
Слайд 32

Map.Entry public interface Entry { K getKey(); V getValue(); V setValue(V

Map.Entry

public interface Entry {
K getKey();
V getValue();
V setValue(V value);

}
Map map = new HashMap();
map.put("1", "a");
map.put("2", "b");
map.put("3", "c");
for( Entry entry : map.entrySet() ) {
if( "2".equals( entry.getKey() ) )
entry.setValue( "x" );
}
Слайд 33

SortedMap SortedMap — a Map that maintains its mappings in ascending

SortedMap

SortedMap — a Map that maintains its mappings in ascending key

order. This is the Map analog of SortedSet. Sorted maps are used for naturally ordered collections of key/value pairs, such as dictionaries and telephone directories
Слайд 34

SortedMap (methods) public interface SortedMap extends Map { SortedMap subMap(K fromKey,

SortedMap (methods)
public interface SortedMap extends Map{
SortedMap subMap(K

fromKey, K toKey);
SortedMap headMap(K toKey);
SortedMap tailMap(K fromKey);
K firstKey();
K lastKey();
Comparator comparator();
}
Слайд 35

Implementations JDK provides implementations of each interface. All implementations permit null

Implementations

JDK provides implementations of each interface.
All implementations permit null elements,

keys and values
All are Serializable, and all support a public clone method
Each one is unsynchronized
If you need a synchronized collection, the synchronization wrappers allow any collection to be transformed into a synchronized collection
Слайд 36

HashSet, TreeSet, LinkedHashSet The two general purpose Set implementations are HashSet

HashSet, TreeSet, LinkedHashSet

The two general purpose Set implementations are HashSet and

TreeSet (and LinkedHashSet which is between them)
HashSet is much faster but offers no ordering guarantees.
If in-order iteration is important use TreeSet.
Iteration in HashSet is linear in the sum of the number of entries and the capacity. It's important to choose an appropriate initial capacity if iteration performance is important. The default initial capacity is 101. The initial capacity may be specified using the int constructor. To allocate a HashSet whose initial capacity is 17:
Set s= new HashSet(17);
Слайд 37

Set Implementation Comparisons

Set Implementation Comparisons

Слайд 38

ArrayList and LinkedList The two general purpose List implementations are ArrayList

ArrayList and LinkedList

The two general purpose List implementations are ArrayList and

LinkedList . ArrayList offers constant time positional access, and it's just plain fast, because it does not have to allocate a node object for each element in the List, and it can take advantage of the native method System.arraycopy when it has to move multiple elements at once
If you frequently add elements to the beginning of the List, or iterate over the List deleting elements from its interior, you might want to consider LinkedList. These operations are constant time in a LinkedList but linear time in an ArrayList. Positional access is linear time in a LinkedList and constant time in an ArrayList
Слайд 39

HashMap, TreeMap, LinkedHashMap The two general purpose Map implementations are HashMap

HashMap, TreeMap, LinkedHashMap

The two general purpose Map implementations are HashMap and

TreeMap.
And LinkedHashMap (similar to LinkedHashSet)
The situation for Map is exactly analogous to Set
If you need SortedMap operations you should use TreeMap; otherwise, use HashMap
Слайд 40

The Legacy Collection Types Enumeration Analogous to Iterator. Vector Analogous to

The Legacy Collection Types

Enumeration
Analogous to Iterator.
Vector
Analogous to ArrayList, maintains an ordered

list of elements that are stored in an underlying array.
Stack
Analogous of Vector that adds methods to push and pop elements.
Dictionary
Analogous to the Map interface, although Dictionary is an abstract class, not an interface.
Hashtable
Analogous HashMap.
Properties
A subclass of Hashtable. Maintains a map of key/value pairs where the keys and values are strings. If a key is not found in a properties object a “default” properties object can be searched.
Слайд 41

Note the naming convention LinkedList also implements queue and there is

Note the naming convention

LinkedList also implements queue and there is a

PriorityQueue implementation (implemented with heap)
Слайд 42

Implementations Each of the implementations offers the strengths and weaknesses of

Implementations

Each of the implementations offers the strengths and weaknesses of the

underlying data structure.
What does that mean for:
Hashtable
Resizable array
Tree
LinkedList
Hashtable plus LinkedList
Think about these tradeoffs when selecting the implementation!
Слайд 43

Ordering and Sorting There are two ways to define orders on

Ordering and Sorting

There are two ways to define orders on objects.


Each class can define a natural order among its instances by implementing the Comparable interface.
Arbitrary orders among different objects can be defined by comparators, classes that implement the Comparator interface.
Слайд 44

The Comparable Interface The Comparable interface consists of a single method:

The Comparable Interface

The Comparable interface consists of a single method:
public

interface Comparable {
public int compareTo(T o);
}
The compareTo method compares the receiving object with the specified object, and returns a negative integer, zero, or a positive integer as the receiving object is less than, equal to, or greater than the specified Object.
Слайд 45

Comparator Comparator is another interface (in addition to Comparable) provided by

Comparator

Comparator is another interface (in addition to Comparable) provided by the

Java API which can be used to order objects.
You can use this interface to define an order that is different from the Comparable (natural) order.
Слайд 46

Comparator A Comparator is an object that encapsulates an ordering. Like

Comparator

A Comparator is an object that encapsulates an ordering. Like the

Comparable interface, the Comparator interface consists of a single method:
public interface Comparator {
int compare(T o1, T o2);
}
The compare method compares its two arguments, returning a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
Слайд 47

Live Code ☺. Comparable class HDTV implements Comparable { private int

Live Code ☺. Comparable

class HDTV implements Comparable {
private int size;
private String

brand;
public HDTV(int size, String brand) {
this.size = size;
this.brand = brand;
}
public int getSize() { return size;}
public void setSize(int size) {this.size = size; }
public String getBrand() { return brand;}
public void setBrand(String brand) {this.brand = brand; }
@Override
public int compareTo(HDTV tv) {
if (this.getSize() > tv.getSize()) return 1;
else if (this.getSize() < tv.getSize()) return -1;
else return 0;
}
}
Слайд 48

Live Code ☺. Comparable public class Main { public static void

Live Code ☺. Comparable
public class Main {
public static void main(String[] args)

{
HDTV tv1 = new HDTV(55, "Samsung");
HDTV tv2 = new HDTV(60, "Sony");
HDTV tv3 = new HDTV(42, "Panasonic");
ArrayList al = new ArrayList();
al.add(tv1);
al.add(tv2);
al.add(tv3);  
Collections.sort(al);
for (HDTV a : al) {
System.out.println(a.getBrand());
}
}
}
Слайд 49

Live Code ☺. Comparator class HDTV { private int size; private

Live Code ☺. Comparator

class HDTV {
private int size;
private String brand;
public

HDTV(int size, String brand) {
this.size = size;
this.brand = brand;
}
public int getSize() { return size;}
public void setSize(int size) {this.size = size; }
public String getBrand() { return brand;}
public void setBrand(String brand) {this.brand = brand; }
}
Слайд 50

Live Code ☺. Comparator class SizeComparator implements Comparator { @Override public

Live Code ☺. Comparator

class SizeComparator implements Comparator {
@Override
public int compare(HDTV tv1,

HDTV tv2) {
int tv1Size = tv1.getSize();
int tv2Size = tv2.getSize();
if (tv1Size > tv2Size) {
return 1;
} else if (tv1Size < tv2Size) {
return -1;
} else {
return 0;
}
}
}
class BrandComparatorDescOrder implements Comparator {
@Override
public int compare(HDTV tv1, HDTV tv2) {
return tv2.getBrand().compareTo(tv1.getBrand())
}
}
Слайд 51

Live Code ☺. Comparator public class Main { public static void

Live Code ☺. Comparator

public class Main {
public static void main(String[] args)

{
HDTV tv1 = new HDTV(55, "Samsung");
HDTV tv2 = new HDTV(60, "Sony");
HDTV tv3 = new HDTV(42, "Panasonic");
ArrayList al = new ArrayList();
al.add(tv1);
al.add(tv2);
al.add(tv3);
Collections.sort(al, new SizeComparator());
for (HDTV a : al) {
System.out.println(a.getBrand());
}
Collections.sort(al, new BrandComparatorDescOrder());
for (HDTV a : al) {
System.out.println(a.getBrand());
}
}
}
Слайд 52

Other implementations in the API Wrapper implementations delegate all their real

Other implementations in the API

Wrapper implementations delegate all their real work

to a specified collection but add (or remove) extra functionality on top of what the collection offers.
Synchronization Wrappers
Unmodifiable Wrappers
Convenience implementations are mini-implementations that can be more convenient and more efficient than general-purpose implementations when you don't need their full power
List View of an Array
Immutable Multiple-Copy List
Immutable Singleton Set
Empty Set, List, and Map Constants
Слайд 53

Synchronization wrappers The synchronization wrappers add automatic synchronization (thread-safety) to an

Synchronization wrappers

The synchronization wrappers add automatic synchronization (thread-safety) to an arbitrary

collection. There is one static factory method for each of the six core collection interfaces:
public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static Map synchronizedMap(Map m);
public static SortedSet synchronizedSortedSet(SortedSet s);
public static SortedMap synchronizedSortedMap(SortedMap m);
Each of these methods returns a synchronized (thread-safe) Collection backed by the specified collection.
Слайд 54

Unmodifiable wrappers Unmodifiable wrappers take away the ability to modify the

Unmodifiable wrappers

Unmodifiable wrappers take away the ability to modify the collection,

by intercepting all of the operations that would modify the collection, and throwing an UnsupportedOperationException. The unmodifiable wrappers have two main uses:
To make a collection immutable once it has been built.
To allow "second-class citizens" read-only access to your data structures. You keep a reference to the backing collection, but hand out a reference to the wrapper. In this way, the second-class citizens can look but not touch, while you maintain full access.
Слайд 55

Unmodifiable wrappers(cont.) There is one static factory method for each of

Unmodifiable wrappers(cont.)

There is one static factory method for each of the

six core collection interfaces:
public static Collection unmodifiableCollection(Collection c);
public static Set unmodifiableSet(Set s);
public static List unmodifiableList(List list);
public static Map unmodifiableMap(Map m);
public static SortedSet unmodifiableSortedSet(SortedSet s);
public static SortedMap unmodifiableSortedMap(SortedMap m);
Слайд 56

Singleton static Set Collections.singleton(T e) returns an immutable set containing only

Singleton

static SetCollections.singleton(T e) returns an immutable set containing only the

element e
This is handy when you have a single element but you would like to use a Set operation
c.removeAll(Collections.singleton(e));
will remove all occurrences of e from the Collection c
Слайд 57

The Collections Toolbox The collections framework also provides polymorphic versions of

The Collections Toolbox

The collections framework also provides polymorphic versions of algorithms

you can run on collections.
Sorting
Shuffling
Routine Data Manipulation
Reverse
Fill copy
etc.
Searching
Binary Search
Composition
Frequency
Disjoint
Finding extreme values
Min
Max
Слайд 58

Concurrent Collections ConcurrentReaderHashMap An analog of java.util.Hashtable that allows retrievals during

Concurrent Collections

ConcurrentReaderHashMap An analog of java.util.Hashtable that allows retrievals during updates.


ConcurrentHashMap An analog of java.util.Hashtable that allows both concurrent retrievals and concurrent updates.
CopyOnWriteArrayList A copy-on-write analog of java.util.ArrayList
CopyOnWriteArraySet A java.util.Set based on CopyOnWriteArrayList.
SyncCollection A wrapper class placing either Syncs or ReadWriteLocks around java.util.Collection
SyncSet A wrapper around java.util.Set
SyncSortedSet A wrapper around java.util.SortedSet
SyncList A wrapper around java.util.List
SyncMap A wrapper around java.util.Map
SyncSortedMap A wrapper around java.util.SortedMap
Слайд 59

How to choose which Java collection class to use? Which Java List to use?

How to choose which Java collection class to use?

Which Java List

to use?
Слайд 60

How to choose which Java collection class to use? Which Java Set to use?

How to choose which Java collection class to use?

Which Java Set

to use?
Слайд 61

How to choose which Java collection class to use? Which Java Map to use?

How to choose which Java collection class to use?

Which Java Map

to use?
Слайд 62

Open Source Collections Libraries in Java Apache Commons Collections Package Guava-libraries

Open Source Collections Libraries in Java

Apache Commons Collections Package
Guava-libraries (Google Collections

Library)
Trove high performance collections for Java
The Mango Library
- Предыдущая
Розвиток ядерної енергетики в Україні
Следующая -
Java 8 Stream API

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

исследование 4 кл. - презентация для начальной школы
Изгибаемые элементы
Методы экспертных оценок в стратегическом государственном управлении
Презентация Интеллектуальная игра умники и умницы
Тема №6. Аппаратура управления и защиты бортовых систем электроснабжения. Занятие 1. Общие сведения о защите СЭС
Дарвинский заповедник
Презентация Статья 181 УК РФ. Нарушение правил изготовления и использования государственных пробирных клейм
Страйкбол. 6 класс
РЕШАЮЩАЯ РОЛЬ КУЛЬТУРЫ В СТАНОВЛЕНИИ И РАЗВИТИИ НООСФЕРЫ Джура С.Г. dzhura@roerich.com (062) 337-32-66; www.roerich.com
Безопасность человека в ЧС природного характера
Нові медіа – нові потреби аудиторії Ніна Кур’ята
Каталог Лето 2016
Особистість підприємця та його ділові якості
Особенности экономического районирования России Подготовила: Клеутина С.А. Группа МЭ-092
Порядок слов
Презентация по МХК Художественная культура Среднего Востока
Средства инструментального программирования
Инструкция по вносу накладных
Управление таможенной деятельностью
Организационные структуры систем государственного управления
Влияние аутогенных тренировок в предсоревновательный и соревновательный периоды в подготовке легкой атлетике
The definition of management
Архитектура Китая
Художник и мир животных презентация к уроку изобразительного искусства 2 класс УМК «Гармония»
Презентация Привлечение иностранных инвестиций
Структуры в Visual
География древних путешествий
Языковая ситуация в Казахстане
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть