Немного внутренностей словарей в CPython (и PyPy)

[artemisia_borealis]

Да, спасибо, довольно дельно.

Особенно понравилось, что гарантия сохранения порядка элементов в словаре это следствие борьбы за уменьшение памяти, а не просто «мы напряглись и сделали OrderDict по дефолту»

[LinearLeopard]

Это, кстати, позволяет ещё увеличить скорость итерирования, так как мы реже пропускаем пустые элементы. В новых словарях они могут появиться только при удалении элементов, в старых же мы вынуждены пропускать от трети до половины элементов, так как они пусты.

[mwizard]

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

Вот только в приведенных примерах и подобных им проектах используются криптографические хэши, а не простой полином, как в hash() для строк.

Тем более, что т.к. классы могут переопределять свой __hash__, и спецификация языка явно разрешает одинаковый хэш для разных объектов, просто слепо надеяться на то, что это не сломается? Ну хз.

[LinearLeopard]

И прямо до этого предложения идёт следующий текст.

Какова вероятность такого исхода? Примерно 2^-64, разумеется из-за лёгкой предсказуемости значения хеша, можно легко подобрать такой пример, но в реальности до этой проверки выполнение доходит не часто, насколько? Raymond Hettinger собрал интерпретатор, изменив последнюю операцию сравнения простым return true. Т.е. интерпретатор считал объекты равными, если их хеши равны. После чего натравил на такой интерпретатор автоматизированные тесты многих популярных проектов, которые завершились успешно.

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

[ADR]

Можете объяснить что будет если удалять и создавать тот же елемент в новом словаре?

Я так понял что размер должен постоянно расти, но думаю, что вряд ли это так:

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
                [-8522787127447073495, 'barry', 'green'],
                [-6480567542315338377, 'guido', 'blue']]

del the_dict['timmy']

indices =  [None, 1, None, None, None, None, None, 2]
entries =  [DKIX_DUMMY,
                [-8522787127447073495, 'barry', 'green'],
                [-6480567542315338377, 'guido', 'blue']]

the_dict['timmy'] = 'red'

indices =  [None, 1, None, None, None, 3, None, 2]
entries =  [DKIX_DUMMY,
                [-8522787127447073495, 'barry', 'green'],
                [-6480567542315338377, 'guido', 'blue'],
                [-9092791511155847987, 'timmy', 'red']]

[LinearLeopard]

DKIX_DUMMY — значение индекса (что спрятано в DKIX — dict key index, не очень красноречиво, согласен.)

После удаления словарь будет выглядеть примерно так:

indices =  [None, 1, None, None, None, DKIX_DUMMY, None, 2]
entries =  [[-9092791511155847987, None, None],
                [-8522787127447073495, 'barry', 'green'],
                [-6480567542315338377, 'guido', 'blue']]

Кеш, вроде, не трогается, но можете сами это проверить, подебажив интерпретатор. :)

[emigrant90]

Спасибо, с удовольствием прочёл статью, очень познавательно.

Вы не могли бы добавить пример с внутренней структурой indices и entries в словаре, в который добавили 2 элемента с одинаковыми хешами?