Хеширование словаря?

156

Для целей кэширования мне нужно сгенерировать ключ кеша из аргументов GET, которые присутствуют в dict.

В настоящее время я использую sha1(repr(sorted(my_dict.items())))( sha1()это удобный метод, который использует hashlib внутри), но мне интересно, есть ли лучший способ.

ThiefMaster
источник
4
это может не работать с вложенным dict. самое короткое решение состоит в том, чтобы использовать вместо этого json.dumps (my_dict, sort_keys = True), который будет преобразовываться в значения dict.
Андрей Федоров
2
FYI re: dumps, stackoverflow.com/a/12739361/1082367 говорит: «Выходные данные от pickle не гарантируются как канонические по аналогичным причинам, чтобы диктовать и устанавливать порядок как недетерминированный. Не используйте pickle или pprint или repr для хеширования «.
Мэтью Корнелл
сортировать ключи dict, а не элементы, я бы также отправил ключи в хэш-функцию.
nyuwec
2
Интересная предыстория о хешировании изменяемых структур данных (например, словарей): python.org/dev/peps/pep-0351 было предложено разрешить произвольное замораживание объектов, но было отклонено. Обоснование см. В этой теме в python-dev: mail.python.org/pipermail/python-dev/2006-Feb
февраля/
Если ваши данные имеют формат json и вы хотите семантически инвариантное хеширование, обратитесь к github.com/schollii/sandals/blob/master/json_sem_hash.py . Он работает на вложенных структурах (конечно, начиная с json) и не зависит от внутренних элементов dict, как сохраненный порядок (который развивался за время существования python), и даст одинаковый хеш, если две структуры данных семантически одинаковы ( как {'a': 1, 'b':2}семантически так же, как {'b':2, 'a':1}). Я еще не использовал его для чего-то слишком сложного, так что YMMV, но обратная связь приветствуется.
Оливер

Ответы:

110

Если ваш словарь не является вложенным, вы можете создать морозильник с элементами dict и использовать hash():

hash(frozenset(my_dict.items()))

Это гораздо менее вычислительно, чем генерация строки JSON или представление словаря.

ОБНОВЛЕНИЕ: Пожалуйста, смотрите комментарии ниже, почему этот подход не может дать стабильный результат.

Имран
источник
9
Это не сработало для меня с вложенным словарем. Я не пробовал решение ниже (слишком сложное). Решение ОП прекрасно работает. Я заменил sha1 хешем, чтобы сохранить импорт.
Спатель
9
@Ceaser Это не сработает, потому что кортеж подразумевает упорядочение, но элементы dict неупорядочены лучше заморозить.
Сурьма
28
Остерегайтесь встроенного хэша, если что-то должно быть согласованным на разных машинах. Реализации python на облачных платформах, таких как Heroku и GAE, будут возвращать разные значения hash () в разных экземплярах, что делает его бесполезным для всего, что должно быть разделено между двумя или более «машинами» (dynos в случае heroku)
Бен Робертс,
6
Может быть интересно, что hash()функция не выдает стабильный вывод. Это означает, что при одинаковом вводе он возвращает разные результаты с разными экземплярами одного и того же интерпретатора python. Мне кажется, что при каждом запуске интерпретатора генерируется какое-то начальное значение.
Герман Шахнер
7
ожидается. Насколько я помню, семя введено из соображений безопасности, чтобы добавить некоторую рандомизацию памяти. Таким образом, вы не можете ожидать, что хеш будет одинаковым между двумя процессами Python
Nikokrock
137

Использование sorted(d.items())недостаточно, чтобы получить стабильный репр. Некоторые значения dмогут быть словарями, и их ключи будут по-прежнему отображаться в произвольном порядке. Пока все ключи являются строками, я предпочитаю использовать:

json.dumps(d, sort_keys=True)

Тем не менее, если хэши должны быть стабильными на разных машинах или версиях Python, я не уверен, что это пуленепробиваемый. Вы можете добавить separatorsи ensure_asciiаргументы , чтобы защитить себя от каких - либо изменений по умолчанию там. Буду признателен за комментарии.

Джек О'Коннор
источник
6
Это просто параноик, но JSON позволяет большинству символов отображаться в строках без экранирования литералов, поэтому кодировщик может сделать выбор: экранировать символы или просто пропустить их. Таким образом, существует риск того, что разные версии (или будущие версии) кодировщика могут по умолчанию делать разные варианты экранирования, и тогда ваша программа будет вычислять разные значения хеш-функции для одного и того же словаря в разных средах. ensure_asciiАргумент будет защищать против этого совершенно гипотетической проблемы.
Джек О'Коннор
4
Я проверил производительность этого с другим набором данных, это намного быстрее, чем make_hash. gist.github.com/charlax/b8731de51d2ea86c6eb9
Чарлакс
3
@charlax ujson не гарантирует порядок пар dict, поэтому делать это
небезопасно
11
Это решение работает только до тех пор, пока все ключи являются строками, например, сбой json.dumps ({'a': {(0, 5): 5, 1: 3}}).
Кади
5
@LorenzoBelli, вы можете преодолеть это, добавив default=strв dumpsкоманду. Кажется, работает хорошо.
mlissner
63

РЕДАКТИРОВАТЬ : Если все ваши ключи являются строками , то прежде чем продолжить читать этот ответ, пожалуйста, посмотрите значительно более простое (и более быстрое) решение Джека О'Коннора (которое также работает для хэширования вложенных словарей).

Хотя ответ принят, заголовок вопроса - «Хеширование словаря питона», и в отношении этого заголовка ответ неполон. (Что касается основной части вопроса, ответ полный.)

Вложенные словари

Если кто-то ищет в Stack Overflow способ хэширования словаря, он может наткнуться на этот метко озаглавленный вопрос и оставить неудовлетворенным, если кто-то пытается хэшировать несколько вложенных словарей. Ответ выше не сработает в этом случае, и вам придется реализовать какой-то рекурсивный механизм для извлечения хеша.

Вот один из таких механизмов:

import copy

def make_hash(o):

  """
  Makes a hash from a dictionary, list, tuple or set to any level, that contains
  only other hashable types (including any lists, tuples, sets, and
  dictionaries).
  """

  if isinstance(o, (set, tuple, list)):

    return tuple([make_hash(e) for e in o])    

  elif not isinstance(o, dict):

    return hash(o)

  new_o = copy.deepcopy(o)
  for k, v in new_o.items():
    new_o[k] = make_hash(v)

  return hash(tuple(frozenset(sorted(new_o.items()))))

Бонус: хеширование объектов и классов

hash()Функция отлично работает , когда вы хэширования классы или экземпляры. Тем не менее, вот одна проблема, которую я нашел с хэшем, что касается объектов:

class Foo(object): pass
foo = Foo()
print (hash(foo)) # 1209812346789
foo.a = 1
print (hash(foo)) # 1209812346789

Хэш остается тем же, даже после того, как я изменил foo. Это связано с тем, что идентичность foo не изменилась, поэтому хеш остается тем же. Если вы хотите, чтобы foo хэшировал по-разному в зависимости от его текущего определения, решение состоит в том, чтобы хэшировать все, что на самом деле меняется. В этом случае __dict__атрибут:

class Foo(object): pass
foo = Foo()
print (make_hash(foo.__dict__)) # 1209812346789
foo.a = 1
print (make_hash(foo.__dict__)) # -78956430974785

Увы, когда вы пытаетесь сделать то же самое с самим классом:

print (make_hash(Foo.__dict__)) # TypeError: unhashable type: 'dict_proxy'

Свойство класса __dict__не является обычным словарем:

print (type(Foo.__dict__)) # type <'dict_proxy'>

Вот механизм, аналогичный предыдущему, который будет обрабатывать классы соответствующим образом:

import copy

DictProxyType = type(object.__dict__)

def make_hash(o):

  """
  Makes a hash from a dictionary, list, tuple or set to any level, that 
  contains only other hashable types (including any lists, tuples, sets, and
  dictionaries). In the case where other kinds of objects (like classes) need 
  to be hashed, pass in a collection of object attributes that are pertinent. 
  For example, a class can be hashed in this fashion:

    make_hash([cls.__dict__, cls.__name__])

  A function can be hashed like so:

    make_hash([fn.__dict__, fn.__code__])
  """

  if type(o) == DictProxyType:
    o2 = {}
    for k, v in o.items():
      if not k.startswith("__"):
        o2[k] = v
    o = o2  

  if isinstance(o, (set, tuple, list)):

    return tuple([make_hash(e) for e in o])    

  elif not isinstance(o, dict):

    return hash(o)

  new_o = copy.deepcopy(o)
  for k, v in new_o.items():
    new_o[k] = make_hash(v)

  return hash(tuple(frozenset(sorted(new_o.items()))))

Вы можете использовать это, чтобы вернуть кортеж хэша, сколько угодно элементов:

# -7666086133114527897
print (make_hash(func.__code__))

# (-7666086133114527897, 3527539)
print (make_hash([func.__code__, func.__dict__]))

# (-7666086133114527897, 3527539, -509551383349783210)
print (make_hash([func.__code__, func.__dict__, func.__name__]))

ПРИМЕЧАНИЕ: весь приведенный выше код предполагает использование Python 3.x. Не тестировал в более ранних версиях, хотя я предполагаю, что make_hash()будет работать, скажем, в 2.7.2. Что касается делает работу примеров, я действительно знаю , что

func.__code__ 

следует заменить на

func.func_code
jomido
источник
isinstance принимает последовательность для второго аргумента, поэтому будет работать isinstance (o, (set, tuple, list)).
Xealot
спасибо, что заставил меня понять, что frozenset может последовательно хэшировать параметры
строки
1
Элементы должны быть отсортированы, чтобы создать один и тот же хэш, если порядок элементов dict отличается, но значения ключей не отличаются -> вернуть хэш (tuple (frozenset (sorted (new_o.items ()))))
Bas Koopmans
Ницца! Я также добавил вызов hashвокруг списков и кортежей. В противном случае он берет мои списки целых чисел, которые оказались значениями в моем словаре, и возвращает обратно списки хэшей, а это не то, что я хочу.
OSA
Frozenset - это НЕПРАВИЛЬНАЯ коллекция, так что нечего извлекать, сортируя входные данные. Списки и кортежи, с другой стороны, являются коллекциями ORDERED («последовательности»), и поэтому на значение хеш-функции должен влиять порядок элементов внутри. Вы не должны сортировать их!
RobM
14

Вот более четкое решение.

def freeze(o):
  if isinstance(o,dict):
    return frozenset({ k:freeze(v) for k,v in o.items()}.items())

  if isinstance(o,list):
    return tuple([freeze(v) for v in o])

  return o


def make_hash(o):
    """
    makes a hash out of anything that contains only list,dict and hashable types including string and numeric types
    """
    return hash(freeze(o))  
smartnut007
источник
Если вы измените if isinstance(o,list):на, if isinstance(obj, (set, tuple, list)):то эта функция может работать на любом объекте.
Питер Шорн
10

Приведенный ниже код избегает использования хэш-функции Python, поскольку она не будет предоставлять хеш-коды, которые являются согласованными при перезапусках Python (см. Хеш-функция в Python 3.3 возвращает разные результаты между сессиями ). make_hashable()преобразует объект во вложенные кортежи, а make_hash_sha256()также преобразует в repr()хеш SHA256 в кодировке base64.

import hashlib
import base64

def make_hash_sha256(o):
    hasher = hashlib.sha256()
    hasher.update(repr(make_hashable(o)).encode())
    return base64.b64encode(hasher.digest()).decode()

def make_hashable(o):
    if isinstance(o, (tuple, list)):
        return tuple((make_hashable(e) for e in o))

    if isinstance(o, dict):
        return tuple(sorted((k,make_hashable(v)) for k,v in o.items()))

    if isinstance(o, (set, frozenset)):
        return tuple(sorted(make_hashable(e) for e in o))

    return o

o = dict(x=1,b=2,c=[3,4,5],d={6,7})
print(make_hashable(o))
# (('b', 2), ('c', (3, 4, 5)), ('d', (6, 7)), ('x', 1))

print(make_hash_sha256(o))
# fyt/gK6D24H9Ugexw+g3lbqnKZ0JAcgtNW+rXIDeU2Y=
Клаудио Фахи
источник
1
make_hash_sha256(((0,1),(2,3)))==make_hash_sha256({0:1,2:3})==make_hash_sha256({2:3,0:1})!=make_hash_sha256(((2,3),(0,1))), Это не совсем то решение, которое я ищу, но это хорошее промежуточное звено. Я думаю о добавлении type(o).__name__в начало каждого из кортежей, чтобы вызвать дифференциацию.
Пойк
Если вы хотите отсортировать список также:tuple(sorted((make_hashable(e) for e in o)))
Suraj
make_hash_sha256 () - хорошо!
jtlz2
1
@Suraj Вы не должны сортировать список перед хэшированием, потому что списки, содержимое которых имеет разный порядок, однозначно не одно и то же. Если порядок элементов не имеет значения, проблема в том, что вы используете неправильную структуру данных. Вы должны использовать набор вместо списка.
Scottclowe
@scottclowe Это очень верно. Спасибо за добавление этого пункта. Есть 2 сценария, в которых вы все еще хотите получить список (без особых потребностей в заказе) - 1. Список повторяющихся элементов. 2. Когда вам нужно использовать JSON напрямую. Поскольку JSON не поддерживает «заданное» представление.
Сурадж
5

Обновлено с 2013 года ответить ...

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

Как насчет этого вместо этого?

import hashlib

def dict_hash(the_dict, *ignore):
    if ignore:  # Sometimes you don't care about some items
        interesting = the_dict.copy()
        for item in ignore:
            if item in interesting:
                interesting.pop(item)
        the_dict = interesting
    result = hashlib.sha1(
        '%s' % sorted(the_dict.items())
    ).hexdigest()
    return result
Стив Йиго
источник
Как вы думаете, почему важно dict.itemsне возвращать предсказуемо упорядоченный список? frozensetпозаботится об этом
гларрей
2
Набор по определению неупорядочен. Таким образом, порядок добавления объектов не имеет значения. Вы должны понимать, что встроенная функция hashне заботится о том, как распечатывается содержимое frozenset или что-то в этом роде. Протестируйте его на нескольких машинах и версиях Python, и вы увидите.
гларрей
Почему вы используете дополнительный вызов hash () в значении = хэш ('% s ::% s'% (значение, тип (значение))) ??
RuiDo
4

Чтобы сохранить порядок ключей, вместо hash(str(dictionary))или hash(json.dumps(dictionary))я предпочел бы быстрое и грязное решение:

from pprint import pformat
h = hash(pformat(dictionary))

Это будет работать даже для типов, подобных DateTimeи более, которые не сериализуемы в JSON.

shirk3y
источник
3
Кто гарантирует, что pformat или json всегда используют один и тот же порядок?
ThiefMaster
1
@ThiefMaster, «Изменено в версии 2.5: словари сортируются по ключу до вычисления дисплея; до 2.5 словарь сортировался, только если для его отображения требовалось более одной строки, хотя это не было задокументировано». ( Docs.python. org / 2 / library / pprint.html )
Арель
2
Это не кажется мне действительным. Авторы понимают, что модули pprint и pformat предназначены для отображения, а не для сериализации. Из-за этого вы не должны чувствовать себя в безопасности, предполагая, что pformat всегда будет возвращать результат, который срабатывает.
Дэвид Сандерс
3

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

from frozendict import frozendict
my_dict = frozendict(my_dict)

Для обработки вложенных объектов вы можете использовать:

import collections.abc

def make_hashable(x):
    if isinstance(x, collections.abc.Hashable):
        return x
    elif isinstance(x, collections.abc.Sequence):
        return tuple(make_hashable(xi) for xi in x)
    elif isinstance(x, collections.abc.Set):
        return frozenset(make_hashable(xi) for xi in x)
    elif isinstance(x, collections.abc.Mapping):
        return frozendict({k: make_hashable(v) for k, v in x.items()})
    else:
        raise TypeError("Don't know how to make {} objects hashable".format(type(x).__name__))

Если вы хотите поддерживать больше типов, используйте functools.singledispatch(Python 3.7):

@functools.singledispatch
def make_hashable(x):
    raise TypeError("Don't know how to make {} objects hashable".format(type(x).__name__))

@make_hashable.register
def _(x: collections.abc.Hashable):
    return x

@make_hashable.register
def _(x: collections.abc.Sequence):
    return tuple(make_hashable(xi) for xi in x)

@make_hashable.register
def _(x: collections.abc.Set):
    return frozenset(make_hashable(xi) for xi in x)

@make_hashable.register
def _(x: collections.abc.Mapping):
    return frozendict({k: make_hashable(v) for k, v in x.items()})

# add your own types here
Эрик
источник
Это не работает, например, для dictиз DataFrameобъектов.
Джеймс Хиршорн
@JamesHirschorn: обновлен до громкого сбоя
Эрик
Лучше! Я добавил следующее elifпредложение, чтобы оно работало с DataFrames: elif isinstance(x, pd.DataFrame): return make_hashable(hash_pandas_object(x).tolist()) я отредактирую ответ и посмотрю, принимаете ли вы его ...
Джеймс Хиршорн,
1
ХОРОШО. Я вижу, что просил нечто большее, чем «hashable», который только гарантирует, что равные объекты будут иметь одинаковый хеш. Я работаю над версией, которая даст одинаковое значение между запусками и независимо от версии Python и т. Д.
Джеймс Хиршорн,
1
hashрандомизация - это преднамеренная функция безопасности, включенная по умолчанию в python 3.7.
Эрик
1

Вы можете использовать библиотеку карт, чтобы сделать это. В частности, карты. FrozenMap

import maps
fm = maps.FrozenMap(my_dict)
hash(fm)

Чтобы установить maps, просто сделайте:

pip install maps

Он также обрабатывает вложенный dictслучай:

import maps
fm = maps.FrozenMap.recurse(my_dict)
hash(fm)

Отказ от ответственности: я автор mapsбиблиотеки.

Педро Каттори
источник
Библиотека не сортирует список внутри dict. И, следовательно, это может привести к другому хешу. Должна быть опция сортировки списка. Заморозка должна помочь, но мне интересно, как бы вы справились со случаем с помощью вложенного диктата, содержащего список диктов. Как продиктовано непоколебимо.
Сурадж
1
@Suraj: он делает ручки вложенную структуру с помощью .recurse. См. Maps.readthedocs.io/en/latest/api.html#maps.FrozenMap.recurse . Порядок в списках имеет смысл с семантической точки зрения, если вы хотите независимость порядка, вы можете преобразовать свои списки в наборы до вызова .recurse. Вы также можете использовать list_fnпараметр, чтобы .recurseиспользовать другую хешируемую структуру данных, чем tuple(.eg frozenset)
Pedro
0

Один из способов решения этой проблемы - создать кортеж из словаря:

hash(tuple(my_dict.items()))
анонимное
источник
-8

Я делаю это так:

hash(str(my_dict))
garbanzio
источник
1
Может кто-нибудь объяснить, что не так с этим методом?
Христос
7
Таким образом, словари @maximi не являются стабильными с точки зрения порядка hash(str({'a': 1, 'b': 2})) != hash(str({'b': 2, 'a': 1}))(хотя это может работать для некоторых словарей, но не гарантируется , что оно будет работать для всех).
Влад Фролов