Здравствуйте! На прошлом занятии мы узнали, как правильно писать хеш-функцию для своих типов. Сейчас мы обсудим некоторые практические рекомендации для их написания. Давайте вспомним, что мы работали со структурой для автомобильных номеров, и какую хеш-функцию мы для неё написали. Посмотрим наш код. Вот наша структура для автомобильного номера. Такую хеш-функцию мы написали, и благодаря этому мы могли в unordered_set поместить наши автомобильные номера. Давайте напишем ещё какую-нибудь структуру собственную. Поместим в неё поля и попробуем написать хешер для неё. Что там будет? Ну давайте для начала поместим туда число типа double, и у нас сразу встает вопрос: как же мы будем писать для хеш-функцию для double? Ведь значение хеш-функции - это целые числа, а double - это дробное число и не очень понятно, как его однозначно перевести. Но ещё больше было бы непонятно, если бы у нас было вообще не число, а какая-нибудь строка. Как нам переводить строку хеш-функцией в число? Неужели снова писать такую же сложную хеш-функцию, как для автомобильных номеров? И это было бы удивительно, потому что тогда мы бы не смогли положить в unordered_set по умолчанию ни double, ни string. Но давайте убедимся, что мы на самом деле можем это делать спокойно, без написания собственных хеш-функций. Вот мы создаем unordered_set из переменных типа double и код компилируется прекрасно. И если мы заменим на string, он тоже прекрасно компилируется. От нас не требуют написать свою собственную хеш-функцию для этих типов. Это значит, что для этих типов стандартные хеш-функции уже написаны, и мы можем их использовать из стандартной библиотеки. Они так и называются: это структуры hash, параметризованные каким-нибудь типом. Давайте объявим эти хешеры, но только не в нашей структуре, конечно, нам надо написать хешер для нашей структуры. Давайте скопируем отсюда заголовок и поработаем над ним. Значит это будет не PlateHasher, а MyHasher. Мы хотим использовать стандартные хешеры из библиотеки. Пусть это у нас будет dhash и заведем хешер для строк, и тогда при вычислении нашей собственной хеш-функций мы можем использовать их для того, чтобы посчитать компоненты от полей. Это делается довольно просто, вот таким вот образом. Так мы могли бы посчитать значение хеш-функции, но теперь давайте усложним нашу задачу. Что было бы, если бы у нас в полях лежал наш тот самый собственный автомобильный номер, который мы только что записали, как нам использовать хешер для него? Ну это небольшая проблема. Мы же уже тоже написали для него хешер, объявим его использование прямо здесь и, точно так же, для его компонента мы посчитаем хеш для автомобильного номера. Так, здорово. Итак, мы посчитали хеши для всех компонентов нашей структуры, но теперь надо их как-то объединить в одно общее значение. Можно использовать такой же подход, как мы делали в автомобильных номерах, либо можно воспользоваться универсальным советом: это взять какой-нибудь многочлен от нескольких переменных, вернее с несколькими коэффициентами и посчитать его значение. Здесь мы должны выбрать значение для переменной X, а A, B и C мы уже имеем как компоненты хеш-функции от наших полей. В литературе принято брать в качестве значения для X какое-нибудь простое число, ну и мы возьмем какое-то простое число, пусть это будет 37. И тогда мы можем вернуть это самое значение. Посчитаем, R1 * X^2 + + R2 * X + R3 . Вот такую вот простую хеш-функцию мы смогли написать, и теперь конечно же её надо где-то использовать, а именно в том месте, где мы попытаемся свой тип складывать в unordered_set. Не забудем дописать MyHasher, проверим, что это всё у нас компилируется. Да, действительно, у нас всё скомпилировалось, мы смогли всё правильно сделать. Итак, что мы с вами сегодня сделали? Мы с вами сегодня закончили наш разговор о том, как писать хеш-функции для собственных типов. В качестве распространённых подходов можно отметить следующие: во-первых, если ваш класс содержит поля стандартных типов, то для хеширования этих полей можно использовать стандартные хешеры из библиотеки. Во-вторых, для некоторых типов могут быть уже написаны хешеры - например, вами. Для комбинации нескольких хешей часто используют их как коэффициенты при вычислении некого многочлена. И главное, помните самое важное - что после применения всех рассмотренных рекомендаций ваша хеш-функция должна давать равномерное распределение по корзинкам. О том, как выполнять проверку хорошего распределения хеш-функций, вы увидите в задаче после этого видео.
