Статья подготовлена для студентов курса «Разработчик Python» в образовательном проекте OTUS.
Словарь в Python является фундаментальным типом хотя бы потому, что используется для хранения атрибутов объектов любого класса. Внутри словарь реализован как хеш-таблица с открытой адресацией, где коллизии разрешаются методом квадратичного пробинга, таблица расширяется при заполнении более чем на ⅔.
Вообще, словари достаточно хорошо описаны и стоят того, чтобы взглянуть на их исходники (искать в Objects/dictobject.c). Описанное устройство словарей несёт конкретные практические последствия:
- Ключ должен быть хеширумым объектом, т. е. у него должен быть определен метод __hash__, возвращающий одинаковое значение во время жизни объекта. Кстати, если у вашего типа определён метод __eq__, то обязательно должен быть и __hash__, чтобы тип корректно работал со словарями и множествами.
- Словари дают повышение накладных расходов по памяти. Это связано с тем, что хеш-таблица должна быть достаточно большой для эффективной работы с ней. Если есть, например, необходимость сохранить в массиве большое количество записей, то оптимальнее по памяти представить их в виде кортежей, нежели чем в виде словарей.
- Поиск по ключу очень быстрый. Здесь тот самый space-time tradeoff, алгоритмическая сложность доступа O(1).
- Порядок следования ключей зависит от порядка вставки в словарь. Это связано с возникающими коллизиями. При этом словари с одинаковым содержимым равны при проверке через ==.
- Модифицировать словарь, по которому итерируешься — плохая идея. В определённый момент Python может решить, что пора ресайзить хеш-таблицу и тогда старые данные переедут в новую табличку с новыми коллизиями, может измениться порядок следования ключей.
Множества аналогично реализованы через хеш-таблицу, так что к ним применимы те же следствия.
Хотите узнать больше? Записывайтесь на курс «Разработчик Python» или задавайте вопросы в комментариях!
Материал подготовлен для студентов курса «Разработчик Python» в образовательном проекте OTUS. Не забудьте пройти вступительное тестирование:
ПРОЙТИ ТЕСТИРОВАНИЕ