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

I Я пытаюсь хешировать неизменяемый мультимножество (которое в других языках является сумкой или мультимножеством: похоже на математический набор, за исключением того, что оно может содержать более одного элемента каждого), реализованное в виде словаря.Я создал подкласс стандартного библиотечного класса 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()"представления" подобны множествам. @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