Презентация "Коллекции в Java"

Подписи к слайдам:
  • Коллекции в Java
  • Антон Авдеев
  • <number>
  • Что такое коллекции?
  • Классы позволяющие хранить и производить операции над множеством объектов.
  • java.lang.Iterable
  • java.util.Collection
  • java.util.List - список
  • java.util.Set - множество
  • java.util.Queue - очередь
  • java.util.Map - карта, ассоциативный массив
  • <number>
  • Зачем нужны коллекции?
  • Array vs Collection
  • - Типизация данных - Безопасность типа хранимых данных на уровне компилятора - Фиксированный размер массива - Экономия памяти (примитивы) - Быстрый доступ к каждому элементу
  • - f.length
  • - Generics, либо Objects - Generics, либо приведение типов - Размер не фиксирован - Работа только с объектами - Скорость доступа зависит от способа имплементации коллекции - f.size()
  • <number>
  • Методы коллекций
  • Проверки на вхождение
  • boolean contains(Object o); ─ одного элемента
  • boolean containsAll(Collection c); ─ всех элементов коллекции c
  • Collection col = new ArrayList();
  • If (col.isEmpty()) { … как правильно проверять пустоту коллекции?
  • If (col.size() != 0) {…
  • <number>
  • Определение размера
  • int size(); ─ количество элементов
  • boolean isEmpty(); ─ проверка на пустоту
  • Методы коллекций
  • Добавление элементов
  • boolean add(E e); ─ одного элемента
  • boolean addAll(Collection c); ─ элементов коллекции
  • Удаление элементов
  • boolean remove(Object o); ─ одного элемента
  • boolean removeAll(Collection c); ─ элементов коллекции
  • boolean retainAll(Collection c); ─ удаление элементов не из коллекции c
  • void clear(); ─ удаление всех элементов
  • <number>
  • Преобразование в массив
  • <number>
  • Object[] toArray(); ─ создает новый массив
  • Object[] toArray(Object[] a); ─ использует переданный массив
  • list.add(“1”);
  • Foo[] foos = (Foo[]) list.toArray(new Foo[0]);
  • list.add(“2”);
  • Collection list = java.util.Arrays.asList(foos);
  • Итерирование
  • java.lang.Iterable:
  • методы Iterator<T> iterator();
          • boolean hasNext();
          • T next();
          • void remove();
  • Сколько итераций будет выполнено?
  • <number>
  • List list = new ArrayList(30);
  • for (Object o : list) {
  • System.out.println(o.toString());
  • }
  • for (Iterator iter = list.iterator(); iter.hasNext();) {
  • System.out.println(iter.next().toString());
  • }
  • Стандартные коллекции
  • <number>
  • Стандартные коллекции
  • <number>
  • ArrayList
  • <number>
  • ArrayList
  • При добавлении 11-го элемента
  • ArrayList может менять свой размер во время исполнения программы
  • Элементы ArrayList могут быть абсолютно любых типов в том числе и null
  • <number>
  • ArrayList<String> list = new ArrayList<>();
  • list.add("0");
  • ArrayList
  • Добавление в «середину» списка происходит в три этапа:
  • проверяется, достаточно ли места в массиве;
  • 2) подготавливается место для нового элемента с помощью System.arraycopy();
  • 3) перезаписывается значение у элемента с указанным индексом.
  • Удалять элементы можно двумя способами: — по индексу remove(index) — по значению remove(value)
  • <number>
  • ArrayList
  • Итоги
  • — Быстрый доступ к элементам по индексу за время O(1);
  • — Доступ к элементам по значению за линейное время O(n);
  • — Медленный, когда вставляются и удаляются элементы из «середины» списка;
  • — Позволяет хранить любые значения в том числе и null;
  • — Не синхронизирован.
  • <number>
  • LinkedList
  • <number>
  • LinkedList
  • Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны.
  • Реализует методы получения, удаления и вставки в начало, середину и конец списка.
  • Позволяет добавлять любые элементы в том числе и null.
  • <number>
  • List<String> list = new LinkedList<>();
  • list.add("0");
  • list.add("1");
  • LinkedList
  • <number>
  • Добавление элементов в «середину» списка
  • LinkedList. Применение (FIFO)
  • <number>
  • public class Queue {
  • private final LinkedList list = new LinkedList();
  • public void put(Object v) {
  • list.addFirst(v);
  • }
  • public Object get() {
  • return list.removeLast();
  • }
  • public boolean isEmpty() {
  • return list.isEmpty();
  • }
  • }
  • LinkedList
  • Итоги
  • — Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1);
  • — На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1);
  • — Позволяет добавлять любые значения в том числе и null. Для хранения примитивных типов использует соответствующие классы-оберки;
  • — Не синхронизирован.
  • <number>
  • HashCode
  • Если очень просто, то хеш-код — это число. Если более точно, то это битовая строка фиксированной длины, полученная из массива произвольной длины.
  • Ситуация, когда у разных объектов одинаковые хеш-коды называется — коллизией. Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода.
  • <number>
  • HashCode
  • 1. Для одного и того-же объекта, хеш-код всегда будет одинаковым
  • <number>
  • HashCode
  • 2. Если объекты одинаковые, то и хеш-коды одинаковые (но не наоборот, см. правило 3).
  • <number>
  • HashCode
  • 3. Если хеш-коды равны, то входные объекты не всегда равны (коллизия).
  • <number>
  • HashCode
  • 4. Если хеш-коды разные, то и объекты гарантированно разные.
  • <number>
  • Эквивалентность
  • Каждый вызов оператора new порождает новый объект в памяти.
  • <number>
  • public class BlackBox {
  • private int varA;
  • private int varB;
  • public BlackBox(int varA, int varB) {
  • this.varA = varA;
  • this.varB = varB;
  • }
  • }
  • Эквивалентность
  • Создадим класс для демонстрации BlackBox.
  • <number>
  • public class DemoBlackBox {
  • public static void main(String[] args) {
  • BlackBox object1 = new BlackBox(5, 10);
  • BlackBox object2 = new BlackBox(5, 10);
  • }
  • }
  • Эквивалентность
  • Содержимое этих объектов одинаково, то есть эквивалентно. Для проверки эквивалентности в классе Object существует метод equals(), который сравнивает содержимое объектов и выводит значение типа boolean true, если содержимое эквивалентно, и false — если нет.
  • <number>
  • object1.equals(object2);// должно быть true, поскольку содержимое объектов эквивалентно
  • object1.hashCode() == object2.hashCode()// должно быть true
  • Что выведется на экран в первом случае? Во втором?
  • Эквивалентность
  • При сравнение объектов, операция “==” вернет true лишь в одном случае — когда ссылки указывают на один и тот-же объект. В данном случае не учитывается содержимое полей.
  • <number>
  • public boolean equals(Object obj) {
  • return (this == obj);
  • }
  • public native int hashCode();
  • Эквивалентность
  • <number>
  • public class DemoBlackBox {
  • public static void main(String[] args) {
  • ...
  • BlackBox object3 = new BlackBox(5, 10);
  • BlackBox object4 = object3; // Переменная object4 ссылается на тот-же объект что и переменная object3
  • object3.equals(object4); // true
  • }
  • }
  • Эквивалентность
  • <number>
  • public class BlackBox {
  • ...
  • @Override
  • public int hashCode() {
  • final int prime = 31;
  • int result = 1;
  • result = prime * result + varA;
  • result = prime * result + varB;
  • return result;
  • }
  • }
  • Эквивалентность
  • <number>
  • public class BlackBox {
  • ...
  • @Override
  • public boolean equals(Object obj) {
  • if (this == obj)
  • return true;
  • if (obj == null)
  • return false;
  • if (getClass() != obj.getClass())
  • return false;
  • BlackBox other = (BlackBox) obj;
  • if (varA != other.varA)
  • return false;
  • if (varB != other.varB)
  • return false;
  • return true;
  • }
  • }
  • Эквивалентность
  • <number>
  • object1.equals(object2);
  • object1.hashCode() == object2.hashCode();
  • Что выведется на экран в первом случае? Во втором?
  • Эквивалентность
  • Требования к реализации equals()
  • reflexive. x.equals(x) == true
  • symmetric. Если x.equals(y) == true, то y.equals(x) должен быть тоже true.
  • transitive. Если x.equals(y) == true и y.equals(z) == true, то результат x.equals(z) тоже должен быть true
  • consistent. Для любых объектов x и y, если их содержимое не изменяется, то множественный вызов x.equals(y) должен возвращать одно и тоже значение
  • Для x.equals(null) == false.
  • <number>
  • HashMap
  • <number>
  • HashMap
  • HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение).
  • Ключи и значения могут быть любых типов, в том числе и null.
  • Данная реализация не дает гарантий относительно порядка элементов с течением времени
  • Каждый HashMap содержит ряд свойств: table — массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
  • threshold — предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое.
  • size — количество элементов HashMap-а;
  • <number>
  • Map<String, String> hashmap = new HashMap<>();
  • HashMap
  • hashCode()
  • Поиск элемента по ключу происходит в 2 этапа:
  • Поиск нужного контейнера (используя hashCode())
  • Поиск элемента в контейнере (используя equals())
  • <number>
  • HashMap
  • Добавление, получение, удаление элементов
  • Итераторы
  • <number>
  • hashmap.put("0", "zero");
  • hashmap.get(key);
  • hashmap.remove(key);
  • // 1
  • for (Map.Entry<String, String> entry : hashmap.entrySet())
  • System.out.println(entry.getKey() + " = " + entry.getValue());
  • // 2
  • for (String key : hashmap.keySet())
  • System.out.println(hashmap.get(key));
  • // 3
  • Iterator<Map.Entry<String, String>> itr = hashmap.entrySet().iterator();
  • while (itr.hasNext())
  • System.out.println(itr.next());
  • HashMap
  • Итоги
  • — Добавление элемента выполняется за время O(1);
  • — Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии;
  • — Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки;
  • — Не синхронизирован.
  • <number>
  • HashSet
  • <number>
  • HashSet
  • <number>
  • В множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов.
  • Методы аналогичны методам ArrayList за исключением того, что метод add(Object o) добавляет объект в множество только в том случае, если его там нет.
  • Set<Integer> intSet = new HashSet<>();
  • intSet.add(1);
  • intSet.add(4);
  • intSet.add(3);
  • intSet.add(1);
  • intSet.add(2);
  • intSet.add(3);
  • intSet.add(2);
  • [1, 2, 3, 4]
  • [3, 1, 4, 2]
  • [2, 4, 1, 3]
  • Лабораторная работа
  • <number>
  • Задание: Вычислить сколько раз каждая буква встречается в тексте.
  • public class UniqueChars {
  • private Map<Character, Integer> map = new HashMap<>();
  • private String text;
  • public String getText() {
  • return text;
  • }
  • public void setText(String text) {
  • this.text = text;
  • }
  • ...
  • }
  • Лабораторная работа
  • <number>
  • public class UniqueChars {
  • ...
  • public void calculate() {
  • for (char c : text.toCharArray()) {
  • if (Character.isLetter(c)) {
  • if (map.containsKey(c)) {
  • map.put(c, map.get(c) + 1);
  • } else {
  • map.put(c, 1);
  • }
  • }
  • }
  • }
  • ...
  • }
  • Лабораторная работа
  • <number>
  • public class UniqueChars {
  • ...
  • @Override
  • public String toString() {
  • String result = "";
  • for (Entry<Character, Integer> entry : map.entrySet()) {
  • result += "char: " + entry.getKey() +
  • "; count: " + entry.getValue() + "\n";
  • }
  • return result;
  • }
  • }
  • Лабораторная работа
  • <number>
  • Отдельный подсчет цифр;
  • Подсчет в указанном регистре (верхнем, нижнем, не учитывать);
  • interface Basket {
  • void addProduct(String product, int quantity);
  • void removeProduct(String product);
  • void updateProductQuantity(String product, int quantity);
  • void clear();
  • List<String> getProducts();
  • int getProductQuantity(String product);
  • }
  • Реализовать класс корзины интернет магазина по следующему интерфейсу:
  • Лабораторная работа
  • <number>
  • interface Smartable {
  • public List<Integer> removeInRange(List<Integer> list, int element, int start, int end);
  • public boolean isUnique(Map<String, String> map);
  • public Map<String, Integer> intersect(Map<String, Integer> map1, Map<String, Integer> map2);
  • public int countCommon(List<Integer> list1, List<Integer> list2);
  • public Set<String> removeEvenLength(Set<String> set);
  • public int maxOccurrences(List<Integer> list);
  • }
  • Лабораторная работа
  • <number>
  • public List<Integer> removeInRange(List<Integer> list, int element, int start, int end)
  • Который принимает на вход List<Integer>, значение, стартовый и конечный индекс).
  • Метод должен удалить все вхождения element между start (включительно) и end (исключительно) индексами. Вхождения вне этого индекса, а также другие значения должны остаться без изменений.
  • Например, если для списка
  • (0, 0, 2, 0, 4, 0, 6, 0, 8, 0, 10, 0, 12, 0, 14, 0, 16) вызвать метод removeInRange(list, 0, 5, 13) результат будет
  • (0, 0, 2, 0, 4, 6, 8, 10, 12, 0, 14, 0, 16).
  • Лабораторная работа
  • <number>
  • public boolean isUnique(Map<String, String> map);
  • Который возвращает true, если в отображении нет двух и более одинаковых value, и false в противном случае.
  • Для пустого отображения метод возвращает true.
  • Например, для метода {Вася=Иванов, Петр=Петров, Виктор=Сидоров, Сергей=Савельев, Вадим=Викторов} метод вернет true,
  • а для {Вася=Иванов, Петр=Петров, Виктор=Иванов, Сергей=Савельев, Вадим=Петров} метод вернет false.
  • Лабораторная работа
  • <number>
  • public Map<String,Integer> intersect(Map<String, Integer> map1, Map<String, Integer> map2);
  • Который возвращает отображение, который содержит пары «ключ=значение», присутствующие в обоих отображениях.
  • Например, для отображений {Janet=87, Logan=62, Whitaker=46, Alyssa=100, Stefanie=80, Jeff=88, Kim=52, Sylvia=95}
  • и {Logan=62, Kim=52, Whitaker=52, Jeff=88, Stefanie=80, Brian=60, Lisa=83, Sylvia=87}
  • Метод вернет {Logan=62, Stefanie=80, Jeff=88, Kim=52} (не обязательно в этом порядке)
  • Лабораторная работа
  • <number>
  • public int countCommon(List<Integer> list1, List<Integer> list2);
  • Который возвращает количество уникальных совпавших значений в обоих списках.
  • Например, для списков [3, 7, 3, -1, 2, 3, 7, 2, 15, 15] и [-5, 15, 2, -1, 7, 15, 36] метод вернет 4, т.к. совпали элементы -1, 2, 7 и 15.
  • Обратите внимание, что второй раз 15 не считаются, т.к. нужно совпадение уникальных значений.
  • Лабораторная работа
  • <number>
  • public Set<String> removeEvenLength(Set<String> set);
  • Который возвращает множество, в котором удалены все элементы четной длины из исходного множества.
  • Например, для множества ["foo", "buzz", "bar", "fork", "bort", "spoon", "!", "dude"] метод вернет ["foo", "bar", "spoon", "!"]
  • Лабораторная работа
  • <number>
  • public int maxOccurrences(List<Integer> list);
  • Который возвращает количество вхождений наиболее часто встречающегося элемента.
  • Например, для массива [4, 7, 4, -1, 2, 4, 7, 2, 15, 15] метод вернет 3, т.к. наиболее часто встречающееся значение 4 имеет 3 вхождения в массив.
  • Источники
  • https://google.ru
  • http://docs.oracle.com/javase/8/docs/api/index.html
  • https://habrahabr.ru/hub/java
  • <number>