python, как ключи в хранилище в словаре [duplicate]

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

• Словари Python реализованы как хеш-таблицы.
• Таблицы хэша должны разрешать хэш-коллизии, т. е. даже если два разных ключа имеют одинаковое значение хэша, реализация таблицы должна иметь стратегия для вставки и извлечения ключей и значений однозначно.
• Python dict использует открытую адресацию для разрешения хеш-коллизий (поясняется ниже) (см. dictobject.c: 296-297 ).
• Хэш-таблица Python - это просто непрерывный блок памяти (вроде массива, поэтому вы можете выполнить поиск O(1) по индексу).
• Каждый слот в таблице может хранить одну и только одну запись. Это важно.
• Каждая запись в таблице фактически представляет собой комбинацию из трех значений: & lt; хэш, ключ, значение>. Это реализовано как 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>). Но что, если этот слот занят !? Скорее всего, потому, что другая запись имеет один и тот же хеш (хеш-коллизия!) [/ ​​G20]
• Если слот занят, CPython (и даже PyPy) сравнивает хэш И ключ (по сравнению я имею в виду == сравнение не is) записи в слоте против хэша и клавиши текущей записи, которую нужно вставить ( dictobject.c: 337,344-345 ) соответственно. Если совпадают , тогда он считает, что запись уже существует, отбрасывается и переходит к следующей записи, которую нужно вставить. Если хэш или ключ не совпадают, он начинает зондирование.
• Зондинг просто означает, что он ищет слоты по слоту, чтобы найти пустой слот. Технически мы могли бы просто пойти один за другим, i+1, i+2, ... и использовать первый доступный (это линейное исследование). Но по причинам, прекрасно объясненным в комментариях (см. dictobject.c: 33-126 ), CPython использует случайное зондирование. При случайном зондировании следующий слот выбирается в псевдослучайном порядке. Запись добавляется в первый пустой слот. Для этого обсуждения фактический алгоритм, используемый для выбора следующего слота, не очень важен (см. dictobject.c: 33-126 для алгоритма для зондирования). Важно то, что слоты исследуются до тех пор, пока не будет найден первый пустой слот.
• То же самое происходит для поисковых запросов, просто начинается с начального слота i (где я зависит от хэша ключа). Если хэш и ключ не совпадают с входом в слот, он начинает зондирование, пока не найдет слот с совпадением. Если все слоты исчерпаны, он сообщает об ошибке.
• BTW, dict будет изменен, если он будет заполнен на две трети. Это позволяет избежать замедления поиска. (см. dictobject.h: 64-65 )

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

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

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

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