Why are tuples immutable?

Antoon Pardon apardon at forel.vub.ac.be
Thu Dec 23 08:54:33 CET 2004

Op 2004-12-22, Jeff Shannon schreef <jeff at ccvcorp.com>:
> Antoon Pardon wrote:
>>Op 2004-12-21, Jeff Shannon schreef <jeff at ccvcorp.com>:
>>How does the dict know which value is associated with which key? 
>>Because there is a link between the key and the value. The problem
>>with a mutated key in a dictionary is not that the link between the
>>key and the value is severed, but that the key hashes now to a different
>>bucket. But if you just go over the buckets and iterate over the keys
>>within and there associated values, you will encouter your mutated
>>key with its value.
> Except that the hash value *IS* the link between the key and the value.  

No it is not because that would imply that keys with the same hash
would have the same value. The hash is the link between the key
and the dictionary bucket.

> You cannot change the hash value without severing the link.  You cannot 
> trace the link without the original hash value.  You do not have the 
> original hash value when accessing the dict with a mutated key.

You are wrong. Looking up a value in a dictionary is a two stage
process. First a hash is computeted in order to find the hash bucket.
Each bucket is somekind of container with key value pairs. After the
bucket is found a search is done for the pair with the right key.

If the hash of a key is changed this only upsets the first stage,
finding the right bucket. But within one bucket is still that
pair of (now mutated) key and value. And a method like items
will just go over the buckets to collect these pairs.

>>>I need to be able to access sequence-keyed dictionaries with literals, 
>>>which means that the keys need to compare by value, not ID.  Thus, I 
>>>need to have sequences that compare (and hash) by value.  These 
>>>conditions *cannot* be met by a mutable list.
>>Which condition can't be met by a mutable list? The only ones I see
>>above is comparison and hashable by value. A list can be compared
>>and hashed by value.
> A list cannot be hashed by value in such a way that the hash doesn't 
> change when the list mutates.

You didn't list that one and you don't need that condition.

>>>I can have the quality of 
>>>hash value not changing when mutated, or I can have the quality of 
>>>hashing by value, but I *cannot* have both.
>>So? You don't need the first.
> That's an "interesting" assertion.  You have yet to provide any evidence 
> of it, however. 

All you need is that the lists that are used as a key remain stable.
In that case, there hash doesn't change and the directory will have
no problem finding it.

>>>Thus, even if you make 
>>>lists hash by ID, I *still* need to have an immutable tuple type so that 
>>>I can get hash-by-value. 
>>No you don't. The same algorithm that works for hashing tuples will
>>work just as fine for hashing lists.
> Except that the hash value will change when the list mutates, and then I 
> can't access my dictionary values.

Then don't mutate your list. Noone advocated mutating keys in a
dictionary. It's not because I think it could be usefull to use
a mutable as a key, that I think it is usefull to mutate a key.

Antoon Pardon

More information about the Python-list mailing list