Python hashable dicts

Ответ 1

Вот простой способ сделать словарь хеширования. Просто помните, чтобы не мутировать их после вложения в другой словарь по понятным причинам.

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

Ответ 2

Hashables должны быть неизменными - не применяя это, но TRUSTING вы не должны мутировать 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()

Если вам нужно мутировать ваши дикты, и STILL хотят использовать их в качестве ключей, сложность взрывается сториками - не сказать, что это невозможно сделать, но я подожду, пока ОЧЕНЬ конкретное указание, прежде чем я войду в THAT невероятный болото! -)

Ответ 3

Все, что необходимо для создания словарей, используемых для вашей цели, - это добавить метод __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 ​​будет напрямую обращаться к значениям и избегать многих вызовов распределителя памяти, используя элементы для формирования новых много ключевых/значений кортежей в памяти каждый раз, когда вы выполняете поиск.

Ответ 4

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

Ответ 5

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

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())))

Ответ 6

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

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

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

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)])

D'ах! К сожалению, когда вы используете операторы 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'

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

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

Ответ 7

Вы также можете добавить эти два метода, чтобы заставить протокол травления 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),)

Ответ 8

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

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

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

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

4. Большинство (неравных) словарей, которые должны быть хэшированы, не идентичны .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 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 __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))

Ответ 9

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

cache[id(rule)] = "whatever"

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

EDIT:

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

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

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

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

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