hashkey/digest for a complex object

Arnaud Delobelle arnodel at gmail.com
Sun Oct 10 17:49:30 CEST 2010


kj <no.email at please.post> writes:

> In <87hbgu8irb.fsf at gmail.com> Arnaud Delobelle <arnodel at gmail.com> writes:

[...]

>>And, in fact,
>>(-1) is the only int such that hash(x) != x.
>
> Arnaud, how did you determine that -1 is the only such int?  I
> can't imagine any other approach other than a brute-force check of
> all ints...  When I tried this I ran into unforeseen limitations
> in xrange, etc.  It's all very doable, but still, it would take at
> least about 3 hours on my laptop.

I looked at the source, namely the get_hash() function in the
intobject.c file in the 2.x source, and the get_hash() function in the
longobject.c file in the 3.x source.

>>In can only guess that (-1) is a value that has a special meaning when
>>hashing.  Try this (Python 2.6):
>
>>>>> class A(object):
>>...     def __hash__(self): return -1
>>... 
>>>>> a = A()
>>>>> hash(a)
>>-2
>
> Very cool.
>
> BTW, thank you for the explanation in your previous post.  It makes
> a lot of sense.  I find it interesting (as Hrvoje pointed out) that
> the hash function is (or appears to be) idempotent on integers
> (long or not), even though it is not the identity on the integers.
> Thanks to Steven for the counterexamples to show the latter.  I've
> learned tons from this exchange.

It still seems to hold that hash() is idempotent on all objects.

I have learnt too that hash(-1) is not (-1), and that it seems that a
hash value is not allowed to be (-1).  There is one thing left to find
out.  Why can't it be (-1)?  Maybe looking at the source for the hash()
builtin would yield a clue, or maybe someone who knows would be able to
tell us?

-- 
Arnaud



More information about the Python-list mailing list