Вопрос-Ответ

How are Python's Built In Dictionaries Implemented?

Как реализованы встроенные словари Python?

Кто-нибудь знает, как реализован встроенный тип словаря для python? Насколько я понимаю, это своего рода хэш-таблица, но я не смог найти какого-либо окончательного ответа.

Переведено автоматически
Ответ 1

Редактировать:

Этот ответ предназначен для версий Python более ранних, чем 3.6. Для Python 3.6 и далее смотрите Ответ России-необходимо-удалить-Путина ниже.

Оригинал:

Вот все о Python dicts, которые я смог собрать воедино (вероятно, больше, чем кто-либо хотел бы знать; но ответ исчерпывающий).


  • Словари Python реализованы в виде хэш-таблиц.



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



  • Python dict использует открытую адресацию для разрешения коллизий хэшей (описано ниже) (см. dictobject.c: 296-297).



  • Хэш-таблица Python - это просто непрерывный блок памяти (что-то вроде массива, поэтому вы можете выполнять O(1) поиск по индексу).



  • В каждом слоте таблицы может храниться одна и только одна запись. Это важно.



  • Каждая запись в таблице на самом деле представляет собой комбинацию трех значений: < хэш, ключ, значение >. Это реализовано как структура C (см. dictobject.h: 51-56).



  • На рисунке ниже представлено логическое представление хэш-таблицы Python. На рисунке ниже, 0, 1, ..., i, ... слева приведены индексы слотов в хэш-таблице (они приведены только для иллюстрации и, очевидно, не хранятся вместе с таблицей!).


      # Logical model of Python Hash table
      -+-----------------+
      0| <hash|key|value>|
      -+-----------------+
      1|      ...        |
      -+-----------------+
      .|      ...        |
      -+-----------------+
      i|      ...        |
      -+-----------------+
      .|      ...        |
      -+-----------------+
      n|      ...        |
      -+-----------------+


  • Когда инициализируется новый dict, он начинается с 8 слотов. (см. dictobject.h: 49 )



  • При добавлении записей в таблицу мы начинаем с некоторого слота, i который основан на хэше ключа. Изначально CPython использует i = hash(key) & mask (где mask = PyDictMINSIZE - 1, но это не очень важно). Просто обратите внимание, что начальный слот, i который проверяется, зависит от хэша ключа.



  • Если этот слот пуст, запись добавляется в слот (я имею в виду запись, <hash|key|value>). Но что, если этот слот занят !? Скорее всего, потому, что другая запись имеет тот же хэш (коллизия хэшей!)



  • Если слот занят, CPython (и даже PyPy) сравнивает хэш И ключ (под сравнением я подразумеваю == сравнение, а не is comparison) записи в слоте с хэшем и ключом текущей вставляемой записи (dictobject.c:337,344-345) соответственно. Если оба совпадают, то он думает, что запись уже существует, сдается и переходит к следующей вставляемой записи. Если хэш или ключ не совпадают, начинается проверка.



  • Зондирование просто означает поиск слотов за слотом, чтобы найти пустой слот. Технически мы могли бы просто перейти по одному, i+1, i+2, ... и использовать первый доступный (это линейное зондирование). Но по причинам, прекрасно объясненным в комментариях (см. dictobject.c:33-126), CPython использует случайное зондирование. При случайном поиске следующий слот выбирается в псевдослучайном порядке. Запись добавляется в первый пустой слот. Для этого обсуждения фактический алгоритм, используемый для выбора следующего слота, на самом деле не важен (см. dictobject.c: 33-126 Алгоритм поиска). Важно то, что слоты исследуются до тех пор, пока не будет найден первый пустой слот.



  • То же самое происходит и при поиске, просто начинается с начального слота i (где i зависит от хэша ключа). Если хэш и ключ не совпадают с записью в слоте, он начинает поиск, пока не найдет слот с совпадением. Если все слоты исчерпаны, он сообщает о сбое.



  • Кстати, размер dict будет изменен, если он заполнен на две трети. Это позволяет избежать замедления поиска. (см. dictobject.h: 64-65)



ПРИМЕЧАНИЕ: Я провел исследование реализации Python Dict в ответ на мой собственный вопрос о том, как несколько записей в dict могут иметь одинаковые хэш-значения. Я опубликовал здесь слегка отредактированную версию ответа, потому что все исследования очень актуальны и для этого вопроса.

Ответ 2

Как реализованы встроенные словари Python?


Вот краткий курс:


  • Это хэш-таблицы. (Смотрите ниже о специфике реализации Python.)

  • Новая компоновка и алгоритм, начиная с Python 3.6, делают их

    • упорядочены по вставке ключа и

    • занимают меньше места,

    • практически без снижения производительности.


  • Другая оптимизация экономит место, когда dicts совместно используют ключи (в особых случаях).

Упорядоченный аспект является неофициальным начиная с Python 3.6 (чтобы дать шанс другим реализациям не отставать), но официальным в Python 3.7.

Словари Python представляют собой хэш-таблицы

Долгое время это работало именно так. Python предварительно выделял 8 пустых строк и использовал хэш, чтобы определить, куда вставить пару ключ-значение. Например, если хэш для ключа заканчивается на 001, он будет помещен в 1 (т. е. 2-й) индекс (как в примере ниже.) 

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

Каждая строка занимает 24 байта в 64-битной архитектуре, 12 - в 32-битной. (Обратите внимание, что заголовки столбцов являются просто метками для наших целей здесь - на самом деле они не существуют в памяти.)

Если хэш заканчивается так же, как хэш ранее существующего ключа, это коллизия, и тогда пара ключ-значение будет перенесена в другое место.

После сохранения 5 ключей-значений при добавлении другой пары ключ-значение вероятность коллизий хэшей слишком велика, поэтому размер словаря увеличивается вдвое. В 64-битном процессе перед изменением размера у нас остается 72 пустых байта, а после мы теряем 240 байт из-за 10 пустых строк.

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

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

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

Новые компактные хэш-таблицы

Вместо этого мы начинаем с предварительного выделения массива для индекса вставки.

Поскольку наша первая пара ключ-значение находится во втором слоте, мы индексируем следующим образом:

[null, 0, null, null, null, null, null, null]

И наша таблица просто заполняется в порядке вставки:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

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

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

Рэймонд Хеттингер представил это на python-dev в декабре 2012 года. Наконец-то это попало в CPython в Python 3.6. Упорядочивание по вставке считалось деталью реализации для 3.6, чтобы дать шанс другим реализациям Python догнать его.

Общие ключи

Еще одна оптимизация для экономии места - это реализация, использующая общие ключи. Таким образом, вместо избыточных словарей, которые занимают все это пространство, у нас есть словари, которые повторно используют общие ключи и хэши ключей. Вы можете представить это следующим образом:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

Для 64-разрядной машины это может сэкономить до 16 байт на ключ в дополнительном словаре.

Общие ключи для пользовательских объектов и альтернативы

Эти термины с общим ключом предназначены для использования с пользовательскими объектами" __dict__. Чтобы добиться такого поведения, я полагаю, вам нужно завершить заполнение вашего __dict__ перед созданием экземпляра вашего следующего объекта (см. PEP 412). Это означает, что вы должны назначить все свои атрибуты в __init__ or __new__, иначе вы можете не получить экономии места.

Однако, если вы знаете все свои атрибуты во время выполнения вашего __init__, вы также можете предоставить __slots__ для своего объекта и гарантировать, что __dict__ он вообще не создается (если недоступен в родительских файлах), или даже разрешить, __dict__ но гарантировать, что ваши предусмотренные атрибуты в любом случае хранятся в слотах. Подробнее о __slots__, смотрите мой ответ здесь.

Смотрите также:

Ответ 3

Словари Python используют открытую адресацию (ссылка внутри красивого кода)

Открытая адресация ПРИМЕЧАНИЕ!, также известную как закрытое хеширование, не следует, как отмечено в Википедии, путать с противоположным ей открытым хешированием!

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

Ответ 4

Python dict теперь поддерживает два индекса. Один представляет собой разреженный массив. Это то, что он делает, когда первый элемент вставляется в dict:


  • вставить значение ключа

  • dict находит хэш ключа

  • dict сопоставляет хэш с индексом

  • в разреженном массиве находится этот индекс и вводится нулевое число (при первом вводе)

    Второй массив - это плотный массив. Вот что там происходит:

  • В нулевом индексе введите значение

    Таким образом, второй массив компактен и экономит память.
    Для последующих вставок увеличивается индекс вставки второго массива. Таким образом экономится память и сохраняется порядок вставки.
    При вставке индекса в первый разреженный массив могут возникать хэш-коллизии. Об этом заботится псевдослучайный поиск, т. Е. алгоритм, который просматривает пустые ячейки внутри массива предсказуемым, но псевдослучайным способом.
    Второй массив всегда компактный.

2024-01-03 11:23 python dictionary