Питон hashable предсказывает

хэш-таблицы должны быть неизменяемыми - не применяя это, но доверяя вам не мутировать dict после его первого использования в качестве ключа, будет работать следующий подход:

class hashabledict(dict):
  def __key(self):
    return tuple((k,self[k]) for k in sorted(self))
  def __hash__(self):
    return hash(self.__key())
  def __eq__(self, other):
    return self.__key() == other.__key()

Если вам нужно мутировать свои дикты и все еще хотите использовать их в качестве ключей, сложность взрывается в сотни раз-не сказать, что это невозможно, но я подожду до очень конкретного указания, прежде чем попасть в эту невероятную трясину!- )

все, что нужно, чтобы словари можно было использовать для ваших целей, это добавить__ hash _ _ метод:

class Hashabledict(dict):
    def __hash__(self):
        return hash(frozenset(self))

внимание frozenset преобразование будет работать для всех словарей (т. е. не требует сортировки ключей). Кроме того, нет никаких ограничений на значения словарь.

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

class Hashabledict(dict):
    def __hash__(self):
        return hash((frozenset(self), frozenset(self.itervalues())))

это быстрее, чем frozenset(self.iteritems()) по двум причинам. Во-первых,frozenset(self) шаг повторно использует хэш-значения, хранящиеся в словаре, сохраняя ненужные вызовы hash(key). Во-вторых, используя itervalues будет иметь доступ к значениям напрямую и избежать многих вызовов распределителя памяти с помощью предметы для формирования новых много кортежей ключ / значение в памяти каждый раз, когда вы делаете поиск.

ответы-это хорошо, но они могут быть улучшены с помощью frozenset(...) вместо tuple(sorted(...)) для генерации хэша:

>>> import timeit
>>> timeit.timeit('hash(tuple(sorted(d.iteritems())))', "d = dict(a=3, b='4', c=2345, asdfsdkjfew=0.23424, x='sadfsadfadfsaf')")
4.7758948802947998
>>> timeit.timeit('hash(frozenset(d.iteritems()))', "d = dict(a=3, b='4', c=2345, asdfsdkjfew=0.23424, x='sadfsadfadfsaf')")
1.8153600692749023

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

достаточно чистая, простая реализация

import collections

class FrozenDict(collections.Mapping):
    """Don't forget the docstrings!!"""

    def __init__(self, *args, **kwargs):
        self._d = dict(*args, **kwargs)

    def __iter__(self):
        return iter(self._d)

    def __len__(self):
        return len(self._d)

    def __getitem__(self, key):
        return self._d[key]

    def __hash__(self):
        return hash(tuple(sorted(self._d.iteritems())))

я все время возвращаюсь к этой теме... Вот еще один вариант. Мне непросто с подклассами dict добавить __hash__ метод; практически нет выхода из проблемы, что dict изменчивы, и доверие к тому, что они не изменятся, кажется слабой идеей. Поэтому я вместо этого посмотрел на построение отображения на основе встроенного типа, который сам по себе неизменен. хотя tuple является очевидным выбором, доступ к значениям в нем подразумевает сортировку и деление пополам; не проблема, но это, похоже, не так используя большую часть мощности типа, на котором он построен.

что делать, если вы застряли ключ, значение пары в frozenset? Что для этого потребуется, как это будет работать?

Часть 1, вам нужен способ кодирования ' item таким образом, что frozenset будет обрабатывать их в основном своими ключами; я сделаю для этого небольшой подкласс.

import collections
class pair(collections.namedtuple('pair_base', 'key value')):
    def __hash__(self):
        return hash((self.key, None))
    def __eq__(self, other):
        if type(self) != type(other):
            return NotImplemented
        return self.key == other.key
    def __repr__(self):
        return repr((self.key, self.value))

это само по себе ставит вас в плевок расстояние неизменного отображения:

>>> frozenset(pair(k, v) for k, v in enumerate('abcd'))
frozenset([(0, 'a'), (2, 'c'), (1, 'b'), (3, 'd')])
>>> pairs = frozenset(pair(k, v) for k, v in enumerate('abcd'))
>>> pair(2, None) in pairs
True
>>> pair(5, None) in pairs
False
>>> goal = frozenset((pair(2, None),))
>>> pairs & goal
frozenset([(2, None)])

ох! К сожалению, когда вы используете операторы set и элементы равны, но не один и тот же объект; который заканчивается в возвращаемом значении undefined, нам придется пройти еще несколько вращений.

>>> pairs - (pairs - goal)
frozenset([(2, 'c')])
>>> iter(pairs - (pairs - goal)).next().value
'c'

однако поиск значений таким образом является громоздким и, что еще хуже, создает множество промежуточных наборов; это не будет делать! Мы создадим "поддельную" пару ключ-значение, чтобы обойти ее:

class Thief(object):
    def __init__(self, key):
        self.key = key
    def __hash__(self):
        return hash(pair(self.key, None))
    def __eq__(self, other):
        self.value = other.value
        return pair(self.key, None) == other

что приводит к менее проблематично:

>>> thief = Thief(2)
>>> thief in pairs
True
>>> thief.value
'c'

вот и вся глубокая магия; остальное оборачивает все это во что-то, что имеет интерфейс как дикт. Так как мы подклассы от frozenset, который имеет очень другой интерфейс, есть довольно много методов; мы получаем небольшую помощь от collections.Mapping, но большая часть работы-это переопределение frozenset методы для версий, которые работают, как предсказывает, вместо:

class FrozenDict(frozenset, collections.Mapping):
    def __new__(cls, seq=()):
        return frozenset.__new__(cls, (pair(k, v) for k, v in seq))
    def __getitem__(self, key):
        thief = Thief(key)
        if frozenset.__contains__(self, thief):
            return thief.value
        raise KeyError(key)
    def __eq__(self, other):
        if not isinstance(other, FrozenDict):
            return dict(self.iteritems()) == other
        if len(self) != len(other):
            return False
        for key, value in self.iteritems():
            try:
                if value != other[key]:
                    return False
            except KeyError:
                return False
        return True
    def __hash__(self):
        return hash(frozenset(self.iteritems()))
    def get(self, key, default=None):
        thief = Thief(key)
        if frozenset.__contains__(self, thief):
            return thief.value
        return default
    def __iter__(self):
        for item in frozenset.__iter__(self):
            yield item.key
    def iteritems(self):
        for item in frozenset.__iter__(self):
            yield (item.key, item.value)
    def iterkeys(self):
        for item in frozenset.__iter__(self):
            yield item.key
    def itervalues(self):
        for item in frozenset.__iter__(self):
            yield item.value
    def __contains__(self, key):
        return frozenset.__contains__(self, pair(key, None))
    has_key = __contains__
    def __repr__(self):
        return type(self).__name__ + (', '.join(repr(item) for item in self.iteritems())).join('()')
    @classmethod
    def fromkeys(cls, keys, value=None):
        return cls((key, value) for key in keys)

который, в конечном счете, отвечает моим собственным вопрос:

>>> myDict = {}
>>> myDict[FrozenDict(enumerate('ab'))] = 5
>>> FrozenDict(enumerate('ab')) in myDict
True
>>> FrozenDict(enumerate('bc')) in myDict
False
>>> FrozenDict(enumerate('ab', 3)) in myDict
False
>>> myDict[FrozenDict(enumerate('ab'))]
5

принятый ответ @Unknown, а также ответ @AlexMartelli работают отлично, но только при следующих ограничениях:

словарь должен быть hashable. Например, hash(hashabledict({'a':[1,2]})) поднять TypeError.
1. ключи должны поддерживать операции сравнения. Например, hash(hashabledict({'a':'a', 1:1})) поднять TypeError.
2. оператор сравнения по ключам накладывает общий порядок. Например, если два ключа в словаре frozenset((1,2,3)) и frozenset((4,5,6)), они считаются равными в обоих направлениях. Поэтому сортировка элементов словаря с такими ключами может привести к произвольному порядку, а значит нарушит правило, что одинаковые объекты должны иметь одинаковое хэш-значение.

гораздо более быстрый ответ @ObenSonne снимает ограничения 2 и 3, но по-прежнему соблюдать ограничения 1 (значения должны быть hashable).

чем быстрее еще ответ @RaymondHettinger снимает все 3 ограничения, потому что это не так включить .values() в расчете хэша. Однако его производительность хороша только в том случае, если:

1. большинство (неравных) словарей, которые должны быть хэшированы, не идентичны .keys().

если это условие не выполняется, хэш-функция по-прежнему будет действительна, но может вызвать слишком много коллизий. Например, в крайнем случае, когда все словари генерируются из шаблона веб-сайта (имена полей как ключи, пользовательский ввод как значения), Ключи будут всегда быть таким же, и хэш-функция будет возвращать одно и то же значение для всех входов. В результате хэш-таблица, которая полагается на такую хэш-функцию, станет такой же медленной, как и список при получении элемента (O(N) вместо O(1)).

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

Я был бы очень признателен за любую обратную связь по этому поводу, так как я только проверил это слегка до сих пор.

# python 3.4
import collections
import operator
import sys
import itertools
import reprlib

# a wrapper to make an object hashable, while preserving equality
class AutoHash:
    # for each known container type, we can optionally provide a tuple
    # specifying: type, transform, aggregator
    # even immutable types need to be included, since their items
    # may make them unhashable

    # transformation may be used to enforce the desired iteration
    # the result of a transformation must be an iterable
    # default: no change; for dictionaries, we use .items() to see values

    # usually transformation choice only affects efficiency, not correctness

    # aggregator is the function that combines all items into one object
    # default: frozenset; for ordered containers, we can use tuple

    # aggregator choice affects both efficiency and correctness
    # e.g., using a tuple aggregator for a set is incorrect,
    # since identical sets may end up with different hash values
    # frozenset is safe since at worst it just causes more collisions
    # unfortunately, no collections.ABC class is available that helps
    # distinguish ordered from unordered containers
    # so we need to just list them out manually as needed

    type_info = collections.namedtuple(
        'type_info',
        'type transformation aggregator')

    ident = lambda x: x
    # order matters; first match is used to handle a datatype
    known_types = (
        # dict also handles defaultdict
        type_info(dict, lambda d: d.items(), frozenset), 
        # no need to include set and frozenset, since they are fine with defaults
        type_info(collections.OrderedDict, ident, tuple),
        type_info(list, ident, tuple),
        type_info(tuple, ident, tuple),
        type_info(collections.deque, ident, tuple),
        type_info(collections.Iterable, ident, frozenset) # other iterables
    )

    # hash_func can be set to replace the built-in hash function
    # cache can be turned on; if it is, cycles will be detected,
    # otherwise cycles in a data structure will cause failure
    def __init__(self, data, hash_func=hash, cache=False, verbose=False):
        self._data=data
        self.hash_func=hash_func
        self.verbose=verbose
        self.cache=cache
        # cache objects' hashes for performance and to deal with cycles
        if self.cache:
            self.seen={}

    def hash_ex(self, o):
        # note: isinstance(o, Hashable) won't check inner types
        try:
            if self.verbose:
                print(type(o),
                    reprlib.repr(o),
                    self.hash_func(o),
                    file=sys.stderr)
            return self.hash_func(o)
        except TypeError:
            pass

        # we let built-in hash decide if the hash value is worth caching
        # so we don't cache the built-in hash results
        if self.cache and id(o) in self.seen:
            return self.seen[id(o)][0] # found in cache

        # check if o can be handled by decomposing it into components
        for typ, transformation, aggregator in AutoHash.known_types:
            if isinstance(o, typ):
                # another option is:
                # result = reduce(operator.xor, map(_hash_ex, handler(o)))
                # but collisions are more likely with xor than with frozenset
                # e.g. hash_ex([1,2,3,4])==0 with xor

                try:
                    # try to frozenset the actual components, it's faster
                    h = self.hash_func(aggregator(transformation(o)))
                except TypeError:
                    # components not hashable with built-in;
                    # apply our extended hash function to them
                    h = self.hash_func(aggregator(map(self.hash_ex, transformation(o))))
                if self.cache:
                    # storing the object too, otherwise memory location will be reused
                    self.seen[id(o)] = (h, o)
                if self.verbose:
                    print(type(o), reprlib.repr(o), h, file=sys.stderr)
                return h

        raise TypeError('Object {} of type {} not hashable'.format(repr(o), type(o)))

    def __hash__(self):
        return self.hash_ex(self._data)

    def __eq__(self, other):
        # short circuit to save time
        if self is other:
            return True

        # 1) type(self) a proper subclass of type(other) => self.__eq__ will be called first
        # 2) any other situation => lhs.__eq__ will be called first

        # case 1. one side is a subclass of the other, and AutoHash.__eq__ is not overridden in either
        # => the subclass instance's __eq__ is called first, and we should compare self._data and other._data
        # case 2. neither side is a subclass of the other; self is lhs
        # => we can't compare to another type; we should let the other side decide what to do, return NotImplemented
        # case 3. neither side is a subclass of the other; self is rhs
        # => we can't compare to another type, and the other side already tried and failed;
        # we should return False, but NotImplemented will have the same effect
        # any other case: we won't reach the __eq__ code in this class, no need to worry about it

        if isinstance(self, type(other)): # identifies case 1
            return self._data == other._data
        else: # identifies cases 2 and 3
            return NotImplemented

d1 = {'a':[1,2], 2:{3:4}}
print(hash(AutoHash(d1, cache=True, verbose=True)))

d = AutoHash(dict(a=1, b=2, c=3, d=[4,5,6,7], e='a string of chars'),cache=True, verbose=True)
print(hash(d))

вы также можете добавить эти два метода, чтобы заставить протокол маринования v2 работать с экземплярами hashdict. В противном случае cPickle попытается использовать hashdict.____setitem класса____ в результате исключение TypeError. Интересно, что с двумя другими версиями протокола ваш код работает просто отлично.

def __setstate__(self, objstate):
    for k,v in objstate.items():
        dict.__setitem__(self,k,v)
def __reduce__(self):
    return (hashdict, (), dict(self),)

Если вы не помещаете числа в словарь и никогда не теряете переменные, содержащие ваши словари, вы можете сделать это:

cache[id(rule)] = "whatever"

так как id () уникален для каждого словаря

EDIT:

о, Извините, да, в таком случае то, что сказали другие ребята, было бы лучше. Я думаю, что вы также можете сериализовать свои словари в виде строки, например

cache[ 'foo:bar' ] = 'baz'

Если вам нужно восстановить словари из ключей хотя, тогда вам придется сделать что-то более уродливое, как

cache[ 'foo:bar' ] = ( {'foo':'bar'}, 'baz' )

Я думаю, преимущество этого заключается в том, что вам не придется писать столько кода.