Java_amm_lesson_4

В предыдущих сериях
Static методы и переменные в Java – механизм, иногда использующийся, но в целом нарушающий ООП
Передача по ссылке и по значению – в Java примитивы передаются по значению, а объекты – по значению ссылки
Неизменяемые объекты – объекты, состояние которых невозможно изменить (все обертки над примитивами Java)
Класс Object – предок всех классов в Java. Методы equals, toString и hashCode – часто переопределяются

Глава 5.1
Классические структуры данных

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

Массивы
1
5
6
42
3
2
null
null
Лежат в памяти целым «куском»
Элементы проиндексированны
Чтобы вставить элемент в середину, нужно «сдвинуть» элементы справа
Вставка в конец очень быстрая
Получение элемента по индексу очень быстрое
Если не хватает размера, нужно создать новый массив, и скопировать его данные из старого

Оценим сложности стандартных операций
1
5
6
42
3
2
null
null
Получение по индексу
Вставка вконец
Вставка в середину и в начало
Удаление последнего элемента
Удаление элемента из середины

Связные списки
1
5
6
42
null
Состоят из узлов - Node
Каждая нода имеет как минимум ссылку на следующий элемент(односвязный список)
Как правило, эффективен только когда надо много вставлять в середину
next
next
next
next

Оценим сложности стандартных операций
1
5
6
42
null
Получение по индексу
Вставка вконец
Вставка в середину и в начало
Удаление последнего элемента
Удаление элемента из середины
next
next
next
next

Деревья
Чаще всего используются для поиска
Некоторые умеет автобалансироваться
8
3
1
6
4
7
10
14
13

Бинарное дерево
Оценим сложность поиска
8
3
1
6
4
7
10
14
13

Ассоциативный массив
1
Вася
56
Петя
14
Коля
11
Света
Ключ – значение
Как правило используется для получение элемента по ключу
Оценивать не будем (пока ☺)

Глава 5.1.1
Интерфейсы
Comparable и Comparator

Сравнение объектов на «больше» и «меньше» в Java
В Java часто приходится сравнивать объекты не только на равенство, но и на «больше» и «меньше»
Существует 2 способа сравнивать объекты в Java – реализовывать интерфейс Comparable или Comparator

Интерфейс Comparable
Ноль, если два объекта равны
число >0, если первый объект (на котором вызывается метод) больше, чем второй (который передается в качестве параметра);
число <0, если первый объект меньше второго
compareTo возвращает:

Интерфейс Comparable
«Дженерик», в данном случае говорит, что мы сравниваем Vehicle

Интерфейс Comparator
Метод получения или «геттер» для серийного номера

Вопросы и ответы

Глава 5.2
Коллекции в Java

Коллекции
Очень часто при разработке приходится хранить наборы одинаковых данных (мы уже встречали массивы)
Обычные массивы не очень удобны, т.к. они не расширяются автоматически, да и не имеют какого-то удобного API
Коллекции в Java используются как раз для хранения массивов данных.
Есть 2 основные ветки в Java Collection Framework.

Коллекции
Основа первой ветки – интерфейс Iterable
Iterable можно воспринимать как свойство “перечесляемый”, может отдать iterator с помощью метода iterator()
Все что Iterable можно использовать в цикле foreach (начиная с 5 Java)
В более старых версиях «пройтись» по каждому элементу струтуры данных можно было с помощью Iterator
Заметим, что в Iterator нет операции получения по индексу

Iterator

Iterator
Так жили в Java в доисторические времена

Коллекция - интерфейс
Коллекция добавляет операции add, contains
Так же в коллекциях появляется remove конкретного элемента
Основные интерфейсы наследники коллекций – List, Set, Queue

Коллекция - интерфейс

Set
Множество (то есть элементы уникальны)
Хранит каждый элемент 1 раз (проверяется с помощью equals)
Можно пройтись по всем элементам
Можно проверить, содержит ли Set существующий элемент
Нельзя получить элемент по индексу

Set

Set: популярные реализации
HashSet – самая популярная реализация. Использует хеш код для ускорения производительности
LinkedHashSet – поддерживает порядок вставки
TreeSet – наследует SortedSet, внутри красно-черное дерево. Туда можно положить только элементы, которые можно сравнивать (реализуют Comparable) или нужно передать специальный Comparator.

List
List – список. Основная фича – получение элементов по индексу
Две самые известные реализации – ArrayList и LinkedList
Чаще всего используют ArrayList

List

List: популярные реализации
ArrayList – самая популярная реализация. Внутри – массив.
Сложности операций – такие, как у массива
Автоматически расширяется при достижение предела размера внутреннего массива
Используется в 99% случаев

List: популярные реализации
LinkedList – связный список
Сложности алгоритмов как у связного списка
Имеет смысл использовать, только когда нужно много добавлять в середину
Очень популярный вопрос на собеседовании – разница между ArrayList и LinkedList

Queue (куеуе) - очередь
Очередь
Сохраняет принцип – первый пришел первый ушел
Популярная реализация - PriorityQueue

Queue

Фильтрация элементов коллекции: безопасные способы
removeIf
Создать новую коллекцию, и положить туда нужные элементы
Фичи java 8 + (пока мы про них не знаем)
Итератором
Нельзя – в forEach! (ConcurrentModificationException)

Вопросы и ответы

Глава 5.2.1
Utility - классы

Utility класс
Элемент «процедурного программирования»
По сути – набор процедур
Использовать надо с осторожностью
Закрыт final наследования модификатором final
Нельзя создать сущность (для этого делаем приватный конструктор)

Utility класс
final class – закрыт он наследования
Приватный конструктор по умолчанию не даст создать инстанс

Вопросы и ответы

Глава 5.3
Практика. Бенчмарк реализаций интерфейса Collection