В Python словари (или dict для краткости) являются центральной структурой данных. Словари хранят любое количество объектов, каждый из которых идентифицируется уникальным словарным ключом. Словари также часто назавают сопоставлениями, хэшкартами, поисковыми таблицами или асоциативными массивами. Они позволяют очень эффективно находить, помещать в словарь и удалять из словаря любой объект относящийся в определенному ключу.

Что это значит на практике? Оказывается, что простым аналогом словарей в нашем мире является телефонный справочник:

Телефонные книги позволяют быстро получить информацию (номер телефона), связанную с определенным ключом (имя человека). Таким образом, вместо того, чтобы читать телефонную книгу с самого начала и до конца, чтобы найти чей-то номер, вы можете перейти более или менее непосредственно к имени и посмотреть на информацию, связанную с этим именем.

Эта аналогия несколько отличается на практике, когда дело доходит до того, как информация организована, что не всегда позволяет обеспечить быстрый поиск. Но фундаментальные характеристики производительности остаются прежними: словари позволяют быстро находить информацию, связанную с определнным ключом. Таким образом, словари являются одной из наиболее часто используемых и наиболее важных структур данных в информатике.

Итак, как Python обрабатывает словари? Давайте рассмотрим реализации словаря, доступные в ядре Python и стандартной библиотеке Python.

Dict – это словарь

Из-за важности словарей Python имеет отличную нативную реализацию dict в ядре языка.

Python также предоставляет полезный “синтаксический сахар” для работы со словарями. Например, синтаксис словарных выражений с фигурными скобками позволяют удобно определять новые объекты словаря:

phonebook = { 'bob': 7387,
    'alice': 3719,
    'jack': 7052,
}

squares = {x: x * x for x in range(6)} 

>>> phonebook['alice']
3719

>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

Существуют некоторые ограничения на использование объектов в качестве допустимых ключей.

Словари Python индексируются ключами, которые могут иметь любой хэшируемый тип: хэшируемый объект имеет хэш-значение, которое никогда не меняется в течение его жизни (см. __ hash__), и его можно сравнить с другими объектами (см. __eq__). Кроме того, хэшируемые объекты, которые сравниваются как равные, должны иметь одинаковое хэш-значение.

Неизменяемые типы, такие как строки и числа относятся к хэшируемым типам и хорошо работают в качестве ключей словаря. Можно также использовать объекты кортежей в качестве ключей словаря, если они содержат только сами хэшируемые типы.

Для большинства случаев использование встроенной реализации словаря Python сделает все необходимое. Словари хорошо оптимизированы и лежат в основе многих частей языка, например атрибуты класса и переменные в стеке хранятся внутри словарей.

Словари Python основаны на хорошо протестированной и точно настроенной реализации хэш-таблиц, которая обеспечивает ожидаемые характеристики производительности.

Не так много причин не использовать стандартную реализацию dict Python. Однако существуют специализированные сторонние словарные реализации, например, списки пропуска или справочники на основе B-дерева.

Помимо «простых» объектов dict, стандартная библиотека Python также включает ряд специализированных реализаций словаря. Эти специализированные словари основаны на встроенном словаре (и поддерживаются его характеристиками), но добавляют при этом некоторые удобные функции.

Давайте посмотрим на некоторые из них.

collections.OrderedDict – Помните о порядке ввода ключей

Python включает специализированный подкласс dict, который запоминает порядок вставки ключей, добавленных к нему: collections.OrderedDict.

Хотя стандартные экземпляры dict сохраняют порядок вставки ключей в CPython 3.6 и выше, это просто побочный эффект реализации CPython и не определен в спецификации языка. Итак, если порядок ключей важен для работы вашего алгоритма, лучше всего это четко выразить, явно используя класс OrderDict.

Кстати, OrderedDict не является встроенной частью основного языка и должен быть импортирован из модуля коллекций в стандартную библиотеку.

>>> import collections

>>> d = collections.OrderedDict(one=1, two=2, three=3)

>>> d
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> d['four'] = 4

>>> d
OrderedDict([('one', 1), ('two', 2),
				('three', 3), ('four', 4)]) 

>>> d.keys()
odict_keys(['one', 'two', 'three', 'four'])

collections.defaultdict – Возвращает значения по умолчанию для отсутствующих ключей

Класс defaultdict - это другой подкласс словаря, который принимает в своем конструкторе callable-объект, возвращающее значение которого будет использоваться, если запрошенный ключ не может быть найден.

Это может сохранить вам некоторую типизацию и сделать намерения программиста более ясными и понятными по сравнению с использованием методов get () или перехвата исключения KeyError в обычных словарях.

>>> from collections import defaultdict 

>>> dd = defaultdict(list)

# Создается доступ к отстутствующим ключам
# для инициализации используются значения шаблона, 
# т.е. в данном примере в качестве шаблона используется объект list():
>>> dd['dogs'].append('Rufus')
>>> dd['dogs'].append('Kathrin')
>>> dd['dogs'].append('Mr Sniffles')

>>> dd['dogs']
['Rufus', 'Kathrin', 'Mr Sniffles']

В указанном выше примере структура словаря dd определяется шаблоном объекта list (списка, массива), т.е. фактически такая конструкция определяет, что ключ dogs являются списком (массивом).

collections.ChainMap – Поиск нескольких словарей как единого сопоставления

Структура данных collections.ChainMap группирует несколько словарей в один объект (цепочку). Поиск осуществляет базовые сопоставления по каждому словарю, пока не будет найден ключ. Вставки, обновления и удаления влияют только на первое сопоставление, добавленное в цепочку.

>>> from collections import ChainMap 

>>> dict1 = {'one': 1, 'two': 2}

>>> dict2 = {'three': 3, 'four': 4} 

>>> chain = ChainMap(dict1, dict2)

>>> chain
ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})

# ChainMap в каждой коллекции в цепочке
# слева направо, пока не найдет искомый ключ (или выдаст ошибку поиска ключа): 

>>> chain['three']
3
>>> chain['one']
1
>>> chain['missing']
KeyError: 'missing'

types.MappingProxyType – Wrapper для создания Read-Only словарей

MappingProxyType - это обертка вокруг стандартного словаря, которая обеспечивает просмотр Read-Only данных обернутого словаря. Этот класс был добавлен в Python 3.3, и его можно использовать для создания неизменяемых прокси-версий словарей.

Например, это может быть полезно, если вы хотите вернуть внутреннее состояние, поддерживающее словарь, из класса или модуля, в то же время препятствуя доступу на запись к этому объекту. Использование MappingProxyType позволяет установить эти ограничения без предварительного создания полной копии документа.

>>> from types import MappingProxyType

>>> writable = {'one': 1, 'two': 2}

>>> read_only = MappingProxyType(writable)

# В данном примере в качестве прокси-словаря выступает read-only:
>>> read_only['one']
1

>>> read_only['one'] = 23
TypeError:
"'mappingproxy' object does not support item assignment"

# Обновление оригинала, отражается на прокси:
>>> writable['one'] = 42

>>> read_only
mappingproxy({'one': 42, 'two': 2})

Словари в Python: Заключение

Все версии словаря Python, перечисленные в этой главе, являются допустимыми реализациями, встроенными в стандартную библиотеку Python.

Если вы ищете общую рекомендацию о том, какой тип отображения использовать в ваших программах, обратите внимание прежде всего на встроенный тип данных dict. Это универсальная и оптимизированная реализация хеш-таблицы, встроенная непосредственно на основной язык.

Можно порекомендовать использовать один из других типов данных, перечисленных здесь, если у вас есть особые требования, выходящие за рамки того, что предоставляется dict.

При том, что все они являются допустимыми параметрами, но обычно ваш код будет более понятным и более простым в обслуживании другими разработчиками, если он в большинстве случаев использует стандартные словари Python.

Основные выводы

• Словари - это центральная структура в Python.

• Встроенный тип dict будет «достаточно хорошим» в большинстве случаев.

• Специализированные реализации, например, только для чтения или упорядоченные словари, доступны в стандартной библиотеке Python.

Источник: “Python Tricks The Book” Dan Bader