Урок 6: Хеш-таблицы и подсчёт частот

Представьте словарь: вы не читаете его с начала, а сразу переходите к слову и получаете его значение. Это и есть хеш-таблица (в Python: dict) — структура из пар ключ-значение, которая сразу переходит к нужному ключу. Проверка «встречал ли я это раньше?», которая при сканировании списка занимает O(n)

Хеш-таблица — как алфавитный указатель в конце книги: вместо того чтобы листать каждую страницу в поисках слова (это медленное «сканирование»), вы находите слово в указателе и сразу переходите на нужную страницу (это O(1) — мгновенно). Цена? Немного лишней бумаги — то есть чуть больше памяти в обмен на большую скорость.

хеш-таблица (hash map): Структура, отображающая ключ в значение с поиском и вставкой за O(1) в среднем за счёт вычисления прямого адреса из ключа. В Python это dict.
множество (set): Коллекция без дубликатов, которая проверяет принадлежность (есть ли элемент) за O(1) в среднем — удобна для поиска и удаления дубликатов.
подсчёт частот: Подсчёт того, сколько раз каждое значение встречается во входных данных, с помощью dict, который отображает значение → счётчик, за один проход O(n).