Вопрос по python – Хеширование неизменного словаря в Python

16

Short version: Какой лучший алгоритм хеширования для мультимножества реализован в виде словаря неупорядоченных элементов?

Я пытаюсь хэшировать неизменный мультимножество (которое является сумкой или мультимножеством в других языках: подобно математическому набору, за исключением того, что оно может содержать более одного каждого элемента), реализованное в виде словаря. Я создал подкласс стандартного библиотечного классаcollections.Counter, аналогично совету здесь:Python hashable dicts, который рекомендует хеш-функцию, например, так:

<code>class FrozenCounter(collections.Counter):
    # ...
    def __hash__(self):
        return hash(tuple(sorted(self.items())))
</code>

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

Я думаю об использовании этого алгоритма:

<code>def __hash__(self):
    return functools.reduce(lambda a, b: a ^ b, self.items(), 0)
</code>

Я понимаю, используя побитовые XOR средстваorder doesn't matter for the hash value unlike in the hashing of a tuple? Я полагаю, что я мог бы частично реализовать алгоритм Python-хэширования кортежей в неупорядоченном потоке кортежей моих данных. Увидетьhttps://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (найдите на странице слово «hash») - но я едва знаю достаточно C, чтобы прочитать его.

Thoughts? Suggestions? Thanks.

(If you're wondering why I'm messing around with trying to hash a multiset: Входными данными для моей задачи являются наборы мультимножеств, и в каждом наборе мультимножеств каждый набор должен быть уникальным. Я работаю в сжатые сроки и не являюсь опытным программистом, поэтому я хотел избежать, по возможности, изобретать новые алгоритмы. Кажется, что самый Pythonic способ убедиться, что у меня есть уникальные из множества вещей, это поместить их вset(), но вещи должны быть хаси.)

What I've gathered from the comments

И @marcin, и @senderle дали почти одинаковый ответ: используйтеhash(frozenset(self.items())), Это имеет смысл, потому чтоitems() "views" are set-like, @marcin был первым, но я поставил галочку на @senderle из-за хороших исследований времени запуска big-O для различных решений. @marcin также напоминает мневключить__eq__ method - но тот, унаследованный отdict будет работать просто отлично. Вот как я все реализую - приветствуются дальнейшие комментарии и предложения, основанные на этом коде:

<code>class FrozenCounter(collections.Counter):
    # Edit: A previous version of this code included a __slots__ definition.
    # But, from the Python documentation: "When inheriting from a class without
    # __slots__, the __dict__ attribute of that class will always be accessible,
    # so a __slots__ definition in the subclass is meaningless."
    # http://docs.python.org/py3k/reference/datamodel.html#notes-on-using-slots
    # ...
    def __hash__(self):
        "Implements hash(self) -> int"
        if not hasattr(self, '_hash'):
            self._hash = hash(frozenset(self.items()))
        return self._hash
</code>
Тыsure делаяtuple занимает много памяти? Это просто «указатель» каждому элементу в диктовке, а не его копии, которая создается. agf
+1 за исчерпывающее обновление вопроса, а также за окончательную реализацию. mklauber
Проверять, выписыватьсяcs.toronto.edu/~tijmen/programming/immutableDictionaries.html wkschwartz
Любой объект, который можно хэшировать, можно заказать. Если он хешируемый, то он всегда создает один и тот же хеш, поэтому сортируйте по хешу. senderle

Ваш Ответ

2   ответа
1

hash(sorted(hash(x) for x in self.items()))? Таким образом, вы сортируете только целые числа, и вам не нужно составлять список.

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

Как вариант, похожий на мой ответВот, hash(frozenset(self.items())).

13

вы можете создать хеш при создании словаря и вернуть его напрямую. Мое предложение было бы создатьfrozenset отitems (в 3+;iteritems в 2.7), хэшируйте и сохраняйте хеш.

Чтобы предоставить явный пример:

>>>> frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems())
frozenset([(3, 2), (1, 3), (4, 1), (2, 1)])
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems()))
-3071743570178645657
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 4]).iteritems()))
-6559486438209652990

Чтобы уточнить, почему я предпочитаюfrozenset к кортежу отсортированных предметов:frozenset не нужно сортировать элементы (потому что они стабильно упорядочены по их хэшу в памяти), и поэтому начальный хэш должен завершаться за время O (n), а не O (n log n). Это видно изfrozenset_hash а такжеset_next Реализации.

Похожие вопросы