Re: Why are tuples immutable?

Discussion in 'Python' started by Nick Coghlan, Dec 18, 2004.

  1. Nick Coghlan

    Nick Coghlan Guest

    Jp Calderone wrote:
    > On Fri, 17 Dec 2004 11:21:25 -0800, Jeff Shannon <> wrote:
    >
    > The correct characterization is that Python makes user-defined
    > mutable classes hashable (arguably correctly so) as the default
    > behavior.


    However, that is only achieved by using identity based equality by default. If
    you inherit from something which *doesn't* use identity based equality (say,
    list or dict), then the hashability isn't there. So while you're quite correct,
    it doesn't affect the OP's original complaint (not being allowed to use a list
    as a dictionary key).

    The Python docs are pretty precise about what the rules are:

    "__hash__(self)
    Called for the key object for dictionary operations, and by the built-in
    function hash(). Should return a 32-bit integer usable as a hash value for
    dictionary operations. The only required property is that objects which compare
    equal have the same hash value; it is advised to somehow mix together (e.g.,
    using exclusive or) the hash values for the components of the object that also
    play a part in comparison of objects. If a class does not define a __cmp__()
    method it should not define a __hash__() operation either; if it defines
    __cmp__() or __eq__() but not __hash__(), its instances will not be usable as
    dictionary keys. If a class defines mutable objects and implements a __cmp__()
    or __eq__() method, it should not implement __hash__(), since the dictionary
    implementation requires that a key's hash value is immutable (if the object's
    hash value changes, it will be in the wrong hash bucket)."

    (from: http://www.python.org/dev/doc/devel/ref/customization.html)


    The key points are:
    1. Objects which compare equal must have the same hash value
    2. An object's hash value must never change during it's lifetime

    Lists could achieve the former, but not the latter. Tuples can achieve both, by
    virtue of being immutable, with immutable contents. Ditto for sets & frozensets.

    If you want to 'freeze' a mutable object for use as a key, the class below
    forces the use of object identity for keying purposes. As I'm sure Jeff would be
    quick to point out, the downside is that keying by different objects with the
    same value *does not work* if their identities are different (or rather, it does
    work - they just get new entries in the dictionary). However, whether that
    actually matters is going to be application dependent.

    Py> class KeyByIdentity(object):
    .... __slots__ = ["_obj", "_hash_value", "__hash__", "__cmp__"]
    .... def __new__(cls, obj):
    .... self = object.__new__(cls)
    .... self._obj = obj
    .... self._hash_value = id(obj)
    .... return self
    .... def __hash__(self):
    .... return self._hash_value
    .... def __cmp__(self, other):
    .... return cmp(self._hash_value, other._hash_value)
    ....
    Py> d = {}
    Py> key_list = []
    Py> key_dict = {}
    Py> d[KeyByIdentity(key_list)] = "Keyed by a list"
    Py> d[KeyByIdentity(key_dict)] = "Keyed by a dict"
    Py> print "\n".join([str(x._obj) + ": " + str(y) for x, y in d.items()])
    []: Keyed by a list
    {}: Keyed by a dict
    Py> key_list.append(3)
    Py> key_dict["A"] = 3
    Py> print "\n".join([str(x._obj) + ": " + str(y) for x, y in d.items()])
    [3]: Keyed by a list
    {'A': 3}: Keyed by a dict
    Py> key_with_same_id = key_list
    Py> d[KeyByIdentity(key_with_same_id)]
    'Keyed by a list'
    Py> key_with_new_id = list(key_list)
    Py> d[KeyByIdentity(key_with_new_id)]
    Traceback (most recent call last):
    File "<stdin>", line 1, in ?
    KeyError: <__main__.KeyByIdentity object at 0x009DA418>

    It would also be trivial to inherit from dict to make an "IdentityDict" which
    automatically used KeyByIdentity on its elements (using id() directly would be
    dangerous, as the dictionary then has no reference keeping the original object
    alive, thus failing to ensure the uniqueness of the keys - since id() only
    guarantees uniqueness with respect to currently existing objects).

    Cheers,
    Nick.

    --
    Nick Coghlan | | Brisbane, Australia
    ---------------------------------------------------------------
    http://boredomandlaziness.skystorm.net
    Nick Coghlan, Dec 18, 2004
    #1
    1. Advertising

  2. Nick Coghlan

    Roy Smith Guest

    Nick Coghlan <> wrote:
    [quoting from the Reference Manual]
    > If a class defines mutable objects and implements a __cmp__()
    > or __eq__() method, it should not implement __hash__(), since the dictionary
    > implementation requires that a key's hash value is immutable (if the object's
    > hash value changes, it will be in the wrong hash bucket)."


    I know that's what it says, but I don't think it's good advice. All
    that is really required is that __hash__() always returns the same value
    over the lifetime of the object, and that objects which __cmp__() the
    same always return the same hash value. That's it. That's all a
    dictionary cares about.

    Making the object immutable is certainly the easiest way to achieve that
    goal, but it's not the only way.
    Roy Smith, Dec 18, 2004
    #2
    1. Advertising

  3. Op 2004-12-18, Nick Coghlan schreef <>:
    > Jp Calderone wrote:
    >> On Fri, 17 Dec 2004 11:21:25 -0800, Jeff Shannon <> wrote:
    >>
    >> The correct characterization is that Python makes user-defined
    >> mutable classes hashable (arguably correctly so) as the default
    >> behavior.

    >
    > However, that is only achieved by using identity based equality by default. If
    > you inherit from something which *doesn't* use identity based equality (say,
    > list or dict), then the hashability isn't there. So while you're quite correct,
    > it doesn't affect the OP's original complaint (not being allowed to use a list
    > as a dictionary key).
    >
    > The Python docs are pretty precise about what the rules are:
    >
    > "__hash__(self)
    > Called for the key object for dictionary operations, and by the built-in
    > function hash(). Should return a 32-bit integer usable as a hash value for
    > dictionary operations. The only required property is that objects which compare
    > equal have the same hash value; it is advised to somehow mix together (e.g.,
    > using exclusive or) the hash values for the components of the object that also
    > play a part in comparison of objects. If a class does not define a __cmp__()
    > method it should not define a __hash__() operation either; if it defines
    > __cmp__() or __eq__() but not __hash__(), its instances will not be usable as
    > dictionary keys. If a class defines mutable objects and implements a __cmp__()
    > or __eq__() method, it should not implement __hash__(), since the dictionary
    > implementation requires that a key's hash value is immutable (if the object's
    > hash value changes, it will be in the wrong hash bucket)."
    >
    > (from: http://www.python.org/dev/doc/devel/ref/customization.html)
    >
    >
    > The key points are:
    > 1. Objects which compare equal must have the same hash value
    > 2. An object's hash value must never change during it's lifetime
    >
    > Lists could achieve the former, but not the latter. Tuples can achieve both, by
    > virtue of being immutable, with immutable contents. Ditto for sets & frozensets.


    Yes they can. If you don't mutate a list it will never change during
    it's lifetime.

    --
    Antoon Pardon
    Antoon Pardon, Dec 21, 2004
    #3
  4. Op 2004-12-18, Roy Smith schreef <>:
    > Nick Coghlan <> wrote:
    > [quoting from the Reference Manual]
    >> If a class defines mutable objects and implements a __cmp__()
    >> or __eq__() method, it should not implement __hash__(), since the dictionary
    >> implementation requires that a key's hash value is immutable (if the object's
    >> hash value changes, it will be in the wrong hash bucket)."

    >
    > I know that's what it says, but I don't think it's good advice. All
    > that is really required is that __hash__() always returns the same value
    > over the lifetime of the object, and that objects which __cmp__() the
    > same always return the same hash value. That's it. That's all a
    > dictionary cares about.


    It cares about even less. It only cares that these conditions are
    met while the object is a key. If those things would change before
    or after the object is a key, the dictionary wouldn't care about
    it.

    --
    Antoon Pardon
    Antoon Pardon, Dec 21, 2004
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Steve Holden

    Why are tuples immutable?

    Steve Holden, Dec 13, 2004, in forum: Python
    Replies:
    3
    Views:
    323
    Steven Bethard
    Dec 17, 2004
  2. Fredrik Lundh

    Re: Why are tuples immutable?

    Fredrik Lundh, Dec 13, 2004, in forum: Python
    Replies:
    68
    Views:
    1,101
    Antoon Pardon
    Dec 31, 2004
  3. Jp Calderone

    Re: Why are tuples immutable?

    Jp Calderone, Dec 15, 2004, in forum: Python
    Replies:
    1
    Views:
    293
    Roy Smith
    Dec 15, 2004
  4. Mr. SweatyFinger
    Replies:
    2
    Views:
    1,763
    Smokey Grindel
    Dec 2, 2006
  5. Jon Reyes
    Replies:
    18
    Views:
    219
    Mitya Sirenef
    Feb 19, 2013
Loading...

Share This Page