2022-09-27 • Манипуляции со списками, хеш-функции и хеш-таблицы и перспективы использования C++

В начале занятия продолжим заниматься реверсом списка, доведем до торжествующего финала итеративный реверс списка, а рекурсивный вариант предложим слушателям в качестве несложного домашнего задания. И перейдем к хеш-функциям и хеш-таблицам. Которые важны, часто встречаются, использование которых все видели на самом-то деле, потому что слова MD5, CRC, контрольная сумма — это как раз про это. И шифрование паролей. И вообще криптография. Узнаем, что такое хеш-таблицы — это такие контейнеры для хранения данных. Данных определенной однотипной структуры. При этом важно, чтобы эти данные можно было естественным способом по ключу складывать в контейнер, быстро их там перебирать, легко искать, добавлять и удалять. Хеш-функция способна порождать из ключа какой-то числовой результат, integer, который можно назвать хеш-суммой или просто хешем. При этом хорошо бы, чтобы значения хеша были более-менее равномерно размазаны в некотором понятном интервале значений. А особенно важно, чтобы разные по ключу данные имели разные значения хеша, а одинаковые — одинаковые. Точнее, одинаковые данные обязательно должны порождать одинаковые хеши («хеш-функция односторонне однозначна»), а совпадение хешей в теории допустимо ( называется «коллизия»), но чем реже такое происходит — тем лучше. Узнаем, что делать, если коллизия таки случилась. Успеем еще посмотреть, как выглядит обычно код, использующий эту технику, какие функции там должны быть (insert, delete, lookup). И заметим, что для таких кодов вместо С прямо просится к использованию C++, который тут почти все сделает за нас.