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 perfectly.
You just need to DYFR ;-)
I really do like this acronym :)
Cheers, Nick.
--
Nick Coghlan | [EMAIL PROTECTED] | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net
--
http://mail.python.org/mailman/listinfo/python-list
