0: Хорошо, мы посмотрели на варианты того, как можно было бы в теории попридумывать свои хэш функции. Мы посмотрели классический вариант хэш функции собственно полиномиальный хэш. Хорошо, но давайте вспомним, что в какой-то момент я ещё как бы сказал, да.
1: У нас есть хэш таблицы, и они, очевидно, как-то используют наши хэши и хэширование. Более того, словари, да, 1 из таких распространённых хороших вариантов реализации словаря такого ассоциативного контейнера, который сопоставляет некоторые
2: Ключу некоторое значение. Ну, например, Иван, предположим, его оценки 5, 2, 5, да, и так далее. А ключ, значение, все вполне нормально, как бы, да, окей.
3: Это строка, значение, это целый лист, массив других каких-то значений. Ну ничего страшного, все вполне логично, вроде как звучит. Так вот как же все-таки она работает, как нам её построить, используя идею того, что все
4: В итоге сводится к тому, что компьютер как-то работает на элементарных операциях, да, что где-то есть ячейки памяти, что у нас везде все представлено в виде Ноликов единичек, как нам это сделать. Ну естественно, куда же нам без
5: Сила. Мы могли бы, конечно, сделать, в принципе, хэш таблицу, то и с использованием отдельных переменных, да, отдельных, как бы, грубо говоря, ячеек памяти. Но это было бы очень не очень гибко, хоро.
6: Хорошо, используем массив. Мы понимаем, что доступ к элементам массива, ко 2 индексу, к 3, к 4, к нулевому. То есть рандомный доступ, произвольный доступ, он эффективный за от единицы. У нас там константное количество действий супер, но
7: Мы также понимаем, что в хэш таблице, в словаре, в дикшнери мы также хотим вообще получать данные по какому-то ключу. Ну, например, по строчке. В общем случае мы даже хотели бы получать по каким-то кастомным объектам, то есть, например, по объекту типа перс,
8: Плеер, плеер, может быть какой-нибудь объект, бокс, коробочка в вашей игре и так далее и тому подобное. Но пока мы сконцентрируемся на строках, потому что идея в случае кастомных объектов такая же. Нам надо использовать
9: Хорошо, мы берём наш ключ, по которому мы хотим получить значение. Ну и положить, да, я думаю, с учётом того, что у нас пока нет никаких значений в словаре, мы, собственно, будем для начала закидывать словарь.
10: Добавляет словарь значение, что нам для этого нужно, ну, во первых, да, вспомнить словарь, это какая-то структура данных, структура данных, это что это набор правил того, как данные хранятся в памяти как данные.
11: Используются, да, то есть добавляются, меняются, как происходит к ним обращение, удаление, проверка на то, что, собственно, есть те или иные какие-то элементы и все в этом духе. То есть это вот набор таких правил все сводится опять-таки.
12: К ячейкам памяти. Давайте возьмём идею того, что хэш функция, она берет какой-то произвольный набор битов и переводит его в набор битов да установленной длины.
13: И разовьём эту идею, скажем более конкретно. Давай-ка мы возьмём какой-то объект, применим к нему хэш функцию, причём такую хэш функцию, чтобы она нам давала ИНН.
14: Индекс в массиве оо.
15: Мы понимаем, что в принципе любой объект, представленный в виде набора Ноликов, единичек и уж тем более строки, да почему с ними в этом плане довольно легко к ним можно применить произвольные хэш функции, да, мы с вами посмотрели, как можно придумать в ба.
16: Очень базовом, элементарном варианте свою как можно использовать полиномальным хэш можно загуглить что-то более эффективное, более качественное, ну в плане количества коллизий, например, более сложное в работе. Ну мало ли надо и как-то
17: Применить. Хорошо. Давайте мы скажем тогда хэш, соответственно, от нашего ключа. Иван Иван равняется 15. Да, любой набор битов мы можем рассмотреть как интовские значение целочисленное знач.
18: И в том числе в питоне. Почему нет? Вот у нас хэш функция дала 15. Да, предположим, что мы используем полиномиальный хэш. Окей.
19: Проблема, да, сразу g1 проблема. У нас нет такого индекса, но на самом деле эта проблема довольно-таки легко решается как остаток отделения, то есть, по сути,
20: Наша то идея в чем заключается? Мы хотим как-то, да, расположить в массиве, собственно ивана. Да, хорошо, функция будет давать нам индекс внутри этого массива функция может дать, конечно, какой-нибудь
21: Путь несуществующий индекс. Ну, например, у нас массив состоит из 5 элементов. Тут 15. Мы могли бы расширить наш массив, естественно, на какое-то дополнительное количество элементов, да, чтобы тут у нас было 15 куда-то, да, тддд, но
22: Согласитесь, это как-то не очень. Ну потому что у нас хэш, так-то может быть довольно большим, там, допустим, 15000 и создавать лист на 15000 элементов. А мы помним, что лист это, по сути, массив такой немножечко модифицированный.
23: Динамический массив можно сказать так, который как бы является последовательно выделенной областью в памяти. И если у нас будет 15000 элементов, из которых там 14999 элементов первых,
24: Просто пустые. Это будет плохо, да, в плане эффективности. Поэтому нам бы как-то вот этот индекс преобразовать к уже имеющемуся индексу, да, что мы будем делать с этим остаток?
25: Отделения, остаток отделения на количество имеющихся собственно элементов в каком-то массиве, во внутреннем массиве. Давайте так, в данном случае 5, да, 15. Остаток отделения от 5 равняется.
26: О, отлично. Благодаря остатку отделения, мы что делаем? Мы, по сути, как бы вне зависимости от того, какой бы индекс мы в этом массиве не взяли, например, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, миллионный.
27: Мы всегда будем работать после взятия остатка с корректными индексами. Да, мы просто будем ходить по кругу, по этому массиву. Хорошо получили 0 индекс. Вот сюда мы закинем.
28: Нашу пару, Иван, там, 5, 2, 5. Ну да. Окей, ладно, Иван 2. Точнее, че ж мы так расстраиваем его? 5, 2, 5. Хорошо. Это, в принципе, базовые.
29: Идея хэш таблиц. Все как бы в этом плане относительно просто. А сложности возникают, когда мы хотим. Ну, во первых, да, когда мы хотим оптимизировать потребление памяти, да, и не просто так.
30: И когда мы будем добавлять дальше другие какие-то элементы и пытаться удалить, например, элементы, допустим мы что сделаем?
31: Давайте-ка я это вот перепишу, да, 1 этап, соответственно, получить хэш от ключа. 2 этап найти индекс, индекс в нашем внутреннем массиве внутри этого словаря кастомного.
32: Хэш таблицы, да, этот индекс мы получаем как, что, как хэш, остаток отделения на, скажем так, array, length, да, длина этого листа, количество элементов в этом листе. Вот. Ну и дальше уже надо положить туда значение.
33: Ладно, идём далее. Предположим, я теперь хочу обратиться, да, как бы к этому значению. У меня опять-таки есть ключ. Да, я говорю, слушай, словарь, дай-ка мне значение по ключу. Иван, что мне для
34: Для этого надо, как мне найти значение в памяти я создаю, точнее, опять-таки считаю хэш хэш ивана Иван, да, и получаю опять-таки 15 я.
35: Беру далее, что остаток отделения на количество элементов на 5 получаю 0. И, по сути, это ответ на то, где именно лежит значение, соответствующее ключу Иван.
36: В нулевом индексе внутреннего нашего массива. Окей, давайте дальше добавим, что, ну, добавим какое-нибудь новое значение, например, Пётр Пётр.
37: У него вообще не будет оценок. Ну почему бы нет? Только перевёлся в группу, как мы его добавляем в нашу хэш таблицу. Ну, наша хэш таблица, это, собственно, под капотом, скажем так, да, это массив.
38: В котором у нас есть индексы. Естественно, мы опять считаем хэш от петра петра. Предположим, что этот хэш равен 2 окей. 2, остаток отделения на 5. Понятное дело, 2.
39: Это означает, что в 2 индекс нам надо положить значение, соответствующее ключу. Пётр. Отлично.
40: Пётр, и тут пустое значение. Я причём кладу сразу же пару ключ значения. Это нам пригодится не просто так. Это пока все вроде легко и просто можно, конечно, спросить, а как это так? Вроде я
41: Словарь, да, использую, но внутри там у нас как бы словарь реализован через массивы. Ну да, вполне нормально. У нас же есть класс, у нас там эти классы, по сути, позволяют нам создавать кастомные объекты, а как именно реализованы классы, это отдельный вопрос.
42: Да, все зависит от разработчика. И вот вы могли бы создать свой класс, хэш таблица кастом дикшнари, как угодно, называйте его и дальше уже там внутренние, какие-то приватные, соответственно, массивы, использовать функции и все в этом духе. Ну, возвращаемся
43: К нашим Ивану и Петру, предположим, пришёл ещё 1 новенький Максим, а у него есть оценка 1. Ну, предположим, это 3 хорошо.
44: Хэш хэш от максима равняется нулю.
45: О, как бы.
46: Проблема, да, потому что 0. Остаток отделения на 5 даёт нам 0. То есть напоминаю, что у нас, у ивана хэш ивана хэш тут равнялся 15. Хэш максима равнялся нулю. То есть это
47: Коллизия, по сути, но это коллизия не на уровне хэшей, а мы понимаем, что вообще разные ключи то могли дать одинаковый хэш. Это коллизия на как бы более глубоком уровне. Это коллизия на уровне реализации, собственно,
48: Хэш таблицы, когда мы хотим все-таки оптимально тратить память, да, мы не можем бесконечно расширять наш массив, но он должен какие-то разумные границы иметь.
49: В данном случае, собственно, это 5 элементов. И тут произошла коллизия, но не из за хэш функции. С другой стороны, если бы мы взяли какую-нибудь хэш функцию, которая дала бы нам не 0, а единичку, то здесь коллизии бы тоже не произошло, да, поэтому как бы хэш функция виновата, но не
50: Всем виноваты, да, из за того, что мы ограничены памятью, она у нас не бесконечна, у нас поверх хэш функций появляются дополнительные какие-то факторы, которые могут вызвать коллизии. Хорошо, но
51: Что мы делаем? Тут то у нас уже значение готово. Мы не можем просто взять и перезаписать ивана и сюда положить. Типа максима, да, Максим там, соответственно, тройка его. Почему? Ну, потому
52: Что таким образом я перезапишу
53: Вот эту пару, Иван 5 2, 5, максимом 3. Но ключи то разные. То есть получается так, что я добавляю какой-то новый ключ, который у меня ни разу не встречался в словаре. В данном случае. Максим, я каким-то образом удаляю Иван.
54: Это, мягко говоря, да, не очень удобно с точки зрения пользователя было бы, поэтому мы так не будем делать. Мы поступим поумнее, нам надо сохранить оба значения, но оба значения у нас хранятся в нулевом индексе. Что
55: Мы тогда будем делать тут на самом деле есть несколько возможных решений данной проблемы.
56: Например, мы можем использовать другую хэш функцию. То есть когда мы понимаем, что у нас здесь уже что-то лежит, мы можем применить 2, да, как бы дополнительную хэш функцию и таким образом попробовать найти ещё 1.
57: Место, куда нам надо положить это значение, но там тоже может быть занято. А собственно чейнинг метод, как бы цепочка применяется, скажем так, цепочка чего? Цепочка, пар, ключ значения, да, и мы
58: Сейчас этот метод рассмотрим. Есть вариант, когда мы ищем 1 попавшийся пустой слот. То есть мы в нолик не можем попасть. Ну давайте дальше пойдём в 1 слот. Оо 1 слот готовый сюда. Давайте закинем максима и так далее у каждого из этих методов
59: Могут быть свои проблемы. Ну как могут быть они, естественно, есть свои проблемы, да, идеального метода не существует. В каких-то случаях 1 хорошо реализуется в каких-то случаях, другой хорошо показывает себя или проще реализуется. В общем, нюанс.
60: Много, но давайте мы рассмотрим такой хороший вариант. Это, собственно, ченнинг.
61: Его идея, как я уже рассказал, заключается в том, что мы, по сути, представляем каждый индекс не как отдельное маленькое значение, а как связанный список, как цепочку значений.
62: И в этом случае, когда мы попадаем сейчас с максимом в индекс 0, и здесь уже лежит Иван, мы просто добавляем в связный список новый элемент, да, в данном случае Максим и 3 massive 3. Ну вот эта вот пара наш.
63: М. 3 то есть получается, что словарь, да, который реализуется через хэш таблицу, в данном случае будет представлять из себя массив, каждый элемент которого является линки.
64: Листом, связным списком. И, соответственно, это нам даёт следующую штуку. Например, когда пользователь скажет, слушай.
65: Дай мне, пожалуйста, значение ивана аш, Иван, Иван равняется 15. Мы получили хэш. Мы от этого хэша находим индекс и как называть?
66: Вот такие вот связные списки, ну, вообще эти связные списки, вот такие вот связанные списки. Давайте я их так вот нарисую вот так вот, вот красивенько, вот так вот, вот они называются слотами, либо по другому.
67: Бакетами, то есть вёдрами, да, представьте себе, мы, по сути, закинули в это ведро, в этот слот, как там ещё называют, в принципе, в этот мешочек сначала Иванна пару ключ, значение Иван 5, 2, 5, потом
68: Туда же закинули максима 3. В этот слот мы закинули Пётр с пустым набором оценок, а слоты 3 4. Ну, в общем то они никак не использовались. Окей, хорошо, возвращаемся обратно мы находим
69: Лот номер, соответственно, слота номер бакета 15, мот 5 равняется у нас 0. О, отлично. Значит, значение, которое ищет пользователь по ключу. Иван находится в нулевом бакете, но мы же
70: Тем, что тут упс, у нас тут очевидно, 2 значения, что тогда нужно делать? Ну, это линкит лист, связный список. Нам ничего, в общем то, особо не остаётся, как пройтись.
71: По нему, ну то есть мы могли бы, например, ещё использовать там, например, массив дополнительно как-то его отсортировано, поддерживать отсортированным, да, потом бинарным поиском искать там элементы. Может быть, это улучшило бы производительность, может быть нет, ну, отдельный разговор.
72: Мы в данном случае просто пройдёмся по линкит листу. Это в принципе, довольно рабочая стратегия с некоторыми нюансами. Вот мы берём 1 элемент линкит листа, Иван пользователь ищет, собственно,
73: Значение, которое соответствует ключу. Иван, отлично. Мы его нашли. Возвращаем 5, 2, 5. Предположим, другой вариант, когда пользователь спрашивает, слушай, а дай, пожалуйста, значение, которое соответствует ключу. Максим, мы берём хэш от максима, получаем там
74: Нолик, находим номер слота бакета, где лежит это значение, это 0 Бакет.
75: Проходимся по этому линкед листу. Так, Иван, сравниваем ключи Иван и Максим.
76: Мы могли, мы можем сравнить их с помощью хэшей. Конечно, да, мы можем, и мы знаем, что хэш ивана это 15 хэш максима это 0, поэтому тут все будет легко. Да, коллизия не случилась на уровне хэш функции. Коллизия случилась на уровне выбора бакета.
77: Поэтому мы сразу же говорим, что это нам не подходит, и переходим к следующему элементу. А следующий элемент это Максим. И на самом деле мы могли бы в принципе хранить помимо вот этого пары, ключ значения ещё и хэш, но, как правило, все-таки
78: Hash у нас у объекта не меняется. Да, это такой нюанс, который, думаю, мы попозже обсудим, соответственно, возвращаем максима с его тройкой единственной.
79: Окей, в принципе, по этой же логике у нас происходит проверка на наличие того или иного элемента. То есть, если мы, к примеру, берём и спрашиваем, слушай, а у нас есть ли там оценки для Кати? Ну мы берём хэш.
80: Для Кати, да, хэш от ключа получаем, допустим, 3. Находим номер бакета 3 делим, берём остаток отделения на 5, получаем 3.
81: Тут Бакет пустой. Ну, при всем желании Кати у нас тут нет, да?
82: Окей.
83: Собственно, как, да, это с точки зрения сложности алгоритмов работает. Не будем сейчас прям погружаться в это очень глубоко, потому что, опять-таки, все очень сильно зависит от хэш функции. Правильно? Более того, все очень сильно зависит от данных, потому что, в принципе,
84: Если у нас данные зачастую очень похожие или одинаковые, нам надо как бы постараться найти хэш функцию, которая будет давать для них максимально разные хэши, может быть как-то её немножко кастомизировать под наши дан.
85: Тогда мы снизим количество коллизий, тогда мы повысим эффективность наших, собственно, наших эш, таблиц, наших словарей. С другой стороны, если мы ничего о данных не знаем, нам приходится какую-то использовать общую, да, стандартизированную хэш функцию.
86: Как это повлияет на количество операций, довольно проблематично сказать, поэтому анализ сложности для хэш таблиц для словарей, он не особо тривиален и тем не
87: Менее, в принципе, хэш функции мы можем рассматривать как от единицы константное значение, да, опять-таки, потому что, ну, к этому стремятся. И, в принципе, длина ключа по сравнению с остальными, ну и вычисле,
88: Хэша для этого ключа по сравнению со всеми остальными операциями, скорее всего, будет ничтожно мало. Опять-таки, скорее всего, нюансов в реальности довольно много. Может быть. Поэтому в среднем у нас тут от единицы обращение, да, ну и взять
89: Остатка отделения, обращение к индексу нашего массива тоже, в принципе, от единицы, да? Ну и дальше нахождение вот здесь вот элементов не то чтобы от единицы, да, понятное дело, потому что мы проходимся по этому
90: Листу, но если у нас бакеты будут все не заполнены.
91: Тогда это от единицы, да, то есть обращение к конкретному элементу. Почему? Ну потому что все линкит листы будут состоять из 1 элемента. Это идеальный вариант. А вот на это уже влияет степень заполненности нашей хэш таблицы коэффицие.
92: Заполните наши хэш таблицы. То есть представьте себе, если у меня очень плохая хэш функция, и она абсолютно всегда мне даёт хэш нуля, да.
93: Пётр, давайте мы это вот уберём, соответственно, хэш нуля, и я сюда закидываю ещё и петра. Пётр.
94: Наверное, не очень, да, то есть у меня все элементы хранятся в 1 Линке листе. Понятное дело, никакой, ни о какой сложности от единицы тут не идёт речи. Да, проверка, добавление, удаление, все будет очень печальным. Ну а если быть точнее, он, потому что мы
95: Работаем не со словарём каким-то эффективным, мы не работаем с хэш таблицей, мы работаем с линкит листом стандартным. Все тут.
96: Что ещё придумать? Да ничего особого. Да, такой самый крайний печальный случай. И в целом такое может быть, особенно, если вы не задумываетесь о том, какие у вас входящие данные, какую хэш функцию вы используете, как это все взаимосвязано и что это вообще существуе.
97: Ну это прям самый худший вариант. Коэффициент заполненности, заполненности у нас, в общем то, тут очень плохой другой вариант, да, если мы посмотрим на
98: Пакеты, которые содержат по 1 элементу. Ну тогда все будет хорошо, да, все будет замечательно.
99: Окей, что мы ещё можем тут сказать?
100: А, ну естественно, опять-таки это вариант, когда мы используем линкит лист. А ведь у нас же ещё, я вам говорил, что мы находим ближайший. Давайте я чуть чуть отключу, да, ближайший пустой слот, и, более того, там сама
101: Идея поиска ближайшего пустого, она на самом деле тоже не самая простая в том плане, что там есть разные стратегии того, как мы выбираем ближайший, мы можем выбирать соседний, мы можем выбирать каким-то образом основываясь на хэше или на дополнительном хэше, или же как-то
102: Рандомно выбираем дополнительный слот. Ну, в общем, стратегий там много, и это тоже как-то может повлиять на производительность вашего словаря. То есть, когда мы говорим, что словари хэш таблицы хэш сеты, да, у нас работают за от единицы, мы как
103: Как бы понимаем, что они действительно эффективные и математически тут относительно все, ну, в базовой идее, в базовом варианте все просто лаконично, красиво, даже, я бы сказал, ну вот это вот.
104: Звёздочка существует, да, что есть определённые факторы, которые где-то на периферии сознания должны у вас быть, да, то есть вы не можете постоянно использовать словари просто потому что, ну они же эффективные, нет.
105: Они могут, ну как бы в самом таком плохом варианте дать вам ужасную какую-то производительность.