0: 1 из таких известных классических примеров хэш функции это полиномиальный хэш. Собственно, полином многочлен. В этом основная его идея. Напоминаю, что многочлен это у нас, скажем, некое выражение такого вот вида а икс

1: Квадрат плюс б икс плюс ц, да, многочлен 2 степени у нас есть какие-то коэффициенты при иксе в какой-то степени, да, здесь у нас, по сути, икс в 0 степени здесь x 1. То есть степени у нас идут по возрастанию, в принципе, естественно, если бы у нас равня

2: Нулю икс в 1 может и отсутствовать. Вот мы, естественно, можем создать полином там многочлен и 3, и 4, 5 и прочих степенней. Естественно, мы не будем сейчас прямо решать как-то эти всевозможные

3: Равенство, неравенство, да, или строить графики. Я просто напоминаю, как они выглядят. Так вот в чем его идея. Идея заключается в том, что у нас есть некоторая строка. Возьмём ту же самую строку абц, и мы немножечко разовьём идеи того, что хотим в

4: Учитывать не только значение отдельной буквы, но ещё её и позицию и как-то попытаться снизить количество коллизий, при этом предоставить более равномерное, скажем так, распределение возможных хэшей.

5: Для входящих строк и в общем то, сделать это довольно эффективно. Дак как нам это сделать? Ну, собственно, мы хэш получаем следующим образом. У каждой буквы есть, напоминаю, своё значение и своя позиция, и мы берём значение буквы

6: Последовательно берём буквы, причём, да, соответственно, строка нулевая. То есть берём 0 символ нашей строки, входящей умножаем на п. П. Это некий коэффициент в 0 степени, да, потом прибавляем и

7: Здесь берём опять-таки, значение символа в следующем индексе. В данном случае в 1 индексе умножаем на п в 1 степени. Далее берём значение нашего. Какое там 2 индекс.

8: Да, это ц, и умножаем на п во 2. Ну, то есть, думаю, вполне себе ясна идея. Мы берём индекс, да, берём букву по этому индексу и умножаем значение этой буквы, да, как бы, хэш этой буквы на коэффициент п. В соответст.

9: Степени. Окей, что за коэффициент п. П выбирается по разному. То есть это просто какая-то константа и самый такой распространённый вариант взять простое число можно взять

10: Натуральное число, в принципе, это влияет, и это призвано как бы снизить количество коллизий, которые количество, которое даёт нам данная хэш функция. Вот, поэтому в зависимости от того, какое

11: Именно у вас тут алфавит, то есть какие символы могут встречаться в наших строках. То есть, если мы возьмём вот эту строку абц, предположим, что больше никакие символы не могут встречаться в этих строчках. Да, и тогда у нас строки могут состоять только из 3 букв а, б и ц.

12: Да, я могу создавать строки, конечно же. А, а, а, а, а, там из 4, из 5 символов и так далее. Но, в принципе, возможные символы, которые могут мне встретиться, это только абц, да, тогда у нас получается, алфавит состоит из 3 символов, да, если я возьму

13: Все символы английского алфавита, их станет очевидно больше, да, там 31 буква, если я возьму ещё нижний регистр, да, малые буквы, а бц и так далее, их станет в 2 раза больше, если я добавлю

14: Туда ещё какие-то спецсимволы, запятые пробелы, переносы строк и так далее, и тому подобное. То есть я буду расширять алфавит символы, которые могут встретиться в моих строках и в принципе берут в качестве п. Не просто простое число, а некое простое число, которое

15: Больше размера нашего алфавита.

16: И что нам даёт вообще полиномиальный хэш? На самом деле, если обратить внимание на то, как он строится, да, я уже даже подчёркивал это, что мы берём 0 символ, умножаем на п, в 0, берём 1 на п, в 1, 2, 2 символ на п.

17: Во 2 и так далее. Идём последовательно по строке. Мы, по сути, проходимся по префиксам нашей строки и вычисляем для каждого префикса соответствующий, скажем так, под хэш, да, при вычислении нашего

18: Реального хэша. То есть если я уберу вот из вычисления хэша последний член, что получится, то да, в принципе получится вот такое вот выражение а чему соответствует данное выражение, данное выражение соответствует

19: Собственно, хэшу подстроки аб. Да, ну или просто строки, а. Б, если она у нас пошла на вход в хэш функцию окей. Вот. И естественно, как мне вычислить, например, предположим, что я уже

20: Каким-то магическим образом вычислил хэш для строки абц. Да, я его знаю, и я дальше знаю, что у меня на вход поступает абцд строка. Ну я уже знаю хэш абц, да, соответственно, вычислить хэш.

21: Новой строки абцд мне, ну, как минимум, в теории становится легко. Я могу взять хэш старый, там, допустим, у нас получилось 7, я возьму 7 и прибавлю, допустим, хэш д.

22: Д, это у нас какое там, 0, 1, 2, 3. Логично. То есть мы берём тут стр, 3 умноженное на п, в 3 степени, вот как-то так. По идее, я как бы.

23: Могу так вычислять довольно эффективно хэш у нескольких строк. И более того, я могу так сравнивать строки на схожесть, да, при некоторых дополнительных ееще требованиях, но в целом там можно попытаться

24: А использовать эту идею и я могу таким образом.

25: Пытаться понять, да, как-то эффективно. А находится ли у меня какая-то 1 подстрока в другой подстроке. То есть, например, подстрока икс возьмём, да? А, бц и игрек бц. Входит ли игрек в

26: Абц как подстрока.

27: Поиск различных полиндромов, проверка на собственно, то является ли строка полиндромом и так далее, и тому подобное. На самом деле, алгоритмов, которые так или иначе работают со строками, их огромное множество. И они не то чтобы простые, то есть когда мы работаем со строками,

28: Мы, естественно, не в реальности навряд ли будем работать со строчками, то абц мы зачастую хотим поработать с каким-то огромным текстом, да, особенно сейчас, в, скажем так, эпоху развития ллм.

29: Которые стараются все как бы сильнее, сильнее увеличить своё контекстное окно, то есть количество отдельных символов, которые входят, подаются на вход, лмки, на обработку, да, опять-таки.

30: Вопросы обучения, то есть как нам преобразовывать, как нам работать с огромными корпусами текста, то есть такими, скажем, наборами текста, которые каким-то образом предобработаны, как-то категоризированы, как-то потом, чтобы использовать

31: При обучении наших моделей, ну и так далее и тому подобное. То есть это очень большая область, и там очень много всего можно найти. То есть, естественно,