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