Кто-нибудь знает, как реализован встроенный тип словаря для python? Я понимаю, что это какая-то хэш-таблица, но я не смог найти какой-либо окончательный ответ.
Как реализованы встроенные словари Python?
Ответ 1
Здесь все о питонах Питона, которые я смог собрать (возможно, больше, чем кто-либо хотел бы знать, но ответ исчерпывающий).
- Словари 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 для алгоритма для зондирования). Важно то, что слоты исследуются до тех пор, пока не будет найден первый пустой слот. - То же самое происходит и для поисков, просто начинается с начального слота я (где я зависит от хэша ключа). Если хэш и ключ не совпадают с входом в слот, он начинает зондирование, пока не найдет слот с совпадением. Если все слоты исчерпаны, он сообщает об ошибке.
- BTW, размер
dict
будет изменен, если он заполнен на две трети. Это позволяет избежать замедления поиска. (см. dictobject.h: 64-65)
ПРИМЕЧАНИЕ. Я провел исследование по реализации Python Dict в ответ на мой собственный question о том, как несколько записей в dict могут иметь одинаковые значения хэш-функции. Я опубликовал немного отредактированную версию ответа здесь, потому что все исследования очень актуальны и для этого вопроса.
Ответ 2
Словари Python используют открытую адресацию (ссылка внутри красивого кода)
NB! Открытая адресация, a.k.a закрытое хеширование, как отмечается в Википедии, не следует путать с противоположным открытым хэшированием!
Открытая адресация означает, что dict использует слоты массива, и когда первичная позиция объекта занимает в dict, место объекта ищется по другому индексу в том же массиве, используя схему "возмущения", где значение хеш-функции объекта играет роль. ,
Ответ 3
Как реализованы встроенные словари 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__
см. здесь мой ответ.
Смотрите также:
- PEP 509 - добавить личную версию для диктовки
- PEP 468 - Сохранение порядка
**kwargs
в функции. - PEP 520 - Сохранение порядка определения атрибутов класса
- PyCon 2010: словарь могущества - Брэндон Роудс
- PyCon 2017: толковый словарь - Брэндон Роудс
- PyCon 2017: современные словари Python Слияние дюжины великих идей - Рэймонд Хеттингер
- dictobject.c - фактическая реализация dict в CPython на C.
Ответ 4
Это хэш-таблица. Вы можете прочитать об этом в python wiki. В противном случае код хорошо написан и должен быть легко понят.