0: Доброго времени суток. Мы с вами рассмотрели уже некоторые вещи, например, сортировку, поиск. И несмотря на то, что, конечно, там можно ещё много чего искать, изучать. Это довольно огромные большие темы, которые развиваются до сих пор, потому
1: Потому что вопрос того, как эффективно искать, как подходить даже банально к решению задач, мало ли кто то что-то новое придумает, он все также прорабатывается. Но давайте мы чуть дальше пойдём и как раз-таки
2: Над тем, вот как эффективно искать. То есть, да, окей, многие сортировки позволяют вам за, от нлогн найти, ну, отсортировать массив. И дальше бинарным поиском вы можете найти ответ в нём, а с другой
3: Стороны не все данные можно отсортировать. То есть есть данные, например, которые банально не поместятся в оперативную память, да, есть сортировки, конечно, которые специализируются на том, что позволяют вам, например, сортировать данные, да.
4: Без их загрузки всей, всей массы вот этих данных, загрузки в оперативную память, а только по частям как-то вы с ними работаете и так далее, и тому подобное. Но это все как бы хорошо, отлично. Но проблема все равно стоит довольно остро. Вам надо
5: Отсортированные данные и потом вы дальше уже с ними можете работать, вы можете в них искать. И более того, линейный поиск, конечно. Ну он линейный оттен, и это не прямо-таки, что ужасно, да, в случае
6: Чего, но не очень эффективно. То есть можно ли как-то улучшить поиск и на самом деле можно, да, для этого нам надо познакомиться с понятием хэширование. То есть что это такое и 1 из вопросов, на которые можно ответить
7: С помощью хэширования это как раз-таки как эффективно искать
8: Хороший вариант эффективного поиска, это, скажем так, поиск без поиска. То есть, если мы могли бы как-то вот, ну, скажем так, магическим образом понять, где данные находятся, нам было бы хорошо. Согласитесь,
9: Да, то есть не заниматься вот этой вот сортировкой, да, не заниматься линейным поиском какими-то другими подобными вещами. А вот чтобы можно было взять любую, любой объект, любую строчку, любое число и сказать вот ему
10: Соответствует что-то то там своего рода поиск без поиска.
11: Ну как, да, потому что, в принципе, ну вот у нас есть массивчик, да, предположим, что это массив строк, в нём лежат, собственно, какие-то имена Иван, марья, Сергей тузик и так далее. Им как бы поставлены в соответствие.
12: Некоторые индексы 0 1, 2, 3 и так далее, да, благодаря тому, что мы уже знаем с вами, как это все расположено в памяти, и благодаря тому, что мы знаем, что massive это последовательно выделенная область памяти, мы знаем, что
13: Индексы сами по себе не хранятся, но по сути, да, если бы мы сказали, а, например, нашему товарищу. Слушай, сходи и возьми значение, которое лежит в индексе 2, да, то
14: Бы мог довольно эффективно и просто выбрать собственно имя сергея. Или вы могли бы сказать по другому. Смотри, мы двойке сопоставили некоторое имя. В данном случае Сергей.
15: Используя наш обычный стандартный массив, наш товарищ может как бы за от единицы получить имя, ну, например, имя того, кого надо повысить в должности. Отлично, но это все массивы, как бы.
16: Это, конечно, хорошо, но нам надо как-то запоминать эти индексы. Нам надо с ними работать. У массивов есть свои определённые нюансы, но это 1 из таких базовых элементарных частичек структур данных, из которых состоят все остальные структуры, данны.
17: Да, я это уже упоминал, и она нам сегодня понадобится.
18: Ну, все-таки, а если мы хотим, например, здесь использовать не числа, да? Или, возможно, мы не хотим, чтобы они шли по порядку или банально, даже мы бы хотели иметь возможность как-то эффективно проверять наличие того или иного элемента, потому что как мне
19: Проверить, что у меня вот в этой структуре данных, в этом массиве есть тузик. Ну, единственный вариант, это как бы пройти сначала 0 1, 2, 3, то есть перечислить все индексы, обратиться по соответствующему индексу.
20: К элементу массива и проверить, лежит ли там тузик или нет. Так это Иван марья, Сергей тузик, оо тузик имеется в нашей структуре данных. Ну, в данном случае в нашем обычном массиве, да, и в самом худшем случае нам надо пройти, естественно.
21: Весь массив. То есть здесь сложность у нас оттен, это, по сути, линейный поиск, я описал, и если бы вы там вспомнили, например, про то, что у листа есть у нас index of какие-нибудь такие вариации потом
22: У нас в питоне все-таки индекс просто, да, но, как правило, там индекс индексов и что-то в этом духе at, например, ещё бывает, то никакой магии нет, да, то есть есть
23: Мы работаем с листами. Даже если у вас существует какой-то метод индексов, который возвращает индекс того или иного элемента, то, к сожалению, чтобы найти какой-то элемент в массиве, нам надо пройтись по массиву и в лучшем в худшем слу.
24: Случае, естественно, мы делаем это за оттен
25: Ну как нам от этого же избавиться? То есть в любом случае все сведётся к ноликам и единичкам. В любом случае все равно надо, надо как бы в базовом варианте, в базовых, в виде базовых Кирпичиков, как бы использовать переменные и массивы. Что будем делать вы?
26: Могли бы сказать, конечно, но использовать словари, очевидно, ты че, питон, не знаешь? Великий язык? Ну, как бы, да, да. То есть мы могли бы тоже самое достичь с помощью нашего словаря дикшенери.
27: Взять как бы индексы 0 1 2 3 в словаре, они уже называются ключами кий, да, и тогда бы к какому-то ключу сопоставлялось, ну, ставилось бы в соответствие какое-то значение, Иван, и мы могли бы за, от
28: Единицы. Обратиться, собственно, к, скажем так, в кавычках любому индексу, к любому ключу и получить значение для него. Да, и более того, мы могли бы за от единицы проверить наличие этого элемента. Отлично.
29: Да, и более того, в отличие от работы с обычными массивами, мы могли бы ещё использовать строки, да, в качестве ключей, ну, либо вообще какие-то другие, любые наши объекты, ну, почти любые, да, эти объекты должны быть неизменяемыми. Пока.
30: Какой-то причине мы попозже узнаем, по какой удобно, но что если я скажу, что те же самые словари фактически используют массивы, да, потому что как бы вы
31: Не хотели, как бы вы не говорили, что вы там фронтендер, что аналитик, дизайнер и прочее компьютеры, ну, во всяком случае, на данный момент работают по довольно-таки строгим физическим, вполне себе специфичным, чётко определённым правилам.
32: Ещё какие-нибудь там эпитеты подберите и все в итоге сводится к битам, к ноликам и единичкам, к особенностям работы с памятью, да, то есть магически мы не можем вот взять как бы какой-то индекс, пример 1 нам
33: Надо этот пример 1, это название ключа, этот ключ, даже если быть точнее перевести в, грубо говоря, место в памяти.
34: Но как, да, по хорошему, что мы хотим, да, сделать там, это, эту картинку вы уже видели там в самом самом начале, в 1 из первых лекций, но она, по сути, демонстрирует то,
35: О чем я только что говорил, что мы значение храним в виде Ноликов единичек. И фактически мы хотим, по сути, следующую вещь. Мы хотим иметь какое-то значение. Да, наш ключ, и мы бы хотели его использовать. Как что?
36: Вот с интами мы можем использовать их как индексы, то есть это своего рода сдвиг от начала какого-то массива. А как использовать какой-то символ, как использовать, например, тёпл, как использовать какой-то
37: Кастомный объект в качестве ключей. По сути, мы хотим взять вот этот набор Ноликов и единичек, наш символ, а и превратить его в место в памяти, куда нам надо обратиться.
38: Чтобы получить значение, которое сопоставлено этому символу, а
39: И тут мы приходим, по сути, к идеям ассоциативных контейнеров, да, то есть это какая-то коллекция, пар, ключ значения, они ассоциируют значение с некоторым ключом, там существует огромное количество всевозможных, конечно, таких контейнеров, то ест
40: Есть контейнеры, где у нас, например, существует только конкретная пара. Ключ, значение, да, то есть 1 ключ ему сопоставляется. 1 значение. Есть какие-то вариации там, где ключу может сопоставляться несколько значений.
41: Которые добавлялись разные моменты и так далее, и тому подобное. Они могут быть реализованы через графы, как мы потом посмотрим, когда, думаю, будем затрагивать графы, да, они могут быть реализованы через собственно,
42: Обычные массивы некоторым специфичным образом. И как раз-таки вот этот специфичный образ через массивы это по сути, хэш таблицы, с которыми мы сегодня познакомимся.
43: Но для этого нам надо познакомиться, естественно, с понятиями хэша и хэш функции.
44: Что такое хэш функция вообще, что такое функция? Функция? Это, по сути, некоторое правило, некоторый закон, который говорит вам, что вы берете некоторое значение, допустим, ф от икс и каким-то образом его превращаете в новое значение. То есть
45: Например, равняется это эф от икс, равняется единице. То есть в таком случае ф от 5 равняется 1, ф, от 6 равняется 1 как бы логично, да, но я могу и по другому же определить свою функцию. Да, я могу
46: Что-то более сложное сделать. То есть ф от икс равняется икс квадрат + 1. И в таком случае ф от 5 у меня равняется 25 + 1, а ф от 6 уже равняется другому значению.
47: Как бы отлично, да, 26 и 37 супер. И по сути вот это то, что называется у нас функцией. Мы можем функции на самом деле определить не только в таком вот каком-то математическом смысле, но мы можем определить закон.
48: Правила преобразования и в виде слов, конечно же, хотя зачастую это не так удобно. То есть я могу сказать, что там возьмём, давайте первые, там 8 битов нашего, нашего куска, памяти и посчита
49: Сколько там Ноликов и единичек. Да, тут у нас, значит, первые 8 бит, у нас только 1 beat, да, 1 единичка активная. Возьмём 2 и прибавим к этой единичке, там тоже 1, потом 3, потом 3 и так далее складываем, получаем.
50: Как бы я, по сути, определил некое правило преобразования битов?
51: В какой-то другой набор бит. Ну потому что двойка это тоже у нас это как бы число, да, в десятичной системе счисления, которое мы можем преобразовать в двоичную систему счисления. То есть мы можем как-то сохранить в оперативной памяти в виде Ноликов и единичек, ну,
52: В нашем случае это десятичная система счисления. Это по сути, че у нас там 1 0 в двоичной системе счисления. Окей, что нам это даёт? Ну, на самом деле нам это даёт такое довольно.
53: Мощное понятие как собственно хэш функция, то есть хэш функция, это функция, некоторый закон, который преобразует битовую строку, то есть последовательность бит произвольной длины 5, 10 20 элементов в beat.
54: Строку указанной длины, да, мы со временем поймём, почему указанной длины. Нам это, в принципе, пока не сильно принципиально. Все это то, что называется хэш функциями довольно простое.
55: Фундаментальное и зачастую довольно абстрактное понятие. Но если вы помните, как это все устроено в компьютере, то для вас уже становится гораздо проще, потому что действительно, ну, функция, которая преобразует 1 набор Ноликов, единичек в другой набор Ноликов,
56: Где это можно использовать? Ну, например, если вот этот набор, как бы 8 бит, это у нас двойка, да, целочисленное значение 2, то мы можем преобразовать его в
57: Строку 2, но строка же как-то тоже у нас хранится в виде наборов Ноликов и единичек в оперативной памяти. То есть эта двойка, она как-то будет расположена там, ну, условно, как-то так, да, и питон, и другие.
58: И программы, и мы, в том числе, как разработчики, будем знать, что вот эта строка, которая, собственно, хранит в себе двойку, да, мы её каким-то образом получили из вот этого набора Ноликов единичек по какому-то закону. Да, естественно, здесь у нас нолики един
59: Не такие, как здесь. Ну, потому что это строка. А мы знаем с вами, что строка у нас состоит из символов, и каждый символ у нас каким-то образом закодирован, да, в тех или иных кодировках по разному. Вот. Поэтому эти значения, они у нас как бы могут совпадать и могут различаться.
60: В разных ситуациях, но в общем случае, как бы в принципе это функция, которая преобразовала 1 набор Ноликов, единичек в другой набор Ноликов, единичек, супер
61: Ну, где ещё это может быть использовано? Архивация, да, архивы. То есть все, я думаю, так или иначе использовали архивы. Во всяком случае, когда, например, смотрели фильмы, то есть фильмы, так или иначе, при передаче
62: Это даже не только фильмы, видео, да, при передаче по интернету вы не можете просто отправлять какие-то отдельные пиксели их значения, да, вам надо сжимать информацию, потому что, ну, скажем так, передавать
63: Огромные объёмы информации это трудозатратно, мягко говоря, поэтому если бы мы могли уменьшить количество информации, которую хотим передать, да, возможно, иногда с потерей качества да, стопудово все видели на YouTube, на том же самом выборы.
64: Качество, а 1080 пи 144 пи вообще без видео это тоже по сути варианты сжатия, то есть архивации данных и хэш функция там используется с другой стороны да, например, безопасность без
65: Безопасность то есть если мы говорим о безопасности о хранении хэшей ой хэшей паролей да, пароли хранить в открытом виде в базе данных наверное не очень разумно то есть path ворд очень плохой вариант пароль.
66: Но довольно распространённый, как показывает статистика, да, и так вот, мы же, наверное, не очень хотели бы хранить так пароль от какой-нибудь нашей почты или даже, допустим,
67: Не то чтобы мы храним пароль. Да, понятное дело, что когда вы пароль указываете, например, для того же профиля своей почты, он хранится где-то на серверах гугла яндекса, других сервисов. И если он открыться в
68: Хранится в открытом виде, то это проблематично, потому что в случае, если кто-то украдёт базу данных базу данных, то ваш пароль легко будет считать, поэтому его надо как-то зашифровать или
69: Скрыть, да, таким образом, чтобы его нельзя было восстановить в идеале, да, но при этом, когда вы вводите пароль, надо было иметь возможность проверить, что вы ввели корректный пароль, да, потому что изменить данные так, чтобы их невозможно.
70: Было восстановить это не то чтобы сложное дело, но чтобы их можно было потом как-то ещё использовать. Это отдельная проблема, соответственно, в безопасности для хранения паролей, да, для шифрования.
71: Каких-то вещей, банально даже для чек суммы, чек сумм вы, возможно, слышали про различные хэши мд 5, да, ш, 256, например, и так далее.
72: Тому подобное. То есть это какие-то вещи, контрольные суммы, так называемые, которые позволяли бы вам проверить, что вы скачали корректный файл, да, что его не подменили, что он не был повреждён. И вот там тоже у нас
73: Используется хэш функции. Конечно, в зависимости от применения к хэш функциям выставляются разные требования, да, и мы посмотрим, какие у нас хэш.