Словарь (тип данных)
Это понятие впервые встречается на программе «Электроника, программирование и инженерная практика» — примерно 13-14 лет (7-8 класс).
Хранилище пар «ключ — значение»: называешь ключ — получаешь значение. Как бумажный словарь: слово — перевод.
Контакты в телефоне: номер находишь по имени человека, а не по месту в списке.
Назвать три пары «ключ — значение» из жизни: имя — номер телефона, слово — перевод, фамилия — оценка в журнале.
Тип данных, хранящий пары «ключ — значение»: значение находят по ключу, а не по номеру, как в списке. Ключи не повторяются: запись по новому ключу добавляет пару, по существующему — заменяет старое значение новым.
Смоделировать словарь в Scratch двумя списками «имена» и «рекорды»: по имени игрока найти его рекорд; объяснить, что сломается, если одно имя попадёт в список дважды.
Ассоциативный массив — коллекция пар «ключ — значение» с доступом по ключу. Обычная реализация — хеш-таблица: место записи вычисляется из ключа хеш-функцией, поэтому поиск в среднем за O(1), а в списке — перебор за O(n). Ключ обязан быть неизменяемым (в Python — число, строка, кортеж). Краевой случай — коллизия: разные ключи дают один хеш, и таблица различает их дополнительными сравнениями.
Заполнить в Python список пар и dict сотней тысяч записей; замерить (timeit) поиск одного значения в каждом и объяснить разницу через хеш-таблицу.
Частое заблуждение
«Словарь — тот же список, только с подписями». Нет: в списке элемент ищут по номеру, в словаре — по ключу; порядковых номеров у пар нет.