Java Collections

1.

JAVA
COLLECTIONS
Author: Olga Smolyakova
Oracle Certified Java 6 Programmer
[email protected]
1

2.

Содержание
1.
2.
3.
4.
5.
6.
7.
8.
9.
Определение коллекций
Интерфейс Collection
Множества Set
Интерфейс Iterator
Списки List
Интерфейс ListIterator
Очереди Queue
Карты отображений Map
Класс Collections
2

3.

ОПРЕДЕЛЕНИЕ КОЛЛЕКЦИЙ
3

4.

Определение коллекций
Коллекции – это хранилища, поддерживающие различные способы
накопления и упорядочения объектов с целью обеспечения
возможностей эффективного доступа к ним.
Коллекции в языке Java объединены в библиотеке классов java.util и
представляют собой контейнеры, т.е объекты, которые группируют
несколько элементов в отдельный модуль.
Коллекции используются для хранения, поиска,
передачи данных.
Collections framework - это унифицированная
представления и манипулирования коллекциями.
манипулирования и
архитектура
для
4

5.

Определение коллекций
специализирует коллекции
для обработки списков
вершина иерархии
коллекций
специализирует коллекции для обработки множеств, содержащих уникальные элементов
5

6.

Определение коллекций
карта отображения
вида “ключ-значение”
Все конкретные классы Java Collections Framework реализуют
Cloneable и Serializable интерфейсы.
6

7.

ИНТЕРФЕЙС COLLECTION
7

8.

Интерфейс Collection
JDK не предоставляет прямых реализаций интерфейса Collection, но
существует
множество
реализаций
более
специфичных
подинтерфейсов таких как Set и List.
Некоторые методы интерфейса Collection могут быть не реализованы в
подклассах (нет необходимости их реализовывать). В этом случае
метод генерирует java.lang.UnsupportedOperationException.
8

9.

Интерфейс Collection
public interface Collection<E> extends Iterable<E> {
▪
boolean equals(Object o);
▪
int size();
interface Iterable<T>{
▪
boolean isEmpty();
▪ Iterator<T> iterator();
▪
boolean contains(Object element);
}
▪
boolean add(E element);
▪
boolean remove(Object element);
▪
Iterator<E> iterator();
▪
boolean containsAll(Collection<?> c);
▪
boolean addAll(Collection<? extends E> c);
▪
boolean removeAll(Collection<?> c);
Класс
▪
boolean retainAll(Collection<?> c);
AbstractCollection
▪
void clear();
предоставляет частичную
реализацию интерфейса
▪
Object[ ] toArray();
Collection, реализует все
▪
<T> T[ ] toArray(T[ ] a);
методы, за исключением
}
size() и iterator().
9

10.

МНОЖЕСТВА SET
10

11.

Множества Set
Интерфейс Set, наследуясь
от интерфейса Collection,
не добавляет никаких новых
методов
Множество ─
коллекция без
повторяющихся
элементов
public interface Set<E>
extends Collection<E> {
▪
▪
▪
▪
▪
▪
▪
▪
▪
▪
▪
▪
▪
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element);
boolean remove(Object element);
Iterator<E> iterator();
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
Object[] toArray();
<T> T[] toArray(T[] a);
}
11

12.

Множества Set
Класс AbstractSet
public abstract class
AbstractSet<E>
extends AbstractCollection<E>
implements Set<E>
Конкретные реализации множеств
HashSet
LinkedHashSet
TreeSet
ConcurrentSkipListSet
CopyOnWriteArraySet
EnumSet
12

13.

Множества Set
HashSet – неотсортированная и неупорядоченная коллекция не
содержащая повторяющихся элементов.
Для вставки элемента используются методы hashCode() и equals(…)
Set<MyDate> set = new
HashSet<MyDate>();
MyDate date1 = new MyDate(1);
MyDate date2 = new MyDate(1);
set.add(date1);
set.add(date2);
println(set.size());
class MyDate{
int day;
MyDate(int day){this.day = day; }
public boolean equals(Object obj){…}
public int hashCode(){… }
}
Set<MyDate> set = new
HashSet<MyDate>();
MyDate date1 = new MyDate(1);
MyDate date2 = new MyDate(2);
set.add(date1);
set.add(date2);
println(set.size());
1
MyDate date3 = new MyDate(1);
println(set.contains(date3)); 2
true
Чем эффективней реализован метод
hashCode(), тем эффективней работает
коллекция.
13

14.

Множества Set
HashSet используется в случае, когда порядок элементов не важен, но
важно чтобы в коллекции все элементы были уникальны.
Set<String> set = new HashSet<String>();
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Berling");
set.add("New York");
System.out.println(set);
[San Francisco, New York, Paris, Berling, London]
for (Object element : set){
System.out.print(element.toString());
}
San Francisco New York Paris Berling London
14

15.

Множества Set
Конструкторы HashSet
Создает новое пустое множество, capacity = 16, loadfactor = 0.75
HashSet()
HashSet(Collection<? extends E> c)
HashSet(int initialCapacity)
Создает новое множество,
содержащее элементы переданной
в качестве параметра коллекции
Создает новое пустое множество с
определенной начальной
емкостью
HashSet(int initialCapacity, float loadFactor)
Создает новое пустое множество с
определенной начальной емкостью и
определенным значением фактора
загрузки
15

16.

Множества Set
Реализация класса HashSet
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
…
}
16

17.

Множества Set
LinkedHashSet<E> ─ множество c сохранением порядка обхода.
Set<String> set = new LinkedHashSet<String>();
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Berling");
set.add("New York");
System.out.println(set);
[London, Paris, New York, San Francisco, Berling]
for (Object element : set){
System.out.print(element.toString() + " ");
}
London Paris New York San Francisco Berling
17

18.

Множества Set
Реализация класса LinkedHashSet
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
...
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
...
public class LinkedHashSet<E> extends HashSet<E>
}
implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);}
public LinkedHashSet() {
super(16, .75f, true);}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2 * c.size(), 11), .75f, true);
addAll(c);}
}
18

19.

Множества Set
SortedSet<E> ─ множество c предоставлением возможности
полного упорядочивания элементов. Элементы упорядочиваются
или согласно естественному порядку сортировки или согласно
порядку, который задает Comparator.
public interface SortedSet<E> extends Set<E>{
▪ Comparator<? super E> comparator();
▪ E first();
▪ SortedSet<E> headSet(E toElement);
▪ E last();
▪ SortedSet<E> subSet(E fromElement, E toElement);
▪ SortedSet<E> tailSet(E fromElement);
}
19

20.

Множества Set
NavigableSet<E> ─ расширяет SortedSet, добавляет методы
навигации, определяющие ближайший экземпляр по отношению к
экземпляру, заданному для поиска.
public interface NavigableSet<E> extends SortedSet<E>
E lower(E e); < E
E floor(E e);
E pollFirst();
<= E
E higher(E e); > E
E pollLast();
E ceiling(E e); >= E
Iterator<E> iterator();
Iterator<E> descendingIterator();
NavigableSet<E> descendingSet();
20

21.

Множества Set
public interface NavigableSet<E> extends SortedSet<E>
NavigableSet<E> headSet(E toElement, boolean inclusive)
NavigableSet<E> subSet( E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive)
NavigableSet<E> tailSet(E fromElement, boolean inclusive)
SortedSet<E> headSet(E toElement)
SortedSet<E> subSet(E fromElement, E toElement)
SortedSet<E> tailSet(E fromElement)
21

22.

Множества Set
TreeSet<E> – сортированное множество, хранящее элементы в
виде бинарного дерева.
Конструкторы и реализация TreeSet
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
1 private transient NavigableMap<E, Object> m;
private static final Object PRESENT = new Object();
2 public TreeSet() {
3
this(new TreeMap<E, Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator)); }
4 public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
5 public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
}
22

23.

Множества Set
TreeSet<String> treeSet1 = new TreeSet<String>(new LastLetterComparator());
treeSet1.add("London"); treeSet1.add("Paris");
treeSet1.add("New York"); treeSet1.add("San Francisco");
treeSet1.add("Berling"); treeSet1.add("New York");
System.out.println(treeSet1);
[Berling, New York, London, San Francisco, Paris]
TreeSet<String> treeSet2 = new TreeSet<String>();
treeSet2.add("London"); treeSet2.add("Paris");
treeSet2.add("New York"); treeSet2.add("San Francisco");
treeSet2.add("Berling"); treeSet2.add("New York");
System.out.println(treeSet2);
[Berling, London, New York, Paris, San Francisco]
23

24.

ИНТЕРФЕЙС ITERATOR
24

25.

Интерфейс Iterator
Для обхода коллекции можно
использовать:
for-each
Конструкция for-each является краткой формой записи обхода
коллекции с использованием цикла for
for (Object o: collection){
System.out.println(o);
}
Iterator
Итератор - это объект, который позволяет осуществлять обход
коллекции и при желании удалять избранные элементы.
interface Iterable<T>{
Iterator<T> iterator();
}
25

26.

Интерфейс Iterator
Метод Iterator<E> iterator() коллекций – возвращает итератор.
Set<String> set = new HashSet<String>();
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Berling");
set.add("New York");
Iterator<String> iterator = set.iterator();
26

27.

Интерфейс Iterator
public interface Iterator
{
boolean hasNext();
Object next();
void remove();
}
Set<String> set = new TreeSet<String>();
set.add("London"); set.add("Paris");
set.add("New York"); set.add("San Francisco");
set.add("Berling"); set.add("New York");
Iterator<String> iterator = set.iterator();
true
if( iterator.hasNext() ){}
27

28.

Интерфейс Iterator
String str = null;
if(iterator.hasNext()){
str = iterator.next();
}
iterator.remove();
Исключения:
NoSuchElementException ─ генерируется при достижении конца коллекции
ConcurrentModificationException ─ генерируется при изменении коллекции
28

29.

Интерфейс Iterator
Перебор элементов коллекции через итератор:
1
Iterator<String> iterator = set.iterator();
2 while (iterator.hasNext()) {
3
System.out.print(iterator.next() + " ");
}
возвращает объект, на который указывает
итератор, и передвигает текущий указатель на
следующий итератор
Если следующий элемент
коллекции отсутствует, то метод
next() генерирует исключение
static void filter(Collection<?> c) {
for (Iterator<?> it = c.iterator(); it.hasNext();)
if (!cond(it.next()))
it.remove();
}
удаляет объект, возвращенный последним
вызовом метода next()
29

30.

СПИСКИ LIST
30

31.

Списки List
Список - упорядоченная коллекция
Интерфейс List сохраняет последовательность добавления элементов
и позволяет осуществлять доступ к
элементу по индексу.
31

32.

Списки List
public interface List<E> extends Collection<E> {
E get(int index);
E set(int index, E element);
boolean add(E element);
void add(int index, E element);
E remove(int index);
boolean addAll(int index, Collection<? extends E> c);
int indexOf(Object o);
List<String> list =
int lastIndexOf(Object o);
new ArrayList<String>();
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index); list.add("London");
list.add("Paris");
List<E> subList(int from, int to);
list.add("New York");
}
list.add("San Francisco");
list.add("Berling");
list.add("New York");
32

33.

Списки List
Реализации и конкретные реализации списков
AbstractList,
AbstractSequentialList,
ArrayList,
LinkedList,
CopyOnWriteArrayList,
Stack,
Vector
Класс
AbstractList
предоставляет
частичную
реализацию
для
интерфейса List. Реализует все
методы, кроме метода get().
Класс AbstractSequentialList расширяет
AbstractList,
чтобы
предоставить
поддержку для связных списков.
33

34.

Списки List
ArrayList<E> ─ список на базе массива (реализация List)
Конструкторы и реализация ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>,RandomAccess, Cloneable, java.io.Serializable {
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "
+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
}
34

35.

Списки List
Конструкторы и реализация ArrayList
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
}
Дополнительные методы
▪ void ensureCapacity(int minCapacity) ─ определение
вместимости
▪ void trimToSize() ─ “подгонка” вместимости
35

36.

Списки List
LinkedList<E> ─ двусвязный список
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element,
Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
36

37.

Списки List
Дополнительные методы
void addFirst(E o)
void addLast(E o)
E removeFirst()
E removeLast()
E getFirst()
E getLast()
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1);
list.addFirst(2);
list.addLast(6);
list.add(7);
list.addFirst(9);
list.removeLast();
for (Iterator<Integer> it = list.iterator();
it.hasNext();){
System.out.print(it.next() + " ");
}
9 2 1 6
37

38.

Списки List
Vector – потокобезопасная версия ArrayList в Java 1.0/1.1
Реализация класса Vector
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;
public Vector(int initialCapacity, int capacityIncrement) {…}
public Vector(int initialCapacity) {…}
public Vector() {…}
public Vector(Collection<? extends E> c) {…}
public synchronized void copyInto(Object[] anArray) {…}
public synchronized void trimToSize() {…}
…
}
38

39.

Списки List
Vector<Integer> v = new Vector<Integer>(3, 2);
v.addElement(new Integer(1));
v.addElement(new Integer(2));
v.addElement(new Integer(3));
v.addElement(new Integer(4));
Enumeration vEnum = v.elements();
while (vEnum.hasMoreElements()) {
System.out.print(vEnum.nextElement() + " ");
}
1 2 3 4
public interface Enumeration<E> {
boolean hasMoreElements();
E nextElement();
предоставление однопроходного
}
последовательного доступа к серии
объектов
39

40.

Списки List
Класс Stack - позволяет создавать очередь типа last-in-first-out
(LIFO)
public class Stack<E> extends Vector<E> {
public Stack() {}
public E push(E item) {…}
public synchronized E pop() {…}
public synchronized E peek() {…}
public boolean empty() {…}
public synchronized int search(Object o) {…}
}
char[] ar = "a - (b - (c - a) / (b + c) - 2)".toCharArray();
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < ar.length; i++) {
String symbol = new Character(ar[i]).toString();
if ("(".equals(symbol)) { stack.push(ar[i]); continue;
if (")".equals(symbol)) {
stack.pop();
continue; }
}
}
if (stack.isEmpty()){ System.out.println("баланс скобок соблюден");}
40

41.

ИНТЕРФЕЙС LISTITERATOR
41

42.

Интерфейс ListIterator
ListIterator<E> - итератор для списка, позволяющий проходить список
в любом направлении
interface ListIterator<E> extends Iterator {
boolean hasNext();
boolean hasPrevious();
E next();
E previous();
int nextIndex();
int previousIndex();
void remove();
void set(E o);
void add(E o);
}
42

43.

Интерфейс ListIterator
List<String> list = new LinkedList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
for (ListIterator<String> li = list.listIterator(); li.hasNext(); ){
String str = li.next();
if(str.equals("3")){
li.add("33");
li.remove();
}
}
43

44.

ОЧЕРЕДИ QUEUE
44

45.

Очереди Queue
FIFO
Очередь
–
хранилище
элементов (FIFO, LIFO),
предназначенных
для
обработки.
LIFO/FIFO
Очереди не могут хранить null.
У очереди может быть ограничен размер.
45

46.

Очереди Queue
возвращают
специальное
значение
выбрасывают
исключение
public interface Queue<E> extends Collection<E> {
}
boolean add(E e);
добавляет в конец очереди новый элемент и
возвращает true, если вставка удалась
E remove(); возвращает и удаляет головной элемент очереди
E element(); возвращает, но не удаляет головной элемент очереди
boolean offer(E e);
E poll();
E peek();
добавляет в конец очереди новый элемент и
возвращает true, если вставка удалась
возвращает и удаляет головной элемент очереди
возвращает, но не удаляет головной элемент очереди
Класс AbstractQueue –
частичная реализация
интерфейса Queue.
46

47.

Очереди Queue
PriorityQueue
приоритетами.
–
очередь
с
public class PriorityQueue<E> extends AbstractQueue<E> implements
java.io.Serializable {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
private transient Object[] queue;
public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}
public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator){}
public PriorityQueue(Collection<? extends E> c) {
}
public PriorityQueue(PriorityQueue<? extends E> c) { }
public PriorityQueue(SortedSet<? extends E> c) {
}
}
Очередь с приоритетами размещает элементы согласно естественному
порядку сортировки используя Comparable (по умолчанию).
Также можно указать специальный порядок размещения, используя
Comparator
47

48.

Очереди Queue
PriorityQueue
PriorityQueue<String> queue2
= new PriorityQueue<String>(4, Collections.reverseOrder());
queue2.offer("Oklahoma");
queue2.offer("Indiana");
queue2.offer("Georgia");
queue2.offer("Texas");
while (queue2.size() > 0) {
System.out.print(queue2.remove() + " ");
}
Texas Oklahoma Indiana Georgia
48

49.

Очереди Queue
ConcurrentLinkedQueue – потокобезопасная, неблокирующая
реализация Queue на связанных узлах (linked nodes)
public class ConcurrentLinkedQueue<E>
extends AbstractQueue<E>
implements Queue<E>, java.io.Serializable {
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
public ConcurrentLinkedQueue() {}
public ConcurrentLinkedQueue(Collection<? extends E> c) {}
}
49

50.

Очереди Queue
выбрасывают
исключение
void addFirst(E e); void push(E e);
E removeFirst(); E remove(); E pop();
E getFirst(); E element();
возвращают
специальное
значение
boolean offerFirst(E e);
E pollFirst(); E poll();
E peekFirst(); E peek();
выбрасывают
исключение
void addLast(E e);
E removeLast();
E getLast();
возвращают
специальное
значение
boolean offerLast(E e); boolean offer(E e);
E pollLast();
E peekLast();
boolean add(E e);
TAIL
HEAD
public interface Deque<E> extends Queue <E> {
50

51.

Очереди Queue.
Deque<E>
boolean remove(Object o);
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
boolean contains(Object o);
public int size();
Iterator <E> iterator();
Iterator <E> descendingIterator();
}
51

52.

Очереди Queue
LinkedList<E> ─ реализация FIFO/LIFO очереди
Deque<String> deque= new LinkedList<String>();
deque.offer("Oklahoma");
deque.offer("Indiana");
deque.offer("Georgia");
deque.offer("Texas");
while (queue.size() > 0){
System.out.print(queue.remove() + " ");
}
Oklahoma Indiana Georgia Texas
52

53.

Очереди Queue
ArrayDeque - реализация интерфейса Deque с использованием
массива.
public class ArrayDeque<E>
extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {
private transient E[] elements;
private transient int head;
private transient int tail;
public ArrayDeque() {
elements = (E[]) new Object[16];
}
public ArrayDeque(int numElements) {}
}
53

54.

Очереди Queue
ArrayDeque
Deque<String> stack = new ArrayDeque<String>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
while (!stack.isEmpty()){
System.out.print(stack.pop() + " ");
D C B A
}
Deque<String> queue = new ArrayDeque<String>();
queue.add("A");
queue.add("B");
queue.add("C");
queue.add("D");
while (!queue.isEmpty()){
System.out.print(queue.remove() + " ");
A B C D
}
54

55.

Очереди Queue
ConcurrentLinkedDeque – потокобезопасная, неблокирующая
реализация Deque на связанных узлах (linked nodes)
public class ConcurrentLinkedDeque<E>
extends AbstractCollection<E>
implements Deque<E>, java.io.Serializable {
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
public ConcurrentLinkedDeque() {}
public ConcurrentLinkedDeque(Collection<? extends E> c) {}
}
55

56.

КАРТЫ ОТОБРАЖЕНИЙ MAP
56

57.

Карты отображений Map
Интерфейс Map работает с
наборами пар объектов
«ключ-значение»
Все ключи в картах уникальны.
Уникальность ключей
определяет реализация
метода equals(…).
Для корректной работы с картами необходимо переопределить
методы equals(…) и hashCode(), допускается добавление
объектов без переопределения этих методов, но найти эти
объекты в Map вы не сможете.
57

58.

Карты отображений Map
public interface Map<K,V> {
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();
void putAll(Map<? extends K, ? extends V> m);
void clear();
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();
}
58

59.

Карты отображений Map
public static interface Map.Entry<K,V> {
boolean equals(Object o);
K getKey();
V getValue();
int hashCode();
V setValue(V value);
}
59

60.

Карты отображений Map
Класс AbstractMap - предоставляет частичную реализацию интерфейса Map.
public abstract class AbstractMap<K,V> implements Map<K,V>
Конкретные реализации карт отображений
HashMap
LinkedHashMap
TreeMap
IdentityHashMap
WeakHashMap
Hashtable
ConcurrentHashMap
ConcurrentSkipListMap
Properties
EnumMap
60

61.

Карты отображений Map
HashMap – неотсортированная и неупорядоченная карта,
эффективность работы HashMap зависит от того, насколько
эффективно реализован метод hashCode().
Реализация и конструкторы класса HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
public HashMap(int initialCapacity, float loadFactor) {...}
public HashMap(int initialCapacity) {...}
public HashMap() {...}
public HashMap(Map<? extends K, ? extends V> m) {...}
...
}
61

62.

Карты отображений Map
static class Entry<K, V>
implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
...
}
HashMap может принимать в качестве ключа null, но такой ключ
может быть только один, значений null может быть сколько
угодно.
62

63.

Карты отображений Map
HashMap
Map<Integer, String> map = new HashMap<Integer, String>();
map.put(new Integer(1), "one");
map.put(new Integer(2), "two");
map.put(new Integer(3), "three");
Set<Integer> keySet = map.keySet();
for (Iterator<Integer> it = keySet.iterator(); it.hasNext();){
Integer key = it.next();
System.out.println(key + " - " + map.get(key));
}
1 - one
2 - two
3 - three
63

64.

Карты отображений Map
HashMap
Map.Entry
Map<Integer, String> map = new HashMap<Integer, String>();
map.put(new Integer(1), "one");
map.put(new Integer(2), "two");
map.put(new Integer(3), "three");
Iterator<Map.Entry<Integer, String>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<Integer, String> entry = iter.next();
println(entry.getKey() + " -- " + entry.getValue());
}
1 -- one
2 -- two
3 -- three
64

65.

Карты отображений Map
LinkedHashMap – порядок, в котором хранятся элементы в
LinkedHashMap, определяется порядком установки их в
LinkedHashMap (insertion-order).
LinkedHashMap<Integer, String> map1 =
new LinkedHashMap<Integer, String>();
map1.put(new Integer(4), "four");
map1.put(new Integer(1), "one");
map1.put(new Integer(3), "three");
map1.put(new Integer(2), "two");
System.out.println(map1);
{4=four, 1=one, 3=three, 2=two}
65

66.

Карты отображений Map
public interface SortedMap<K,V> extends Map<K,V>{
Comparator<? super K> comparator();
Set<Map.Entry<K,V>> entrySet();
K firstKey();
SortedMap<K,V> headMap(K toKey);
Set<K> keySet();
K lastKey();
SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> tailMap(K fromKey);
Collection<V> values();
}
66

67.

Карты отображений Map
public interface NavigableMap<K,V> extends SortedMap<K,V> {
Map.Entry<K,V> lowerEntry(K key); <
Map.Entry<K,V> floorEntry(K key); <=
Map.Entry<K,V> higherEntry(K key); >
Map.Entry<K,V> ceilingEntry(K key); >=
K lowerKey(K key);
K floorKey(K key);
K higherKey(K key);
K ceilingKey(K key);
Map.Entry<K,V> pollFirstEntry();
Map.Entry<K,V> pollLastEntry();
Map.Entry<K,V> firstEntry();
Map.Entry<K,V> lastEntry();
67

68.

Карты отображений Map
NavigableMap<K,V> descendingMap();
NavigableSet navigableKeySet();
NavigableSet descendingKeySet();
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
SortedMap<K,V>
subMap(K fromKey, K toKey);
SortedMap<K,V>
headMap(K toKey);
SortedMap<K,V>
tailMap(K fromKey);
}
68

69.

Карты отображений Map
TreeMap –хранит элементы в порядке сортировки.
Реализация TreeMap
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;
private transient int size = 0;
private transient int modCount = 0;
public TreeMap() {…}
public TreeMap(Comparator<? super K> comparator) {…}
public TreeMap(Map<? extends K, ? extends V> m) {…}
public TreeMap(SortedMap<K, ? extends V> m) {…}
}
69

70.

Карты отображений Map
TreeMa
p
Map<String, Integer> treeMap = new TreeMap<String, Integer>();
treeMap.put("Smith", 30);
treeMap.put("Anderson", 31);
treeMap.put("Lewis", 29);
treeMap.put("Cook", 29);
System.out.println(treeMap);
{Anderson=31, Cook=29, Lewis=29, Smith=30}
70

71.

Карты отображений Map
Hashtable – унаследованная потокобезопасная коллекция, аналог
HashMap. Порядок следования пар ключ/значение не
определен.
Реализация Hashtable
public class Hashtable<K, V> extends Dictionary<K, V>
implements Map<K, V>,Cloneable, java.io.Serializable {
private transient Entry<K, V>[] table;
private transient int count;
public Hashtable(int initialCapacity, float loadFactor) { }
public Hashtable(int initialCapacity) {}
public Hashtable() {
}
public Hashtable(Map<? extends K, ? extends V> t) { }
public synchronized int size() {
}
public synchronized boolean isEmpty() {}
public synchronized Enumeration<K> keys() { }
}
71

72.

Карты отображений Map
Hashtable<String, String> ht = new Hashtable<String, String>();
ht.put("1", "One");
ht.put("2", "Two");
ht.put("3", "Three");
Collection c = ht.values();
Iterator itr = c.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
Three
Two
One
c.remove("One");
Enumeration e = ht.elements();
while (e.hasMoreElements()) {
Three
System.out.println(e.nextElement()); Two
}
72

73.

Карты отображений Map
ConcurrentHashMap – потокобеопасная версия HashMap. В отличие от
Hashtable и блоков synhronized на HashMap, данные представлены в
виде сегментов, разбитых по hash'ам ключей. В результате, дданные
лочатся по сегментам, а не по одному объекту.
ConcurrentSkipListMap – потокобезопасная версия TreeMap.
73

74.

Карты отображений Map
Класс Properties
(параметров).
предназначен
для
хранения
набора
свойств
public class Properties extends Hashtable<Object, Object> {…
public Properties() {}
public Properties(Properties defaults) {}
public synchronized Object setProperty(String key, String value) {}
public synchronized void load(Reader reader) {}
public synchronized void load(InputStream inStream) {}
public void store(Writer writer, String comments) {}
public void store(OutputStream out, String comments) {}
public synchronized void loadFromXML(InputStream in) {}
public void storeToXML(OutputStream os, String comment) {}
public void storeToXML(OutputStream os, String comment, String encoding){}
public String getProperty(String key) {}
public String getProperty(String key, String defaultValue) {}
public Enumeration<?> propertyNames() {}
public Set<String> stringPropertyNames() {}
public void list(PrintStream out) {}
public void list(PrintWriter out) {}
}
74

75.

Карты отображений Map
Properties
Properties capitals = new Properties();
Set states;
String str;
capitals.put("Illinois", "Springfield");capitals.put("Missouri", "Jefferson City");
capitals.put("Washington", "Olympia");capitals.put("California", "Sacramento");
capitals.put("Indiana", "Indianapolis");
states = capitals.keySet();
Iterator itr = states.iterator();
while (itr.hasNext()) {
str = (String) itr.next();
System.out.printlnstr + " is "
+ capitals.getProperty(str);
}
Missouri - Jefferson City
Illinois - Springfield
Indiana - Indianapolis
California - Sacramento
Washington - Olympia
str = capitals.getProperty("Florida", "Not Found");
System.out.println("The capital of Florida is "
+ str + ".");
The capital of Florida is Not Found.
75

76.

Карты отображений Map
EnumMap – карта отображений, в качестве ключей используются
элементы перечисления. Null ключи запрещены. Null значения
допускаются.
Конструкторы EnumMap
public class EnumMap<K extends Enum<K>, V>
extends AbstractMap<K, V>
implements java.io.Serializable, Cloneable{
public EnumMap(Class<K> keyType) {
}
public EnumMap(EnumMap<K, ? extends V> m) {
}
public EnumMap(Map<K, ? extends V> m) {
}
}
76

77.

Карты отображений Map
EnumMap
enum Size {
S, M, L, XL, XXL, XXXL;
}
...
EnumMap<Size, String> sizeMap
= new EnumMap<Size, String>(Size.class);
sizeMap.put(Size.S, "маленький");
sizeMap.put(Size.M, "средний");
sizeMap.put(Size.L, "большой");
sizeMap.put(Size.XL, "очень большой");
sizeMap.put(Size.XXL, "очень-очень большой");
sizeMap.put(Size.XXXL, "ну оооооочень большой");
for (Size size : Size.values()) {
System.out.println(size
+ ":" + sizeMap.get(size));
}
S:маленький
M:средний
L:большой
XL:очень большой
XXL:очень-очень большой
XXXL:ну оооооочень большой
77

78.

КЛАСС COLLECTIONS
78

79.

Класс Collections
Collections — класс, состоящий из статических методов,
осуществляющих различные служебные операции над
коллекциями.
79

80.

Класс Collections
sort
public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T> void sort(List<T> list, Comparator<? super T> c)
Сортировка списка, используя merge sort алгоритм, с гарантированной скоростью O (n*log n).
List<String> list1
= Arrays.asList("red", "greean", "blue");
Collections.sort(list1);
System.out.println(list1); [blue, greean, red]
List<String> list2
= Arrays.asList("greean", "red", "yellow", "blue");
Collections.sort(list2, Collections.reverseOrder());
System.out.println(list2);
[yellow, red, greean, blue]
80

81.

Класс Collections
binarySearch
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key)
public static <T>
int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
Бинарный поиск элементов в списке.
List<Integer> list3 = Arrays
.asList(2, 4, 7, 10, 11, 45, 50, 59, 60, 66);
println("(1) Index: “ + Collections.binarySearch(list3, 7));
(1) Index: 2
println("(2) Index: " + Collections.binarySearch(list3, 9));
(2) Index: -4
List<String> list4 = Arrays.asList("blue", "green", "red");
println("(3) Index: " + Collections.binarySearch(list4, "red"));
(3) Index: 2
println("(4) Index: " + Collections.binarySearch(list4, "cyan"));
(4) Index: -2
81

82.

Класс Collections
reverse
public static void reverse(List<?> list)
Меняет порядок элементов в списке
List<String> list1
= Arrays.asList("yellow", "red", "green", "blue");
Collections.reverse(list1);
System.out.println(list1);
[blue, green, red, yellow]
82

83.

Класс Collections
shuffle
public static void shuffle(List<?> list)
public static void shuffle(List<?> list, Random rnd)
List<String> list2
= Arrays.asList("yellow", "red", "green", "blue");
Collections.shuffle(list2);
System.out.println(list2);
[yellow, blue, green, red]
83

84.

Класс Collections
swap
public static void swap(List<?> list, int i, int j)
List<String> list = new
ArrayList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
System.out.println(list);
Collections.swap(list, 1, 3);
System.out.println(list);
[1, 2, 3, 4]
[1, 4, 3, 2]
84

85.

Класс Collections
fill
public static <T> void fill(List<? super T> list, T obj)
List<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add(new String("A"));
list.add("D");
System.out.println(list);
Collections.fill(list, new String("V"));
[A, B, A, D]
[V, V, V, V]
true
System.out.println(list);
System.out.println(list.get(0) == list.get(1));
85

86.

Класс Collections
copy
static <T> void copy(List<? super T> dest, List<? extends T> src)
List<String>
List<String>
srclst = new ArrayList<String> (5);
destlst = new ArrayList<String> (10);
srclst.add("a");
srclst.add("b");
destlst.add("d");
destlst.add("e");
destlst.add("f");
Collections.copy(destlst, srclst);
System.out.println(srclst);
System.out.println(destlst);
[a, b]
[a, b, f]
86

87.

Класс Collections
min, max
static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
List<Integer> list = new
LinkedList<Integer>();
list.add(-8);
list.add(4);
list.add(-5);
list.add(1);
System.out.println(Collections.min(list));
System.out.println(Collections.max(list));
-8
4
87

88.

Класс Collections
rotate
public static void rotate(List<?> list, int distance)
List<Integer> numbers = new ArrayList<Integer>();
for (int i = 0; i < 5; i++) {
numbers.add(i);
}
println(Arrays.toString(numbers.toArray()));
Collections.rotate(numbers, 3);
println(Arrays.toString(numbers.toArray())); [0, 1, 2, 3, 4]
[2, 3, 4, 0, 1]
88

89.

Класс Collections
replaceAll
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
List<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("A");
list.add("C");
System.out.println(list);
Collections.replaceAll(list, "A", "AA");
System.out.println(list);
[A, B, A, C]
[AA, B, AA, C]
89

90.

Класс Collections
indexOfSubList
lastIndexOfSubList
public static int indexOfSubList(List<?> source, List<?> target)
public static int lastIndexOfSubList(List<?> source, List<?> target)
List<String> arrlistsrc = new ArrayList<String>();
List<String> arrlisttarget = new ArrayList<String>();
arrlistsrc.add("A"); arrlistsrc.add("D");
arrlistsrc.add("C"); arrlistsrc.add("D");
arrlistsrc.add("E"); arrlistsrc.add("F");
arrlisttarget.add("C"); arrlisttarget.add("D");
arrlisttarget.add("E");
int index = Collections.indexOfSubList(arrlistsrc, arrlisttarget);
System.out.println(index);
2
90

91.

Класс Collections
unmodifibleCollection
<T> Collection<T> unmodifiableCollection(Collection<? extends T> c)
<T> Set<T> unmodifiableSet(Set<? extends T> s)
<T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s)
<T> List<T> unmodifiableList(List<? extends T> list)
<K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m)
<K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m)
List<String> list1 = Arrays.asList("red", "greean", "blue");
List<String> list = Collections.unmodifiableList(list1);
list.add("black");
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.Collections$UnmodifiableCollection.add(Unknown Source)
91

92.

Класс Collections
synchronizedCollection
<T> Collection<T> synchronizedCollection(Collection<T> c)
<T> Set<T> synchronizedSet(Set<T> s)
<T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
<T> List<T> synchronizedList(List<T> list)
<K,V> Map<K,V> synchronizedMap(Map<K,V> m)
<K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
Set<String> set = new HashSet<String>();
set.add("A");
set.add("B");
set.add("С");
set.add("D");
Set<String> synset = Collections.synchronizedSet(set);
92

93.

Класс Collections
checkedCollection
<E> Collection<E> checkedCollection(Collection<E> c, Class<E> type)
<E> Set<E> checkedSet(Set<E> s, Class<E> type)
<E> SortedSet<E> checkedSortedSet(SortedSet<E> s, Class<E> type)
<E> List<E> checkedList(List<E> list, Class<E> type)
<K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType)
<K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m, Class<K> keyType, Class<V> valueType)
Set<String> hset = new TreeSet<String>();
hset.add("A"); hset.add("B"); hset.add("C");
Set<String> tsset = Collections.checkedSet(hset, String.class);
System.out.println(tsset);
93

94.

Класс Collections
emptyIterator
emptyListIterator
emptyEnumerator
public static <T> Iterator<T> emptyIterator()
public static <T> ListIterator<T> emptyListIterator()
public static <T> Enumeration<T> emptyEnumeration()
ListIterator<String> it = Collections.emptyListIterator();
System.out.println(it.hasNext());
System.out.println(it.hasPrevious());
false
false
94

95.

Класс Collections
emptySet
emptyList
emptyMap
public static final <T> Set<T> emptySet()
public static final <T> List<T> emptyList()
public static final <K,V> Map<K,V> emptyMap()
Set<String> set = Collections.EMPTY_SET;
set.add("A");
Exception in thread "main"
java.lang.UnsupportedOperationException
at java.util.AbstractCollection.add(Unknown Source)
95

96.

Класс Collections
singleton
singletonList
singletonMap
public static <T> Set<T> singleton(T o)
public static <T> List<T> singletonList(T o)
public static <K,V> Map<K,V> singletonMap(K key, V value)
Set<String> set = Collections.singleton("A");
set.add("B");
Exception in thread "main"
java.lang.UnsupportedOperationException
at java.util.AbstractCollection.add(Unknown Source)
96

97.

Интерфейс Iterator
Удаление всех экземпляров определенного элемента е из
коллекции с :
c.removeAll(Collections.singleton(e));
Удаление всех элементов null из коллекции
c.removeAll(Collections.singleton(null));
97

98.

Класс Collections
nCopies
public static <T> List<T> nCopies(int n, T o)
List<String> list = Collections.nCopies(5, new String("A"));
println(list);
println(list.get(0) == list.get(1));
[A, A, A, A, A]
true
98

99.

Класс Collections
reverseOrder
public static <T> Comparator<T> reverseOrder()
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
List<Integer> list = new LinkedList<Integer>();
list.add(-8);
list.add(2);
list.add(-2);
list.add(8);
Comparator<Integer> cmp = Collections.reverseOrder();
Collections.sort(list, cmp);
System.out.println(list);
[8, 2, -2, -8]
99

100.

Класс Collections
enumeration
list
public static <T> Enumeration<T> enumeration(final Collection<T> c)
public static <T> ArrayList<T> list(Enumeration<T> e)
List<String> list = new ArrayList<String>();
Vector<String> v = new Vector<String>();
v.add("A"); v.add("B"); v.add("C"); v.add("D");
Enumeration<String> e = v.elements();
list = Collections.list(e);
System.out.println(list);
[A, B, C, D]
100

101.

Класс Collections
frequency
public static int frequency(Collection<?> c, Object o)
Collection<String> collection
= Arrays.asList("red","cyan","red");
System.out.println(
Collections.frequency(collection, "red"));
2
101

102.

Класс Collections
disjoin
boolean disjoint(Collection<?> c1, Collection<?> c2)
List<String> srclst = new ArrayList<String>(5);
List<String> destlst = new ArrayList<String>(10);
srclst.add("A"); srclst.add("B");
srclst.add("C"); srclst.add("D");
destlst.add("E"); destlst.add("F");
destlst.add("G");
boolean iscommon = Collections.disjoint(srclst, destlst);
System.out.println(iscommon);
true
102

103.

Класс Collections
addAll
<T> boolean addAll(Collection<? super T> c, T... elements)
List<String> arrlist = new ArrayList<String>();
arrlist.add("A"); arrlist.add("B");
arrlist.add("C"); arrlist.add("D");
System.out.println(arrlist);
boolean b = Collections.addAll(arrlist, "1", "2", "3");
System.out.println(arrlist);
[A, B, C, D]
[A, B, C, D, 1, 2, 3]
103

104.

Класс Collections
newSetFromMap
public static <E> Set<E> newSetFromMap(Map<E, Boolean> map)
Map<String, Boolean> map = new HashMap<String, Boolean>();
Set<String> set = Collections.newSetFromMap(map);
set.add("1"); set.add("2");
set.add("3"); set.add("4");
println("Set is: " + set);
println("Map is: " + map);
Set is: [3, 2, 1, 4]
Map is: {3=true, 2=true, 1=true, 4=true}
104

105.

Класс Collections
asLifoQueue
public static <T> Queue<T> asLifoQueue(Deque<T> deque)
Deque<Integer> deque = new ArrayDeque<Integer>(7);
deque.add(1);
deque.add(2);
deque.add(3);
deque.add(4);
deque.add(5);
Queue<Integer> nq = Collections.asLifoQueue(deque);
System.out.println(nq);
[1, 2, 3, 4, 5]
105

106.

СПАСИБО ЗА ВНИМАНИЕ!
ВОПРОСЫ?
Java
Collections
Author: Olga Smolyakova
Oracle Certified Java 6 Programmer
[email protected]
106