Mutable objects which define __hash__ (was Re: Why are tuples immutable?)

[Nick Coghlan]

Steven Bethard wrote:
> Of course, if rehash worked in place, you could probably do some 
> optimizations to only rehash the necessary items.

Yep, especially given this little critter from dictobject.h which contains 
everything needed to spot mutated objects:

typedef struct {
	long me_hash;      /* cached hash code of me_key */
	PyObject *me_key;
	PyObject *me_value;
} PyDictEntry;

So the major downside to giving standard mutable objects hash methods is that 
dictionaries then suffer from the 'mutation without resorting' problem that 
sorted lists can currently suffer from.

As I said to Antoon, I no longer have any theoretical objection to the idea of 
mutable objects with a variable hash. I do, however, have a practical objection 
- mutating a dict's keys without calling rehash() could lead to some extremely 
subtle bugs that the interpreter can't really help identify. It just seems far 
too easy to inadvertently burn yourself by altering an object that is being used 
as a dictionary key.

What I'd prefer to see is a collections.id_dict (and a corresponding 
collections.id_set) - identity based versions of the standard classes, useful 
when classifying mutable objects. The id_dict would be handy when you want to 
associate additional information with a mutable object without altering the 
object (e.g. analysing a graph, and recording extra information about each of 
the nodes).

For mutable objects, value-based keying doesn't really make sense (as the value 
may change with time), but identity-based keying is entirely straightforward, 
and including ID-based dicts and sets would go a long way to providing OOWTDI. 
And the performance should leave the Python-based versions for dead. They should 
actually be slightly faster than the standard dict() and set(), since they don't 
have to deal with user-overridable special methods :)

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://boredomandlaziness.skystorm.net