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

294

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

ricree
источник
4
Вот проницательный разговор о словарях Python от 2.7 до 3.6. Ссылка
Sören

Ответы:

494

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

  • Словари 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сравнение) записи в слоте с хешем и ключом текущей записи, которую нужно вставить ( 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 могут иметь одинаковые значения хеш-функции. Я разместил здесь слегка отредактированную версию ответа, потому что все исследования очень актуальны и для этого вопроса.

Правин Голлакота
источник
9
Вы сказали, что когда и хеш, и ключ совпадают, он (вставка op) сдается и уходит. Не вставляет перезаписать существующую запись в этом случае?
0xc0de
65

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

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

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

Упорядоченный аспект неофициальный с 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 ), проверьте, чтобы ключи были равны (используя тот же алгоритм, описанный ранее), и, если это так, верните значение.

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

Раймонд Хеттингер (Raymond Hettinger) представил это на 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__или __new__, иначе вы не сможете сэкономить место.

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

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

Аарон Холл
источник
1
Вы сказали «мы» и «позволить другим реализациям Python шанс наверстать упущенное» - означает ли это, что вы «знаете вещи» и что это может стать постоянной функцией? Есть ли какие-либо недостатки в том, что заказы диктуются спецификацией?
toonarmycaptain
Недостаток заказа заключается в том, что, если ожидается, что заказы будут заказываться, они не смогут легко переключиться на более качественную / быструю реализацию, которая не заказана. Хотя вряд ли так будет. Я «знаю вещи», потому что я смотрю много разговоров и читаю много вещей, написанных основными членами и другими людьми с лучшей реальной репутацией, чем я, поэтому даже если у меня нет источника, на который можно сразу ссылаться, я обычно знаю о чем я говорю Но я думаю, что вы можете понять это из одного из выступлений Раймона Хеттингера.
Аарон Холл
1
Вы несколько расплывчато объяснили, как работает вставка («Если хэш закончился так же, как хеш существовавшего ранее ключа, ... тогда он поместил бы пару ключ-значение в другое место» - любой?), Но вы не объяснили как работает поиск и проверка членства. Не совсем понятно, как местоположение определяется хэшем, но я полагаю, что размер всегда равен степени 2, и вы берете последние несколько бит хэша ...
Алексей
@Alexey Последняя ссылка, которую я предоставляю, дает вам хорошо аннотированную реализацию dict - где вы можете найти функцию, которая делает это, в настоящее время в строке 969, которая называется find_empty_slot: github.com/python/cpython/blob/master/Objects/dictobject.c # L969 - и начиная со строки 134, есть некоторая проза, которая описывает это.
Аарон Холл
46

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

NB! Открытая адресация , иначе говоря, закрытое хеширование , не следует путать с противоположным открытым хэшированием!

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

u0b34a0f6ae
источник
5
«Не путайте с противоположным открытым хэшированием! (которое мы видим в принятом ответе)». - Я не уверен, какой ответ был принят, когда вы это написали, или что этот ответ сказал в то время, - но этот комментарий в скобках в настоящее время не соответствует принятому ответу и его лучше удалить.
Тони Делрой