hashkey/digest for a complex object

[kj]

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

>Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:

>> On Sat, 09 Oct 2010 21:39:51 +0100, Arnaud Delobelle wrote:
>>
>>> 1. hash() is an idempotent function, i.e. hash(hash(x)) == hash(x) hold
>>> for any hashable x (this is a simple consequence of the fact that
>>> hash(x) == x for any int x (by 'int' I mean 2.X int)).
>>
>> It's a beautiful theory, but, alas, it is not the case.
>>
>>>>> hash(-1) == -1
>> False
>>>>> hash(2**64) == 2**64
>> False
>>
>> to give only two of an infinite number of counter-examples.

(Infinite???)

>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.

>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.

~kj