Best way to hash a dictionary

[Alex Martelli]

Miki Tebeka wrote:

> Hello Andres,
>> Compute the hash as the xor of the hash of the items.  That way you
>> don't need to sort first, and you'll get an O(n) hash instead of
>> O(n*log(n)).
> Can you give an example?

I gave an example of hashing just the keys in a previous post, as in
general it need not be the case that values are also hashable -- if
they are, then just throw them into the pot too, using the following
snippet rather than what I had previously posted:

class Hash2dict(dict):

    def __init__(self, *args, **kwds):
        dict.__init__(self, *args, **kwds)
        myhash = 0
        for it in self.iteritems(): myhash ^= hash(it)
        self.myhash = myhash

    def __hash__(self):
        return self.myhash

> Does this gives uniq keys?

Nope, but that's not a requirement for hash -- Python's dicts' code
is quite adept at handling collisions.  The fewer collisions the
better, of course, but no need to go out of your way for that.

> (BTW: n < 20 always)

Good, then Hash2dict.__init__ won't take all THAT long;-).


Alex