Are user-defined objects good keys?

Tim Hochberg tim.hochberg at ieee.org
Sun Sep 30 05:11:27 CEST 2001


Speaking from total ignorance in the hope that some other Tim, will correct
my mistakes.

[SNIP]
> Let inst be an instance, and let n be an integer.  In my python
> installation, the following are true:
>
> A.    hash(n) == n
> B.    hash(inst) == hash(id(inst))
>
> Regarding A: Is hash() used to create hash indices for dictionaries?  If
> so, is the identity function a good hash function for integer keys?

Yes. It depends.

More verbosely, I believe that it depends which integers end up being used
as keys. I believe that in practice that the integers used as keys tend to
be dense (most of the keys between the minimum and maximum key values are
filled in) in which case hash(n) is a good choice. On the other hand if the
integers are every N, where N is the number of hash slots, it will be very
bad since all of the keys end up in one slot. Anyway, the main point is that
there is no optimal solution unless you know what integers will be used and
the current scheme works well in practice.

> Regarding B: Is B true for all python implementations?  If not, then is it
> true that
>
> C.    hash(inst) == fn(id(inst))
>
> for *some* function fn()?  If either B or C is true, then most
user-defined
> mutable instances can be used as dictionary keys.  (I say "most" because
> most user-defined mutable instances will not redefine __cmp__.)
>
> My central question is: Can I use user-defined mutable instances (that are
> "==" iff their ids are equal) as dictionary keys?  On my system I can.
> What about others?

I can't give any details, but you can rely on instances being useful as
dictionary keys unless you do something screwy (where doing something screwy
means redefining cmp, eq or hash in the 'wrong' way for some definition of
wrong). It says some stuff about this at
http://www.python.org/doc/current/ref/customization.html.

-tim





More information about the Python-list mailing list