Comments 7
Да, спасибо, довольно дельно.
Особенно понравилось, что гарантия сохранения порядка элементов в словаре это следствие борьбы за уменьшение памяти, а не просто «мы напряглись и сделали OrderDict по дефолту»
Особенно понравилось, что гарантия сохранения порядка элементов в словаре это следствие борьбы за уменьшение памяти, а не просто «мы напряглись и сделали OrderDict по дефолту»
Может показаться странным считать объекты с равными хешами равными, не проверять дополнительно их содержимое, и целиком полагаться только на хеш, но вы это делаете регулярно, когда пользуетесь протоколами git или torrent.
Вот только в приведенных примерах и подобных им проектах используются криптографические хэши, а не простой полином, как в hash() для строк.
Тем более, что т.к. классы могут переопределять свой __hash__, и спецификация языка явно разрешает одинаковый хэш для разных объектов, просто слепо надеяться на то, что это не сломается? Ну хз.
И прямо до этого предложения идёт следующий текст.
Разумеется, это не более чем занимательный факт, в реальности не стоит так делать с данными, получаемыми от пользователей. Конечно, можно заменить стандартный хеш на что-то более криптостойкое и выбросить проверку объектов на равенство, в рельности не факт, что вы получите серьёзный прирост скорости, и, разумеется, если вам нужны такие оптимизации, вы где-то на предыдущих этапах свернули не туда.
Какова вероятность такого исхода? Примерно 2^-64, разумеется из-за лёгкой предсказуемости значения хеша, можно легко подобрать такой пример, но в реальности до этой проверки выполнение доходит не часто, насколько? Raymond Hettinger собрал интерпретатор, изменив последнюю операцию сравнения простым return true. Т.е. интерпретатор считал объекты равными, если их хеши равны. После чего натравил на такой интерпретатор автоматизированные тесты многих популярных проектов, которые завершились успешно.
Разумеется, это не более чем занимательный факт, в реальности не стоит так делать с данными, получаемыми от пользователей. Конечно, можно заменить стандартный хеш на что-то более криптостойкое и выбросить проверку объектов на равенство, в рельности не факт, что вы получите серьёзный прирост скорости, и, разумеется, если вам нужны такие оптимизации, вы где-то на предыдущих этапах свернули не туда.
Можете объяснить что будет если удалять и создавать тот же елемент в новом словаре?
Я так понял что размер должен постоянно расти, но думаю, что вряд ли это так:
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']]
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']]
Кеш, вроде, не трогается, но можете сами это проверить, подебажив интерпретатор. :)
Спасибо, с удовольствием прочёл статью, очень познавательно.
Вы не могли бы добавить пример с внутренней структурой indices и entries в словаре, в который добавили 2 элемента с одинаковыми хешами?
Sign up to leave a comment.
Немного внутренностей словарей в CPython (и PyPy)