315 subscribers

Словари, ассоциативные массивы и хеш-таблицы. Структуры данных Python #1

110 full reads

Извиняюсь за задержку, пришлось на время отойти от Дзена. Однако, уже сейчас вы узнаете почему словари в Python — центральная структура данных и какие есть вариации словарей из встроенных библиотек. Начнем!

Введение в Python dict

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

Словари также нередко называют ассоциативными массивами (associative arrays), ассоциативными хеш-таблицами (hashmaps), поисковыми таблицами (lookup tables) или таблицами преобразования. Они допускают эффективный поиск, вставку и удаление любого объекта, связанного с заданным ключом. 

Что это означает на практике? Оказывается, что телефонные книги представляют собой достойный аналог объектов-словарей из реальной жизни: 

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

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

Резюмируя, словари — это одна из наиболее часто используемых и самых важных структур данных в информатике. 

Итак, каким же образом Python обращается со словарями? 

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

dict — ваш дежурный словарь

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

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

Работа со словарями
Работа со словарями

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

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

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

Нет особых причин не использовать стандартную реализацию dict, включенную в Python. Тем не менее существуют специализированные сторонние реализации словаря, например списки с пропусками или словари на основе В-деревьев. 

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

Давайте их рассмотрим. 

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

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

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

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

Пример работы OrderedDict
Пример работы OrderedDict

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

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

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

Работа с defaultdict
Работа с defaultdict

collections.ChainMap — производит поиск в многочисленных словарях как в одной таблице соответствия

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

Работа с ChainMap
Работа с ChainMap

types.MappingProxyType — обертка для создания словарей только для чтения

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

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

Работа с MappingProxyType
Работа с MappingProxyType

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

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

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

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

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

Ключевые выводы 

  • Словари — это единственная центральная структура данных в Python.
  • Встроенный тип dict будет «вполне приемлем» в большинстве случаев.
  • Специализированные реализации, такие как словари с доступом только для чтения или упорядоченные словари, имеются в стандартной библиотеке Python. 

Если вам понравилась статья, то пожалуйста, поставьте лайк и оставьте любой комментарий, это очень поможет в продвижении статьи!

#структуры данных #технологии #python #программирование #интернет