Why are tuples immutable?

Jeff Shannon jeff at ccvcorp.com
Fri Dec 17 01:11:56 CET 2004


Adam DePrince wrote:

>And how exactly do you propose to mutate an object without changing its
>hash value?
>
>
>* Create this mutate-able object type.  
>* Create two objects that are different with different hash values.
>* Mutate one so that it is the same as the other.
>* Compare their hash values.  
>
>If the hash values are the same, you lose because you didn't keep your
>original promise.
>
>If the hash values are different then you just broke your object because
>two objects with the same value must have the same hash value, but yours
>are different.
>  
>

Correct me if I'm wrong, here, but I believe that what you're saying 
here (and my vague memories of the little bit that I've read about 
hashes) is that, for a well-behaved hash function, then A == B should 
imply that hash(A) == hash(B).  (The reverse is *not* true, however -- 
hash(A) == hash(B) does not necessarily say anything about whether A == B.)

If that is a correct condition for a well-behaved hash function, then it 
is indeed impossible to have a well-behaved hash function that can be 
useful in the face of object mutation.  For something like a list, one 
can only define a poorly-behaved hash-like function.

To take another approach -- given some function that allows lists to 
(pretend to be) hashable:

.>>> key = [1,2]
.>>> d[key] = 'foo'
.>>> d[[1,2]]
????
.>>> key.append(3)
.>>> d[key]
???
.>>>

As I understand it, it is impossible for there to be a hash function for 
which both of these cases can return the same object.  For most uses of 
dicts, it is necessary that the first case be valid -- a dict isn't 
going to be very useful to me if I have to pass around all of the 
objects used as keys in order to access it. Equality-based hashes are 
necessary, so the second case must then be disallowed.

But isn't it a bit nonsensical that, without ever rebinding key, one can 
do something like

.>>> d[key] = 'foo'
.>>> frombulate(key)
.>>> d[key]
Traceback (most recent call last):
  File "<interactive input>", line 1, in ?
KeyError: key
.>>>

In order to maintain the logical consistency that if an object is used 
as a dict key, that same object should reasonably be expected to 
retrieve the same value, identity-based hashes are necessary.  As a 
result, the first option must be disallowed.

In either case, if it's ever possible for equality to change while 
identity doesn't, then somewhere along the lines one of the core 
requirements, the contract if you will, of a dictionary *must* be 
broken.  And while it may be possible to get away with breaking that 
contract some of the time (by postulating, for example, that if one 
mutates a dict key then things will break), this will result in more 
bugs and more confusion over time.  There is no way for Python to be 
able to behave consistently in the face of mutable dict keys, therefore 
("In the face of ambiguity, refuse the temptation to guess.") Python 
declines the temptation of making it trivial to use mutable objects as 
dict keys.

Jeff Shannon
Technician/Programmer
Credit International






More information about the Python-list mailing list