hashing mutable instances (was Re: delete duplicates in list)
mwh at python.net
Thu Oct 30 12:55:23 CET 2003
Thomas Heller <theller at python.net> writes:
> Michael Hudson <mwh at python.net> writes:
> > Alex Martelli <aleax at aleax.it> writes:
> >> > Actually the Set in sets module has an average lookup of O(1), worst
> >> > case O(n) (not 100% sure of worst case, but 99% sure). It's been
> >> Hmmm -- could you give an example of that worstcase...? a _full_
> >> hashtable would give such behavior, but Python's dicts always ensure
> >> the underlying hashtables aren't too full...
> > Try inserting a bunch of instances of
> > class C:
> > def __hash__(self): return 0
> > into a dictionary.
> I've though about using something like this in production code
> to be able to store mutable instances in a dict.
> Performance problems aside (since there are only a couple of key/value
> pairs in the dict), is it such a bad idea?
Um, I don't know actually. It pretty much defeats the point of using
a hashtable. If your class has some non-mutable parts it'd be an
idea to hash them, of course.
And the performance problems are severe -- inserting just a thousand
instances of the class C() into a dictionary takes noticable time.
(What *is* a bad idea is giving such classes an __eq__ method that
mutates the dict being inserted into -- I found a bunch of such bugs a
couple years back and I think it's still possible to core Python (via
stack overflow) by being even more devious).
Our Constitution never promised us a good or efficient government,
just a representative one. And that's what we got.
More information about the Python-list