Re: Mutable objects which define __hash__ (was Re: Why are tuples immutable?)
From: Nick Coghlan (ncoghlan_at_iinet.net.au)
Date: Sun, 26 Dec 2004 12:17:42 +1000 To: Python List <email@example.com>
Bengt Richter wrote:
> I take it you are referring to regular python dictionaries,
Correct. So I'll skip over the sections talking about alternate lookup
strategies in my reply.
>>Anyway, what are the consequences of a type which has a 'variable hash'?
>>The only real bad consequence is that the internal state of a dictionary can
>>break if someone alters the hash of one of its keys. The restriction to
>>'constant hashes' is aimed squarely at eliminating this class of programming
>>errors. It doesn't actually provide any performance gain.
> Why not? It means you only have to compute the hash for any given object once,
> and you can cache the hash value. That could be a biggie if you had megabyte trees
> of nested tuples as keys and reused them frequently for lookup.
Allowing mutation doesn't mean abandoning your caching - it just means you need
a way to tell the dict to update it's key cache (i.e. rehash())
> I think, for one thing, it would be more efficient to notice that some keys were guaranteed not
> to need rehashing... um, maybe by paritioning the key set into immutables and mutables ;-)
True, since otherwise rehash() would have to check every key, even the immutable
ones. However, that only affects the time required for a rehash(), rather than
general dictionary operation.
> For another, it's not just a matter of "moving" keys that hash "incorrectly". If keys that
> are a part of the state of the dict can mutate outside of dict methods, then keys can mutate
> to equal each other, and "rehashing" will give equal hashes for previously unequal and distinct keys,
> and you must choose which of the previous values is to be the value for the two keys that have now
> become one by equality (however __eq__, __cmp__, __coerce__ and inheritance may define equality).
Or resist the temptation to guess, and have rehash() raise an exception :)
> OTOH, if KeyError is frequent because of mutation, hashing may be next to useless overhead. IOW, DYFR ;-)
Indeed. I defined my FR based on Antoon's analogy of the sorted list - have the
dict behave like sorted list, so that if you screw the invariant, it's the
programmer's job to tell the dictionary to fix it.
>>>The problem is also that you really can't make new immutable objects
> I don't understand that one. What do you mean by "new immutable object"?
Bad terminology on Antoon's part, I think - I believe he meant "new immutable type".
I gave the Python 2.4's Decimal as an example of something which is
theoretically immutable, but doesn't actually enforce that immutability properly.
Overriding __setattr__ can give true immutability. It just makes the class a
serious pain to write :)
> That is so different that I don't know how it could be used to debug an app that
> uses a mutable key dict. I think Antoon was just asking for a key-mutation detector.
> I think that's reasonable goal. A deep copy of all keys defined would permit that,
> at least when dict methods had control. But you couldn't find the code that mutated
> the originals without something outside the dict to catch it in the act.
The identity keyed dict was based on Antoon's posted use case: he wanted to
classify mutable objects, and then check for membership in those groups.
You can use lists for this, but the lookup is slow. Conventional dictionaries
and sets give a fast lookup, but require that the items in use be hashable.
An identity dictionary (or set) solves the 'object classification' problem
> You just need to DYFR ;-)
I really do like this acronym :)
-- Nick Coghlan | firstname.lastname@example.org | Brisbane, Australia --------------------------------------------------------------- http://boredomandlaziness.skystorm.net