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

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

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

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

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

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

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

Я полагаю, что использование побитового XOR означает, что порядок не имеет значения для хеш-значения, в отличие от хэширования кортежа? Предполагаю, что я мог бы полу-реализовать алограмм арифметического кортежа Python в неупорядоченном потоке кортежей моих данных. См. https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (поиск на странице для слова "хэш" ) - но я едва знаю достаточно C, чтобы прочитать его.

Мысли? Предложения? Спасибо.

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

Что я собрал из комментариев

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

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

Ответы

Ответ 1

Поскольку словарь неизменен, вы можете создать хэш, когда словарь создан и вернуть его напрямую. Мое предложение состояло в том, чтобы создать 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 для кортежа отсортированных элементов: a frozenset не нужно сортировать элементы (потому что они стабильно упорядочены по их хешу в памяти), и поэтому исходный хэш должен завершено в O (n) времени, а не O (n log n). Это можно увидеть из frozenset_hash и set_next.

Ответ 2

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

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

В качестве альтернативы, как и мой ответ здесь, hash(frozenset(self.items())).