[БЕЗ_ЗВУКА] Здравствуйте. На прошлом занятии мы с вами разобрали, как помещать свои собственные типы данных в ассоциативные контейнеры, в частности, в хеш-таблицу. На этом занятии мы узнаем, как правильно следует писать свою собственную хеш-функцию для хеш-таблицы. Для этого снова обратимся к нашему коду. У нас есть код с прошлого занятия, где у нас написана функция main, которая заполняет контейнеры set и unordered_set, и написан простой Hasher, который используется для хеш-таблицы. И это всё у нас работает. Что мы хотим сделать сейчас? Мы хотим замерить производительность: насколько эффективно наши свежеиспеченные конструкции работают. Давайте это сделаем. У нас есть код, который занимается тестированием. Что он делает? Он просто берет первые N случайных номеров каких-то, заполняет ими структуру set, потом берет другие N случайных номеров и пытается их в этой структуре найти. Неважно, есть они там или нет. Нас интересует только скорость, с которой осуществляется поиск. Потом ровно этот же тест у нас работает для контейнера unordered_set. Берём случайные номера, складываем их в контейнер, потом берём другие случайные номера и ищем их в контейнере. Такой вот нехитрый тест. Давайте его запустим. Компилируется. Он работает, но N = 10 как-то мало, конечно, для теста, давайте возьмем N побольше. Возьмем N = 50 000. Видим, что у нас тест продолжает работать, но мы наблюдаем какой-то странный эффект. Мы видим, что наш unordered_set работает медленнее почти в два раза, чем обычный set. А это странно, мы ведь с вами знаем из предыдущих занятий, что хеш-таблица работает очень быстро. Значит, у нас что-то пошло не так. Давайте попытаемся это объяснить. Как мы знаем, у нас для разрешения коллизий в хеш-таблицах используется метод цепочек. И мы с вами говорили, это важно, чтобы такие цепочки были короткими. Давайте посмотрим, есть ли надежда в нашем коде, что цепочки будут короткими. Такой надежды, получается, что у нас и нет. Потому что у нас эксперимент состоит из 50 000 различных автомобильных номеров, а в качестве номеров корзин, то есть в качестве значений хеш-функции, мы используем только числа от 1 до 1000. То есть у нас есть всего лишь 1000 различных корзин для 50 000 автомобильных номеров. Этого явно недостаточно. И у нас будет очень много коллизий. Поэтому производительность unordered_set и снижается так сильно. Надо что-то предпринять. Каким образом? Нам нужно использовать более, чем эту 1000 корзин. Мы ведь можем написать более хитрую хеш-функцию. И мы можем написать её следующим образом. Можем использовать не только центральное число из автомобильного номера, но еще и код региона. С помощью такой нехитрой арифметической магии мы можем взять номер, умножить его на 100 и прибавить регион. Таким образом, у нас получится пятизначное число, и мы это пятизначное число уже сможем использовать в качестве значения хеш-функции. Давайте это и сделаем. Перепишем наш хеш и посмотрим, изменится ли от этого производительность. Берём, пишем точно так же, как мы захотели это сделать на слайде. [ЗВУК] Прибавляем регион и возвращаем то, что получилось, в качестве значения хеш-функции. Компилируем. Запускаем. Получилось неплохо - у нас unordered_set начал выигрывать у set. И значит, мы на верном пути. Мы делаем всё правильно, и правильно понимаем как работает хеш-таблица. Но давайте усугубим наш эксперимент. Возьмем побольше, не 50 000 тестовых номеров, а миллион. Что-нибудь изменится или нет? Собираем. Запускаем. set у нас отработал за две секунды. unordered_set больше, чем за две секунды. То есть у нас, когда тест становится серьезнее, unordered_set все-таки проигрывает по производительности. А мы знаем из теории, что не должен. И опять-таки понятно почему. Потому что у нас различных корзин 100 000 получается, потому что у нас пятизначные числа используются, а тест состоит из миллиона номеров. И у нас опять много коллизий. Окончательно решить эту проблему можно, только использовав всю информацию, которая имеется на госномере. То есть кроме чисел с госномера использовать ещё и буквы. Вы спросите: «А как же нам буквы превратить в значение хеш-функции? Ведь буквы — это буквы». Ничего страшного. Мы можем буквы конвертировать в их порядковый номер в алфавите: отняв букву А, например, получить порядковый номер. И затем эти порядковые номера использовать в такой арифметической магии, как показано на слайде. И таким образом, получить для этого автомобильного номера такое большое число. Ну что ж, давайте сделаем то, что мы собрались. Это у нас магия для букв, которая отнимает букву А и затем мы хотим число s, которое получилось после обработки букв, прибавить в наш результат. Сдвигаем на шесть нулей наш result и прибавляем то, что получилось. Компилируем и запускаем. Супер. Мы видим, что наш unordered_set стал почти в два раза быстрее. Мы сделали всё, что от нас требовалось. Мы использовали всю информацию с госномера, и поэтому у нас получилась отличная хеш-функция. Пора подводить итоги. На этом занятии мы с вами узнали, что качество хеш-функции очень сильно влияет на производительность хеш-таблицы, то есть на производительность контейнера unordered_set. И хорошая хеш-функция, которую вы пишете для достижения хорошей производительности, должна охватывать широкий диапазон корзин, а также по возможности равномерно распределять по ним объекты.
