Здравствуйте! На прошлом занятии мы узнали, что контейнер unordered_map в некоторых случаях работает быстрее, чем обычный map. На этом занятия мы разберём почему он быстрее. Для этого мы решим задачу, в которой нам необходимо реализовать свой простой ассоциативный контейнер, а именно электронную копилку. Мы хотим уметь считать сколько купюр разного номинала у нас накопилось. Давайте напишем код и посмотрим, что у нас получается. Значит, купюра у нас задается номиналом, и пускай у нас все купюры приходят из входного потока. Вот мы их все считали. Дальше, нам их надо куда-то сложить. Давайте для этого заведём вектор. И индексом в этом векторе будут номиналы купюр, те самые. Этот вектор мы вынуждены завести длиной 5001, потому что у нас максимальная купюра это 5000 и ещё +1, потому что индексация начинается с нуля. Когда мы вводим число с клавиатуры или с входного потока, мы складываем его в нашу копилку, то есть увеличиваем счётчик. Таким образом, мы сейчас считали все номиналы купюр из входного потока и положили их вектор. Что делаем дальше? Дальше нам нужно напечатать, что же у нас получилось. Значит, пробежимся по всему вектору, и для тех купюр, которые присутствуют в копилке - значит, что у них счётчик не равен нулю - мы напечатаем их количество. Так, ну вроде бы отлично, запускаем, собрали. Где мы возьмем купюры? Они у нас заранее приготовлены и лежат во входном файле input.txt. Вот мы видим, что у нас есть набор каких-то купюр. Запустим нашу программу на этом входном файле. Наша программа работает, и она действительно подсчитывает для купюр их количество, то что надо. Казалось бы, то что надо, но давайте посмотрим какие недостатки есть у нашей программы. Из плюсов отметим то, что программа очень простая, она просто использует номинал купюр в качестве индекса и делает инкремент в векторе. Всё, супер просто, ошибиться невозможно. Какие недостатки? Мы для такой простой задачи выделили вектор длиной 5001 - это чрезмерно много, особенно, если мы вспомним, что различных купюр у нас всего лишь 8. Представьте, что у нас максимальная купюра была бы не 5000, а просто какого-нибудь сумасшедше большого номинала, у нас бы даже памяти не хватило выделить такой большой вектор, как бы мы тогда решали задачу? Вернемся к коду, исправим 5001 на 8 и думаем: как же нам быть? Мы можем сложить разные купюры в вектор длины 8, если напишем функцию, которая вычисляет индекс для купюры, для каждого номинала. Она проверяет, какая купюра пришла на вход и возвращает соответствующий индекс. Таких сравнений у нас должно быть, соответственно, 8, в них будут фигурировать все наши купюры, и соответственно, возвращать индексы. Как ожидается у нас, 8 различных купюр на вход и 8 различных индексов на выход. Как мы это используем? Там где мы обращаемся к элементам вектора - мы используем функцию получения индекса. Казалось бы всё, но единственное, что будет некрасиво, это что мы будем распечатывать индекс от нуля до семи вместо обозначения купюры. Давайте заведём вспомогательный вектор, тоже длинны 8, в который сложим человеческие названия наших купюр. Это будут, конечно, те же самые номиналы. Итак, запускаем, собрали, почти работает. Почему? Потому что мы забыли, когда распечатаем, использовать эти самые названия. Ещё разок - отлично, теперь мы видим, что программа работает, что она возвращает тот же самый результат, которого мы добились с самого начала. И мы сэкономили очень большое количество памяти, написав функцию получения индекса. Это отлично, более того, из кода становится понятно, что мы можем задавать купюры и другим способом, например, используя их названия, а не числовой номинал. Для нас задача практически не меняется, мы просто перепишем функцию получения индекса, где будем сравнивать строки вместо чисел, и, таким образом, мы сможем использовать строковые названия в качестве ключей. Удобно. Более того, вместо купюр мы можем решать аналогичную задачу для произвольного набора строк. Всё что нам понадобится сделать - это написать функцию перевода этих строк в индексы. Например, если мы сможем написать такую функцию для набора цветов, то мы сможем использовать эти цвета в качестве ключей. Для такой функции получения индекса есть специальное название, она называется хеш-функцией. Мы увидели из примеров, как хеш-функция помогает нам использовать строки в качестве ключей, отражая их в индексы. Что же дальше? Дальше мы отметим, что хеш-функция может, в общем случае, отображать в индексы не только строки, но и произвольные объекты. Рассмотрим, в качестве объекта, российский автомобильный номер, он состоит из нескольких цифр, букв и номера региона. Предложим простую хеш-функцию, которая определяет индекс автомобильного номера, как число из его середины. С помощью неё мы можем раскладывать номера по 1000 разных корзин. Обратите внимание, что всевозможных автомобильных номеров существует очень много, но их никак не получится разложить всего лишь по тысяче корзин без повторений. Если два номера отличаются между собой только буквами или регионом, то они попадают в одну корзину, такая ситуация называется коллизией. Итак, на этом занятии мы узнали, что такое хеш-функция - она отображает объекты любого типа в числа. И что такое коллизия в хеш-функциях - это когда два разных объекта отображаются в одно число. На следующем занятии мы продолжим изучать внутреннее устройство ассоциативных контейнеров.
