Модуль 4. Дженерики и коллекции в Java. Тема 4.3 Коллекции, HashSet, HashMap и TreeMap

4.43M

Category:

programming

Модуль_4_Тема_3

1. Модуль 4. Дженерики и коллекции в Java. Тема 4.3 Коллекции, HashSet, HashMap и TreeMap

Кнапп Иван
Java разработчик в компании «Альфа-Капитал»

2.

Структура презентации
1. Алгоритмы
2. Хэш-таблицы
3. Хеширование
4. HashMap
5. HashSet
6. TreeMap
7. TreeMap
8. Практика
9. Заключение
10.Задачи
2

Линейный поиск
Одна из основных задач при работе с алгоритмами — оценка эффективности программы и поиск
наиболее экономичного подхода.
Задача:
Дан массив целых чисел длины N. Нужно найти в нём заданное число x и вернуть его индекс. Если x в
массиве не встречается — вернуть -1.
Решение(не самое лучшее):
Простым перебором сравниваем все элементы
массива с искомым числом
Алгоритм решает поставленную задачу. Но насколько быстро он это делает?
Попробуем понять, сколько элементарных операций совершается в процессе его работы. Под
элементарной операцией понимают любую арифметическую операцию или операцию сравнения.
В реализации алгоритма видно, что для каждого элемента массива будет выполнена одна
элементарная операция — сравнение с x
4

5.

Линейный поиск
Можем сказать, что скорость работы алгоритма в худшем случае пропорциональна размеру массива.
На математическом языке ещё говорят: «Вычислительная сложность алгоритма линейно зависит
от размера входных данных».
Из-за того, что у описанного алгоритма поиска время работы линейно зависит от размера входных
данных, он называется линейным поиском.
И будет обозначаться O(n) - читается «о от эн» или «о большое от эн»
5

6.

Бинарный поиск
Есть и другой способ решить задачу поиска элемента в массиве. Если элементы в массиве
упорядочены по возрастанию, то найти нужный можно гораздо быстрее.
Задача всё та же найти элемент в массиве, но
Изменились условия массив теперь отсортирован
И мы можем применить бинарный поиск, еще его
двоичный поиск, метод деления пополам
Алгоритм: состоит из 2 шагов
1) Определение значения элемента в середине структуры данных. Полученное значение сравнивается
с ключом.
2) Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов,
иначе — во второй.
Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет
пустым интервал для поиска.
6

7.

Бинарный поиск
Основное преимущество бинарного поиска заключается в его логарифмической временной
сложности: O(log n), где (n) — это количество элементов в массиве.
Таким образом, бинарный поиск значительно более эффективен, чем линейный поиск, особенно для
больших массивов, поскольку с каждым шагом количество рассматриваемых элементов уменьшается
вдвое.
7

8.

Сравнение алгоритмов
Сравнение времени выполнения алгоритмов поиска
линейного O(n) и бинарного O(log n)
Обратите внимание, что на небольших объёмах входных данных разница между линейным и
бинарным поиском не такая уж большая. Но чем больше данных на входе — тем сильнее заметна
разница.
8

9.

Хеш-таблица
9

10.

Задача
Вы разрабатываете систему управления библиотекой, где необходимо быстро находить информацию о книгах
по их уникальному идентификатору (ISBN).
Система должна поддерживать операции добавления новых книг, удаления существующих и поиска
информации о книге по её ISBN.
10

11.

Вопрос
Какую структуру данных можно использовать для хранения таких данных, учитывая следующие
условия:
• Данные представлены в виде объектов, которые получены из базы данных или загружены из файла.
• Важно, чтобы эти операции выполнялись максимально быстро, даже при большом количестве книг в
библиотеке.
11

12.

Ответ
В зависимости от того, как планируется использовать эти данные, можно рассмотреть следующие
варианты:
• Массивы
• Списки
Объекты могут храниться в массивах или списках. Этот подход возможен, но для поиска конкретного
элемента в таких коллекциях, например, по уникальному идентификатору (ISBN), потребуется перебрать
все элементы. Это может быть неэффективно для коллекций, содержащих несколько тысяч
элементов, так как время поиска будет иметь сложность O(n).
Чтобы ускорить поиск объектов по идентификатору, можно использовать коллекции, основанные на
хеш-таблицах.
Они позволяют значительно сократить время поиска до сложности O(1).
О(1) – константное время, не зависит от кол-ва элементов в списке
12

13.

Хеш-таблица
Хеш-таблица — это структура данных, которая работает как ассоциативный массив, то есть хранит данные в
виде пар ключ-значение.
В хеш-таблицах можно размещать пары, такие как
идентификатор — объект,
название — объект,
номер — объект
и так далее.
Она поддерживает основные операции:
• Добавление пары
• Поиск объекта по ключу
• Удаление объекта по ключу
Как следует из названия, любая хеш-таблица использует механизм хеширования.
13

14.

Хеширование
14

15.

Определение
Хеширование — это превращение входных данных произвольной длины в выходную строку
фиксированной длины или число.
Пример:
15

16.

Определение
хеш-код
хеш-таблица
Хеш-таблица применяет этот код для
поиска элемента без необходимости
проходить через все ключи.
63350368
Alice
0
В самом простом случае хеш-код
используется для определения индекса
в массиве (номера ячейки), где
находится нужный элемент.
66965
Bob
1
-1891246254
Charlie
2
номера ячейки
16

17.

Вопрос
Может ли для разных строк или любых других объектов вычисляться один и
тот же хеш-код?
17

18.

Ответ
Да, это явление известно как коллизия.
Для решения коллизий применяются различные методы.
В Java, если несколько элементов попадают в одну и ту же ячейку массива,
определяемую хеш-кодом, то нужный элемент находится с помощью вызова
метода equals для каждого элемента в этой ячейке.
18

19.

Пример хеш-таблицы с коллизией
Alice
Atos
Bob
Barry
Charlie
Chappie
Billy
Ячейка массива
Объекты с одинаковым хеш-кодом
19

20.

Реализация хэш-таблицы в Java
HashMap
20

21.

Коллекция HashMap
Ответ на вопрос, заданный в начале лекции, следующий:
Для хранения объектов, которые часто нужно искать, изменять, удалять или добавлять по их
идентификатору, в Java рекомендуется использовать коллекцию HashMap.
Это связано с тем, что HashMap построена на основе хеш-таблиц.
Визуально HashMap можно представить как массив, где идентификатор используется в качестве
ключа, а связанный с ним объект — в качестве значения.
21

22.

Коллекция HashMap
Alice
55
Atos
54
Bob
14
Barry
22
Billy
Chappie
65
Charlie
7
44
Ячейка массива
Объекты с одинаковым хеш-кодом
22

23.

Интерфейс Map
Коллекция HashMap реализует основной интерфейс Map<K,V>, который можно представить как
словарь или справочник, где каждому ключу соответствует определённое значение.
<<Interface>>
Map
HashMap
<<Interface>>
SortedMap
<<Interface>>
NavigableMap
LinkedHashMap
TreeMap
23

24.

Методы интерфейса Map часть 1
• put(k,v) — добавляет элемент v с ключом k в коллекцию.
• putAll(otherMap) — добавляет все элементы из другой коллекции Map.
• get(k) — возвращает значение, связанное с ключом k; возвращает null, если такого ключа
нет.
• remove(k) — удаляет элемент с указанным ключом и возвращает его значение.
• containsKey(k) — возвращает true, если в коллекции есть указанный ключ.
• containsValue(v) — возвращает true, если указанное значение присутствует в коллекции
хотя бы один раз. Обратите внимание, что операция выполняется за время O(n).
24

25.

Методы интерфейса Map часть 2
• size() — возвращает количество элементов в коллекции.
• isEmpty() — проверяет, пуста ли коллекция (возвращает true, если количество элементов
равно нулю).
• clear() — удаляет все элементы из коллекции.
• keySet() — возвращает набор (Set) всех ключей, содержащихся в коллекции.
• values() — возвращает коллекцию (Collection) всех значений, содержащихся в коллекции.
• entrySet() — возвращает набор (Set) пар ключ-значение (Entry) из коллекции.
25

26.

Особенности реализации HashMap
Чтобы операции вставки, удаления и поиска в HashMap для произвольных классов в Java
выполнялись как можно быстрее, желательно приблежаясь к O(1).
Для этого нужно правильно переопределить методы equals() и hashCode(), следуя
определённым правилам:
1. Метод hashCode должен возвращать одно и то же значение при многократных вызовах на
одном и том же объекте.
2. Если два объекта считаются равными (то есть equals возвращает true), то их хеш-коды
должны быть одинаковыми.
3. Если объекты разные, их хеш-коды могут быть одинаковыми, но для повышения
производительности хеш-таблиц лучше, чтобы они были разными.
26

27.

Вопрос
Что произойдёт, если изменить ключ объекта, который уже добавлен в HashMap?
Например, если изменить поле, используемое для вычисления хеш-кода?
27

28.

Ответ
В такой ситуации в HashMap могут появиться дублирующиеся объекты, что может привести к
трудноуловимым ошибкам.
Чтобы избежать этой проблемы, рекомендуется использовать неизменяемые (immutable) объекты в
качестве ключей в HashMap. Неизменяемыми называются классы, поля объектов которых не могут
быть изменены после создания.
28

29.

Переопределение метода equals
29

30.

Переопределение метода hashCode
Вручную как мы уже делали:
Или используя библиотеку из стандартного пакета java.util:
30

31.

Пример работы с HashMap
Создадим коллекцию HashMap, где в качестве ключа используем тип String (isbn), а в
качестве значения тип String (название книги).
31

32.

Пример работы с HashMap
Имейте в виду, что два элемента не могут иметь одинаковый ключ — в этом случае
значение будет заменено новым. Однако два одинаковых значения могут существовать
под разными ключами.
Вопрос
А можно ли использовать null в качестве ключа ?
32

33.

Пример работы с HashMap
HashMap позволяет это делать
33

34.

Еще одна задача
34

35.

Задача
Предположим, у вас есть библиотека, и вы хотите отслеживать все различные
жанры, которые представлены в ваших книгах. Поскольку жанры должны быть
уникальными и порядок их хранения не важен.
Какую коллекцию следует использовать в таком случае, чтобы можно было
быстро определить к какому жанру принадлежит книга и какие жанры есть вообще
?
35

36.

Задача
Как и в предыдущем примере, можно было бы использовать массивы или списки
для решения задачи.
Однако проблема медленного поиска (полного перебора) остается актуальной.
HashMap мог бы стать альтернативой, но для этого каждому жанру необходимо
присвоить уникальный идентификатор.
Что делать, если идентификатора нет или объект небольшой? Если использовать
все поля объекта в качестве ключа, фактически объект станет ключом.
Например, если в коллекции хранятся строки, и ключ, и значение будут строками.
Хранить две строки для одного небольшого объекта избыточно. В таких случаях
проще хранить только одну строку. Для этого используют множества, которые
представляют собой еще один вид коллекции для хранения данных.
36

37.

Реализация множества в Java.
Коллекция HashSet
37

38.

Множество
В математике: это совокупность объектов, обладающих общим свойством. Над множеством можно выполнять
такие операции, как объединение, пересечение и разность.
В программировании: это структура данных, хранящая объекты определенного типа, где порядок элементов не
имеет значения. Обычно она позволяет выполнять стандартные математические операции над множествами.
В Java структура данных множества представляет собой коллекцию (массив) уникальных элементов, например:
{ a, b, c, d, e } — множество символов.
Одной из наиболее часто используемых коллекций для представления множеств является HashSet, которая
базируется на HashMap и, следовательно, на хеш-таблицах.
38

39.

Особенности реализации
HashSet передает выполнение всех своих методов внутреннему объекту HashMap.
В этой реализации сам объект выступает в роли ключа, а в качестве значения используется
специальный объект-заглушка(Dummy).
39

40.

Код из стандартной библиотеки
Как видим в конструкторе HashSet объявляется HashMap
40

41.

Коллекция HashSet
Ячейка массива
Alice
Dummy
Atos
Dummy
Bob
Dummy
Barry
Dummy
Charlie Dummy
Billy
Dummy
Dummy – объект заглушка
Chappie Dummy
Объекты с одинаковым хеш-кодом
41

42.

Интерфейс Set
<<Interface>>
Iterable
Коллекция HashSet – реализует основной
интерфейс Set<E>.
<<Interface>>
Collection
<<Interface>>
Set
HashSet
<<Interface>>
SortedSet
LinkedHashSet
<<Interface>>
NavigableSet
TreeSet
42

43.

Методы интерфейса Set часть 1
• add(e) — добавляет элемент в множество, если он отсутствует. Возвращает true, если
добавление прошло успешно.
• addAll(collection) — добавляет все элементы из коллекции в множество, если они
отсутствуют. Возвращает true, если добавление прошло успешно.
• clear() — удаляет все элементы из множества.
• contains(o) — возвращает true, если указанный объект присутствует в множестве.
• containsAll(collection) — возвращает true, если все элементы из указанной коллекции
присутствуют в множестве.
• isEmpty() — возвращает true, если множество пусто.
43

44.

Методы интерфейса Set часть 2
• iterator() — возвращает итератор по элементам сета.
• remove(e) — удаляет элемент из множества. Вернет true, если такой элемент был.
• removeAll(collection) — удаляет из множества все элементы, которые есть в коллекции.
Вернет true, если сет был изменен в результате вызова метода.
• retainAll(collection) — оставляет в сете только элементы, которые есть в коллекции,
удаляет все остальные. Вернет true, если сет был изменен в результате вызова метода.
• size() — возвращает количество элементов в множестве.
• toArray() — возвращает массив, содержащий все элементы множества.
44

45.

Пример работы с HashSet
В качестве объектов будем использовать String
45

46.

Сравнение HashSet и ArrayList
Свойство
HashSet
ArrayList
Сохраняет порядок
вставки элементов
Нет
Да
Позволяет хранить
дубликаты
Нет
Да
Скорость поиска
О(1)
О(n)
46

47.

Реализация коллекции TreeMap в Java
47

48.

TreeMap структура
Ранее мы обсудили одну из основных реализаций интерфейса Map — HashMap. Теперь давайте
рассмотрим другую реализацию этого интерфейса — коллекцию TreeMap.
<<Interface>>
Map
HashMap
<<Interface>>
SortedMap
<<Interface>>
NavigableMap
LinkedHashMap
TreeMap
48

49.

TreeMap структура
TreeMap — это структура данных, которая организует элементы в порядке сортировки по
ключам.
Это означает, что коллекция управляет элементами в виде пар ключ-значение.
Операции добавления, удаления, поиска и изменения элементов осуществляются
исключительно через их ключи, которые используются для сортировки элементов внутри
коллекции.
49

50.

TreeMap структура
TreeMap построен на основе красно-черного дерева, что позволяет ему хранить элементы
в отсортированном по ключам порядке или в порядке, определённом компаратором,
заданным при создании коллекции.
Главным свойством красно-черного дерева является то что оно является бинарным и в то
же время сбалансированным – это гарантирует скорость работы
50

51.

Структура Дерева
Корень
Дерево — это структура данных,
включающая узлы и соединяющие их
ребра.
• Каждый узел связан с другим
узлом через ребро.
Узел
Ребро
• В дереве всегда есть хотя бы один
узел без входящих ребер, который
называется корнем.
• Узлы, не имеющие исходящих
Лист
ребер, называются листьями.
51

52.

Красно-черное дерево
Красно-черное дерево является является бинарным деревом
52

53.

Свойства красно-черного дерева
Бинарное дерево (или двоичное) — это
3
разновидность структуры данных типа дерева,
характеризующаяся следующими особенностями:
3
10
• каждый узел может иметь не более двух
дочерних узлов;
1
6
14
• левые потомки всегда меньше текущего узла;
• правые потомки всегда больше текущего узла;
4
7
53

54.

Свойства красно-черного дерева
Красно-черное дерево — это бинарное дерево, где каждый узел имеет цвет: красный или
черный.
• Для поиска элемента в таком дереве необходимо сравнить искомое значение с корневым
узлом (узлом, не имеющим предков).
• Если искомое значение больше корневого узла, переходим к правому потомку;
• Если значение меньше, то перемещаемся к левому потомку и продолжаем сравнение с
ним.
• Этот процесс продолжается до тех пор, пока не будет найден нужный элемент или не
достигнут лист дерева (узел без потомков).
54

55.

Красно-черное дерево
13
17
8
1
15
11
NIL
NIL
NIL
NIL
25
NIL
NIL
27
22
6
NIL
NIL
NIL
NIL
NIL
55

56.

Методы TreeMap
Как мы помним из иерархии коллекций класс TreeMap реализует интерфейс NavigableMap,
который в свою очередь наследует методы интерфейса SortedMap. Давайте проговорим
какие есть методы у этих интерфейсов
56

57.

Методы интерфейса SortedMap
• K firstKey(), K lastKey() — возвращает ключ первого или последнего элемента в map
соответственно.
• SortedMap<K, V> headMap(K end) — возвращает map, содержащий элементы до
указанного ключа (включая его).
• SortedMap<K, V> tailMap(K start) — возвращает map, начиная с указанного ключа и до
конца текущей коллекции.
• SortedMap<K, V> subMap(K start, K end) — возвращает map с элементами в пределах
заданного диапазона ключей.
57

58.

Методы интерфейса NavigableMap
• Map.Entry<K, V> ceilingEntry(K key) — возвращает элемент с ключом, который больше или равен
указанному ключу key. Если такого элемента нет, возвращается null.
• Map.Entry<K, V> floorEntry(K key) — возвращает элемент с ключом, который меньше или равен
указанному ключу key. Если такого элемента нет, возвращается null.
• Map.Entry<K, V> higherEntry(K key) — возвращает элемент с ключом, который строго больше
указанного ключа key. Если такого элемента нет, возвращается null.
• Map.Entry<K, V> lowerEntry(K key) — возвращает элемент с ключом, который строго меньше
указанного ключа key. Если такого элемента нет, возвращается null.
• Map.Entry<K, V> firstEntry() — возвращает первый элемент в map.
• Map.Entry<K, V> lastEntry() — возвращает последний элемент в map.
58

59.

Методы интерфейса NavigableMap
• Map.Entry<K, V> pollFirstEntry() — извлекает и удаляет первый элемент из map.
• Map.Entry<K, V> pollLastEntry() — извлекает и удаляет последний элемент из map.
• K ceilingKey(K key) — возвращает ключ, который больше или равен указанному ключу
key. Если такого ключа нет, возвращается null.
• K floorKey(K key) — возвращает ключ, который меньше или равен указанному ключу key.
Если такого ключа нет, возвращается null.
• K lowerKey(K key) — возвращает ключ, который меньше указанного ключа key. Если
такого ключа нет, возвращается null.
• K higherKey(K key) — возвращает ключ, который больше указанного ключа key. Если
такого ключа нет, возвращается null.
59

60.

61.

Конструкторы коллекции TreeMap
• TreeMap() — инициализирует пустую коллекцию map.
• TreeMap(Map<K, ? extends V> map) — создает коллекцию на основе уже имеющейся
коллекции map.
• TreeMap(SortedMap<K, ? extends V> map) — аналогично предыдущему, создает
коллекцию, используя существующую отсортированную коллекцию.
• TreeMap(Comparator<? super K> comparator) — создает коллекцию с использованием
указанного объекта Comparator для сортировки элементов.
61

62.

Использование коллекции TreeMap
62

63.

А что если мы добавим еще одну книгу с ключом,
который уже есть в нашей коллекции
будет ли она добавлена ?
63

64.

Использование коллекции TreeMap
TreeMap не позволяет дублирование ключей поэтому элемент заменился
64

65.

Исключительная ситуация при добавлении ключа
который равен null.
Вопрос что будет ?
65

66.

Исключительная ситуация
TreeMap в отличии от HashMap не позволяет null в качестве ключей и будет ошибка во время работы программы
66

67.

Исключительная ситуация. Почему так ?
Почему возникает ошибка во время выполнения программы?
В TreeSet нельзя использовать null в качестве ключа, так как невозможно вызвать
метод compareTo на null.
Когда объекты, отличные от строк и чисел, используются в качестве ключей,
необходимо явно задавать порядок их сортировки.
Для этого можно воспользоваться двумя подходами:
• реализовать интерфейс Comparable;
• создать класс Comparator.
67

68.

Реализация интерфейса Comparable
Напишем свой класс BookID для использования в качестве ключа в нашей коллекции TreeMap
68

69.

Пример использования ключа BookID
69

70.

Реализация интерфейса Comparator
В данном случае наш класс BookID не должен реализовывать интерфейс Comparable, достаточно
Лишь создать класс реализующий Comparator<BookID>
Текущее состояние класса BookID:
70

71.

Пример с Comparator<BookID>
Данным способ предпочтительнее потому что не требуется модифицировать класс BookID
71

72.

Сравнение TreeMap и HashMap по скорости
работы
Название операции
TreeMap
HashMap
containsKey
O(log n)
O(1)
get
O(log n)
O(1)
put
O(log n)
O(1)
remove
O(log n)
O(1)
72

73.

Преимущества и недостатки
Преимущества
• Отсортированность: Хранит элементы в отсортированном порядке по ключу.
• Навигационные методы: Предоставляет методы для работы с диапазонами ключей и для
получения первых и последних ключей.
• Гибкость: Поддерживает как естественный порядок ключей, так и пользовательские
компараторы.
Недостатки
• Производительность: Операции put, get, remove имеют время выполнения O(log n), что
медленнее, чем у HashMap.
• Память: Использует больше памяти для хранения структуры красно-черного дерева.
• Не допускает null ключей: Ключи не могут быть null, что может быть ограничением в некоторых
случаях.
73

74.

Сравнение HashMap, HashSet и TreeMap
HashMap
HashSet
TreeMap
Когда использовать:
Когда требуется быстрая вставка, удаление и поиск элементов.
Когда порядок элементов не имеет значения.
Примеры:
Кэширование данных.
Словари ключ-значение
Когда использовать:
Когда требуется хранить уникальные элементы.
Когда порядок элементов не имеет значения.
Для быстрых операций добавления, удаления и проверки наличия элемента.
Примеры:
Хранение уникальных ID.
Удаление дубликатов из коллекции.
Когда использовать:
Когда требуется хранить элементы в отсортированном порядке.
Хранение цен акций: Отслеживание цен акций на протяжении времени, где ключом является дата, а
значением — цена. Это позволяет быстро находить цену акции на любую дату.
Реализация рейтингов: Хранение пользовательских рейтингов, где ключом является рейтинг, а
значением — список пользователей с этим рейтингом. Это позволяет быстро находить пользователей
74
с определенным рейтингом или выше/ниже определенного значения.

75.

Практика
75

76.

Практика
76

77.

Практика
77

78.

Заключение
Ключевые моменты
HashMap: Обеспечивает быструю вставку и поиск элементов, но не гарантирует порядок.
HashSet: Используется для хранения уникальных элементов и обеспечивает быструю проверку наличия
элемента.
TreeMap: Хранит элементы в отсортированном порядке и подходит для операций с диапазонами ключей.
Основные выводы по теме
• Выбор структуры данных зависит от конкретных требований к производительности и
функциональности.
• HashMap и HashSet обеспечивают O(1) время выполнения операций в среднем случае, но не
гарантируют порядок элементов.
• TreeMap обеспечивает логарифмическое время выполнения операций и хранит элементы в
отсортированном порядке, что полезно для работы с диапазонами ключей и упорядоченными
данными.
78

79.

Заключение
Временная сложность основных структур
79

80.

Задачи
80

81.

Определить сложность алгоритма
a) В больнице, в которую обычно ходит Гоша, работает доктор Игнатий Петрович. Он не очень
общительный и весь день проводит в кабинете, а заходят к нему только пациенты.
Нужно определить, сколько раз в день откроется дверь в кабинет Игнатия Петровича при условии, что
все пациенты, уходя, закрывают её за собой.
b) На вход подаётся целое число n. Нужно вычислить значение функции 42⋅

English Русский Rules