hashkey/digest for a complex object

[Arnaud Delobelle]

[...]

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.

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?

 

[Hrvoje Niksic]

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

Because -1 has a special meaning in the C function equivalent to
Python's hash(). PyObject_Hash returning -1 means that an exception was
raised somewhere inside the object's __hash__ method. For that reason
hash functions that really return -1 must change that to another value,
and -2 is as good a replacement as any.

This is documented in
http://docs.python.org/c-api/object.html?highlight=pyobject_hash#PyObject_Hash

 

[kj]

Reading the source code is also a good approach.

Every time I have attempted to answer a question by looking at the
Python C source, all I've achieved was wasting time, sometimes a
*lot* of time, so by now I've developed what can only be described
as a phobia to it. I probably need professional help at this point.

~kj