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

Кто-нибудь знает, как реализован встроенный тип словаря для python? My understanding is that it is some sort of hash table, but I haven't been able to find any sort of definitive answer.

Источник

4 ответа

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

Источник

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

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

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

Упорядоченный аспект неофициальный, начиная с Python 3.6, но официальный в Python 3.7.

Словари Python - это хеш-таблицы

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

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

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

Источник

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

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

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

Источник

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

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

    Второй массив представляет собой плотный массив. Вот что там происходит:
  • В нулевом индексе введите значение.

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