Хеши


Для решения удобно воспользоваться хеш-функцией, которая возвращает уникальное значение для каждой строки (хеш).
В С++ 11 есть встроенное средства для получения хеша: hash. 
В дальнейшем для подсчета количества хешей лучше использовать хеш-таблицу unordered_map, которая тоже появилась в С++ 11. Подробнее про использование map можно узнать в курсе Динамические структуры данных -> Ассоциативные массивы: map.

Пример получения хеша из строки "test":

hash<string> hash_fn;
size_t str_hash = hash_fn("test");
cout<<str_hash;

В результате будет выведено: "2949673445", таким образом от каждой уникальной строки можно получить уникальный хеш, который можно использовать в качестве ключа в unordered_map.

Задача для тренировки:

Хеши: Начало (C++)

Хэширование строки - представление строки в виде какого-то числа, уникального (будем считать, что шанс коллизии пренебрежительно мал) для каждой строки. Это позволяет хранить какие либо важные данные (вроде паролей) в базе данных не в виде строк, а в виде чисел. Это позволяет защитить пароли, если злоумышленник получит доступ к базе данных паролей, ибо он получит не сами пароли, а только их численное представление, а получить строку по ее хэшу (особенно не зная алгоритм хэширования) практически невозможно. 
В задачах по олимпиадному программированию чаще всего используется полиномиальный хэш.
Один из лучших способов определить хэш-функцию от строки S следующий:
h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N

Задача для тренировки:

HASH

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация