Пример email-курса Java Ranger

Sorting Algorithms

Самых популярных алгоритмов сортировки пять.

Три итеративных –

  • пузырьком (Bubble Sort);
  • вставками (Insertion Sort);
  • выборками (Selection sort);

и два рекурсивных –

  • быстрая сортировка (Quicksort) и
  • сортировка слиянием (Merge Sort).

Пузырьковая сортировка, сортировка выборками и сортировка вставками построены на очень похожих принципах. Их иногда тяжело отличить одну от другой. А также можно их соединить и создать еще одну сортировку, которая тоже будет работать.

Первые три сортировки работают примерно n2 времени, а вторые две работают значительно быстрее, n*log2n, где n – это размер массива. К примеру, log2(1024) = 10.

ArgorithmAverageWorst
Linear SearchN
Binary Searchlog2N
Bubble SortN2N2
Selection SortN2N2
Insertion SortN2N2
Quick SortN∙log2NN2
Merge SortN∙log2NN∙log2N

При поиске, если массив не отсортирован, то единственный вариант – линейный поиск, если отсортирован, то бинарный поиск предпочтительнее. Это оценки для N→∞. Если у нас в массиве 4 элемента, то возможно бинарный поиск будет работать медленнее.

Алгоритмы Bubble SortInsertion SortSelection sort и Quicksort – in-place, они не требуют дополнительного выделения памяти, им нужно только память для счетчиков циклов и временной переменной. А Merge Sort – out-of-placeалгоритм, он требует столько же памяти, сколько ему дали сортировать элементов.

Most Common Exceptions in Java

24 самых популярных исключений в Java:

ArithmeticExceptionRENegativeArraySizeExceptionRE
ArrayIndexOutOfBoundsExceptionRENoSuchElementExceptionRE
ArrayStoreExceptionRENotSerializableExceptionEx
AssertionErrorErrNullPointerExceptionRE
ClassCastExceptionRENumberFormatExceptionRE
ClassNotFoundExceptionExOutOfMemoryErrorErr
CloneNotSupportedExceptionExSecurityExceptionRE
ConcurrentModificationExceptionREStackOverflowErrorErr
EOFExceptionExStringIndexOutOfBoundsExceptionRE
FileNotFoundExceptionExThreadDeathErr
IllegalArgumentExceptionREUnsupportedEncodingExceptionEx
InterruptedExceptionExUnsupportedOperationExceptionRE

 

В Java всего около 50 ключевых слов, и из них с исключениями связано 5: try, catch, finally, throw, throws. Из них catch, throw и throws применяются к экземплярам класса, причём работают они только с Throwable и его наследниками.

Инструкция throw очень аналогична инструкции return – она прекращает выполнение метода, дальше мы не идем. Если мы нигде не ставим catch, то у нас бросок Exception очень похож на System.exit() – система вырубается. Но мы в любом месте можем поставить catch и, таким образом, прекратить поломку.

Фактически при работе с исключениями весь материал делится на две части: синтаксис (ответ на вопрос, что компилятор пропустит, а что нет) и семантика (вопрос, как лучше делать) исключений. В отличие от вариантов с for, while, switch, Exceptions – более сложный механизм. Но он сложен не синтаксически, а семантически, по своему подходу. То есть не как правильно его использовать, а с каким смыслом его использовать. То есть вопрос, в каких ситуациях ломать систему и где, а в каких ситуациях ее восстанавливать.

В хорошей инженерной системе каждый модуль проверяет все аргументы на входе.

Можно еще сказать про такую иерархию способов прекратить действие по мощности: continue, break, return, throw.

  • continue прекращает выполнение данной итерации в цикле;
  • break прекращает выполнение данного цикла;
  • return – это инструкция выхода из данного метода;
  • throw – еще более сильная инструкция, она прекращает выполнение данного метода и метода, который его вызвал. Так как исключения позволяют сломать весь стек.

Collections

В некоторых языках программирования коллекции (maps, lists) являются частью синтаксиса языка. В Java же это отдельная тема – Collection API, а частью языка являются лишь массивы.

Три ключевые абстракции коллекций – это:

  • List;
  • Set;
  • Map.

Три ключевые реализации коллекций – это:

  • разные способы создать List(AllrayList, LinkedList);
  • хэш-структуры данных (HashSet, HashMap);
  • структуры данных на основе дерева (TreeSet, TreeMap).

При изучении коллекций рассматриваются два подхода – один с точки зрения ООП (тут важно иерархическое дерево классов и интерфейсов), а другой – с точки зрения реализации алгоритмов и структур данных (где важно, кто реально работает – в примере ниже – классы под пунктирной линией).

Иерархия коллекций (базовая, классов на самом деле больше):

Наследниками Collection являются List и Set. И на этом же уровне абстракции расположен Map, но он не является наследником Collection. В общем, это три разных класса, но у List и Set между собой больше общего, чем у Listи Map или Set и Map.

Сверху над пунктирной линией – интерфейсы, то есть абстракции, а снизу классы-реализации:

  • У List две реализации – ArrayList и LinkedList.
  • У Set непосредственная реализация – HashSet, а у NavigableSet есть реализация TreeSet.
  • У Map непосредственная реализация – HashMap, а у NavigableMap есть реализация TreeMap.

У Set и Map есть промежуточные интерфейсы SortedSet и SortedMap. Но в JDK нет ни одного класса, который бы от них реализовывался. В Set и Map объявлены какие-то методы и HashSet и HashMap реализуют только эти методы соответственно, поэтому наследуются напрямую. А у TreeSet и TreeMap намного больше методов, чем у HashSet и HashMap. Поэтому желательно иметь промежуточный интерфейс, который объявил вот эти добавочные методы. Это с точки зрения ООП.

С другой стороны, в коллекции встречается другой подход – говорить не про ООП, а про конкретные реализацииКонтейнеры (они же коллекции) – довольно сложные вещи и их реализовывать нетривиально. С точки зрения Кормена, вся эта иерархия вообще не важна, потому что все закодировано в классах (под пунктирной линией). И еще с его точки зрения HashSet и HashMap – это одно и то же – хэш-таблица и он рассказывает о конкретной структуре данных. А потом на ее основе можно получать разные имплементации. Также TreeSet и TreeMap – это одна структура, которая называется красно-черное дерево.

Конкретно в JDK класс HashMap – полноценный, а класс HashSet на самом деле не реализован, он весь сделан через HashMap. Хотя с точки зрения ООП Set и Map – абсолютно разные вещи и общий предок у них только java.lang.Object.

В коллекциях есть ряд классов, в которых называние начинается со слова Abstract: AbstractList, AbstractSet, AbstractMap – это абстрактные классы, где накоплена реализация.

Enum

enum появились в Java 5 – это определенный ссылочный тип данных, который гарантирует точное количество экземпляров данного типа. Если Singleton – это полностью искусственная конструкция, то в enum обеспечивается языковыми средствами ограниченное количество экземпляров. Предок enum – это класс java.lang.Enum<E extends Enum<E>>.

Пример enum:

Данный код эквивалентен этому:

У enum могут быть поля, но записываются они после экземпляров. Также может быть, конструктор, но тогда экземпляры должны содержать данные, идущие аргументами в конструктор:

Отличия enum от полноценных классов:

  1. У них обязательно должны бытьэкземпляры (хотя бы один).
  2. Перечисленные экземпляры enum– это единственные экземпляры, которые будут существовать на всем протяжении жизни JVM.
  3. enumвообще никак не наследуются (ни они, ни от них), но они могут имплементить интерфейсы.

В heap место могут занимать три вещи: экземпляры классамассивы и enum. Экземпляры интерфейсов и абстрактных классов нельзя создавать.