Arch Linux

vkumar

Member

Registered: 2008-10-06

Posts: 166

[solved] issue with hashing generators in python

It's often useful to memoize values, so they can be reused [1].

Lists can't be memoized because they're mutable and can't be hashed. Tuples can be memoized, are immutable, and have (more-or-less) unique hashes that reflect their contents.

Generators behave oddly. It looks like they can be memoized, but their hashes are mostly non-unique. They can be used as keys in a dictionary, but when performing lookups, raise KeyErrors.

>>> a = {f(): 1, g(): 2}
>>> a
{<generator object f at 0x7f0e09c968c0>: 1, <generator object g at 0x7f0e09c96870>: 2}
>>> a[f()]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: <generator object f at 0x7f0e09c96910>
>>> hash(f())
8731141904002
>>> hash(f())
8731141904002
>>> hash(g())
8731141904002
>>> hash(g())
8731141904002

Why are hashes for generators the same? Why are hashes for other types of generators (e.g range()) a different, constant value? Why am I getting this KeyError?

[1]: http://wiki.python.org/moin/PythonDecor … ry#Memoize

edit: Wait, I get it. The hashes are the same because the source of the generator is the same. Python can't look inside to see what values are in the generator and tell them apart that way. I got a KeyError because the id()s of the objects are different. That is to say, though the hash had a match in the dictionary, the contents of the bucket were different (again: different ids).

Last edited by vkumar (2011-06-06 16:20:48)

---

div curl F = 0

the_isz

Member

Registered: 2009-04-14

Posts: 280

Re: [solved] issue with hashing generators in python

In python, functions are first-class objects. Your functions f and g return
different function objects upon each call, which is why your lookup fails.

The hash function calls an object's __hash__ member function which is the same
for each of these objects.

So, what you could do to solve your problem is this:

>>> a = {hash(f()): 1, hash(g()): 2}

Tes--

Member

Registered: 2009-11-13

Posts: 44

Re: [solved] issue with hashing generators in python

Edit: What does memoizing a generator even mean?

Last edited by Tes-- (2011-06-08 14:04:06)