Saint Petersburg, 2012 Java Lecture #1 Intro DSA Collections. - презентация

1 Saint Petersburg, 2012 Java Lecture #1 Intro DSA Collections

2 Java Platform 2

3 Java Enterprise Edition 3

4 Spring 4

5 DSL Groovy – синтаксический сахар. Скриптоподобный язык с динамической типизацией. 5 Clojure – современный диалект Lisp. Функциональный язык программирования. Scala – функциональный, объектно-ориетированный язык. AspectJ – аспект-ориетированный язык. Используется в Spring. JRuby– порт языка Ruby для JVM. Jython– порт языка Python для JVM. Используется в IBM WebSphere.

6 Best Practices Используйте интерфейс только для определения типов. Шаблон интерфейса констант - это неудачный вариант использования интерфейсов. 6 Проверяйте параметры в публичных методах.

7 Best Practices Возвращайте пустой объект, а не null 7

8 Best Practices 8 Для таких случаев есть паттерн Null Object

9 Data Structures. Collections and Generics Cтруктуры данных Collections Framework 9

10 Структуры данных Структуры данных нужны для эффективной организации работы с информацией Каждая структура данных имеет свои преимущества и недостатки Виды структур: o Array o Linked List o Set 10

11 Виды структур данных o Queue o Stack o Map o Tree 11

12 Collections Классы, относящиеся к Collections Framework, находятся в пакетах java.util и java.util.concurrent Collections Framework содержит готовые реализации основных структур данных и алгоритмов: списки, множества, очереди, стэки, хэш-таблицы, деревья. 12

13 Collection interface Интерфейс Collection содержит базовые методы работы с коллекциями (множествами элементов) Вставка: add(Object), addAll(Collection) Удаление: remove(Object), removeAll(Collection), retainAll(Collection) Поиск: contains(), containsAll(), size(), isEmpty() Просмотр: toArray(), iterator() 13

14 Interfaces List – упорядоченный список нумерованных элементов ArrayList LinkedList Set – набор уникальных элементов HashSet – для собственных объектов надо пересмотреть hashCode() TreeSet – поддерживает сортировку через интерфейс Comparable Queue – очередь, обычно FIFO, хранит список объектов, предназначенных для обработки. Реализации на основе массивов и связанных списков Deque BlockingQueue 14

15 Best Practices 15 Во имя эффективности (без обязательности ее достижения) делается больше вычислительных ошибок, чем по каким-либо иным причинам, включая непроходимую тупость. William A. Wolf Мы обязаны забывать о мелких усовершенствованиях, скажем, на 97% рабочего времени: опрометчивая оптимизация – корень всех зол. Donald E. Knuth Что касается оптимизации, то мы следуем двум правилам: Правило 1: Не делайте этого. Правило 2 (только для экспертов): пока не делайте этого – т.е. пока у вас нет абсолютно четкого, но неоптимизированного решения. M. A. Jackson

16 LinkedList vs ArrayList 16

17 Best Practices Для ссылки на объект используйте его интерфейс 17

18 Map interface Интерфейс Map описывает таблицу соответствий ключ-значение: словарь, DNS, foreign key etc – и методы работы с ними: Изменение: get(Object), put(Object, Object), putAll(Map), remove(Object), clear() Просмотр: keySet(), values(), entrySet() Инфо: containsKey(Object), containsValue(Object), size(), isEmpty() 18

19 HashMap HashMap – самая популярная реализация интерфейса Map. Основные параметры: size – количество элементов capacity - емкость таблицы load factor – коэффициент загрузки (size/capacity) threshold – порог числа эл-тов перед увеличением таблицы (capacity*load factor) HashMap(): capacity = 16, load factor = 0.75 Чем больше load factor, тем реже перехеширование. Но коллизий больше. 19

20 Другие Map IdentityHashMap – сравнение ключей по ссылке. WeakHashMap - использует WeakReference LinkedHashMap – сохраняет порядок вставки элементов TreeMap – аналогичен TreeSet 20

21 Types of Collections. Sorting and ordering. 21

22 Collection extends Iterable interface Collection extends Iterable {...} interface Iterator { boolean hasNext(); E next(); void remove(); } Итератор (курсор) позволяет просмотреть элементы контейнера, не принимая во внимание конечную реализацию самого контейнера. Поддерживается в конструкции for each. Итератор становится недействительным в случае изменения коллекции в процессе просмотра. 22

23 Collection extends Iterable interface Collection extends Iterable {...} interface Iterator { boolean hasNext(); E next(); void remove(); } Пример: Collection c = new ArrayList(); c.add("A"); c.add(1L); c.add(2.3f); Iterator i = c.iterator(); while (i.hasNext()) { Object obj = i.next(); System.out.println(obj); } 23

24 Sorting with java.lang.Comparable Для поддержки сортировки в Java Collections используется интерфейс Comparable, который реализуют стандартные типы данных. Чтобы сравнивать объекты необходимо реализовать метод compareTo(Object), который возвращает: 0 – если объекты равны > 0 – если this больше < 0 – если this меньше sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) (x.compareTo(y) > 0 && y.compareTo(z) > 0) -> x.compareTo(z)>0 x.compareTo(y)==0 -> sgn(x.compareTo(z)) == sgn(y.compareTo(z)) 24

25 Comparable example Integer extends Number implements Comparable { int compareTo(Integer anotherInteger) { int thisVal = this.value; int anotherVal = anotherInteger.value; return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); } 25

26 Sorting with Java.util.Comparator Также можно сравнивать объекты с помошью внешнего объекта, не изменяя код самих объектов. Для этого используется интерфейс java.util.Comparator, в котором необходимо реализовать метод compare(Object, Object) Сравнение производится по полям класса с помошью getterов Классы-компараторы нужны в случае, когда объекты сортированных коллекций не реализуют интерфейс Comparable. 26

27 Java.util.Collections Класс Collections содержит статические методы работы с коллекциями: Создание immutable коллекций Shuffle Сортировочки, binary Search Min, max Thread safe synchronized collections Index of sublist Etc Класс Arrays Arrays – то же самое, только с массивами Arrays, Collections & Apcahe CollectionUtils 27

28 Google Guava Collections Часть проекта Google Guava. Это библиотека создана из частей часто используемого кода в Google. Если хочется чего-то странного, то с большой долей вероятности это там есть. 28

29 Library Effective Java. Programming Language Guide Item 25. Prefer Lists to Arrays och%20arrays%20prefer&pg=PA119#v=onepage&q&f=false och%20arrays%20prefer&pg=PA119#v=onepage&q&f=false Thinking In Java by Bruce Eckel Java Interview Design Patterns - Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides OReilly. Java.Generics.and_Collection s.Oct