Зачем на ЕГЭ понимать модель ключ-значение
Ключ-значение встречается почти в каждом варианте экзамена. Эксперты любят задачи, где нужно быстро найти элемент по уникальному идентификатору. Школьник, игнорирующий этот приём, тратит лишние минуты и рискует ошибиться. Модель проста: ключ однозначно указывает на значение. Примером служит словарь Python. Запомнив идею, ученик легко связывает её с массивами хеш-таблиц, структурами баз данных и файловыми системами. Поэтому изучение приёма приносит пользу не только на ЕГЭ, но и в дальнейшей работе с кодом.
Теория без скуки: что скрывается под парой «key → value»
Смысл идеи в том, что данные хранятся в парах. Ключ уникален, значение нет. Операции выполняются за амортизированное O(1) благодаря хеш-функции. Это даёт колоссальное преимущество перед линейным поиском, когда массив большой. При коллизии таблица использует цепочки или открытое адресование. На школьном уровне достаточно понимать, что несколько разных ключей не конфликтуют часто, если размер таблицы выбран правильно. Стоит запомнить: порядок перебора не гарантируется. Экзаменаторы любят ловить на этом.
Ключ-значение в Python: словарь и связанная магия
Словарь создаётся фигурными скобками или функцией dict. Ключ должен быть хешируемым, значит неизменяемым. Строки, числа и кортежи подходят, списки нет. Добавление пары происходит за константное время. Метод get позволяет вернуть значение или запасной результат, если ключа нет. Такой подход спасает от KeyError в стрессовых условиях экзамена. Также полезны методы keys, values, items: они раскрывают внутренние коллекции без копирования данных. Перебор словаря даёт именно ключи, а не пары, что часто забывают.
Алгоритмы поиска и сортировки через призму словаря
Задача «найти повтор» решается простым подсчётом частот. Создаём пустой dict, идём по списку, инкрементируем счётчик. Вторая классика — поиск двух элементов, сумма которых равна X. Храним разницу X − a[i] как ключ, индекс как значение. Получаем одно проход. Длинная, но важная мысль: иногда нужно восстановить исходный порядок. Тогда храним не только индекс, но и время появления элемента. Для сортировки по ключам используем sorted(d.items()). Это создаёт список кортежей, потому что внутренний порядок неупорядочен. Экзамен ценит понимание, почему приходится копировать данные.
Типовые задания из банка ФИПИ
- Найти слово, встречающееся чаще других в тексте. Решается подсчётом частот.
- Определить, есть ли в массиве два числа, равных друг другу. Используем множество.
- Проверить, все ли элементы уникальны. Достаточно сравнить длину списка и множества.
- Сконструировать граф из списка рёбер. Храним словарь списков смежности.
- Преобразовать таблицу excel-формата в словарь по первому столбцу.
Каждое задание тренирует отдельное умение: счёт, поиск, фильтрацию, группировку. Отработайте их на автоматизм, и баллы придут.
Ошибки, на которых горят баллы
Главная беда — мутация ключей. Если ключ изменится, словарь потеряет элемент. Так происходит при использовании списка как ключа, что запрещено. Вторая ошибка — доверие к порядку вывода. С версии Python 3.7 порядок сохранён, но ФИПИ всё ещё формулирует задачи, предполагая хаос. Поэтому лучше явно сортировать. Третья ловушка — неправильное использование метода update: он перезаписывает совпадающие ключи. Хотели добавить запись, а потеряли старые данные. Последняя проблема — раздувание памяти, когда ключом делают длинные строки вместо числовых индексов.
Тренируемся разумно: мини-практикум на час
Возьмём массив длиной миллион элементов. Сначала найдём все пары чисел, сумма которых делится на 107. Словарь остатков сократит время до одного прохода. Далее запустим задачу «самая длинная подстрока без повторов» — классика для хеш-мэп. Храним последний индекс каждого символа. Сложность O(n). Последний шаг — построить инвертированный индекс для набора текстов: ключ — слово, значение — список номеров документов. На ЕГЭ такие таски короче, но сейчас лучше переработать идею на большом объёме.
Шпаргалка: как отвечать быстро и без паники
1. Определи, можно ли заменить линейный поиск словарём. 2. Оцени тип ключа: нужен hash-able объект. 3. Создай структуру через dict или set. 4. Выполни операцию в один проход. 5. При выводе отсортируй, если нужен порядок. 6. Проверяй граничные случаи: пустой ввод, один элемент, повтор ключей. 7. Оптимизируй память, удаляя неактуальные записи. Эти семь пунктов экономят время и нервы.
Готовы закрепить? Полный курс подготовки к ЕГЭ доступен в онлайн школе el-ed.ru. Там вы найдёте десятки задач, видео и живые разборы.