CODEWITHSUNDEEP
pythonlistdictionary
jkarimi
jkarimi

Reputation: 1267

dictionary keys: custom objects vs lists

I have read that lists cannot be dictionary keys because mutable objects cannot be hashed. However, custom objects appear to be mutable as well:

# custom object
class Vertex(object):
    def __init__(self, key):
        self.key = key

v = Vertex(1)
v.color = 'grey' # this line suggests the custom object is mutable

But, unlike lists, they can be used as dictionary keys; why is this? Couldn't we simply hash some sort of id (such as the address of the object in memory) in both cases?

Upvotes: 3

Views: 335

Answers (1)

jkarimi
jkarimi

Reputation: 1267

as noted in Why Lists can't be Dictionary Keys:

Lists as Dictionary Keys

That said, the simple answer to why lists cannot be used as dictionary keys is that lists do not provide a valid hash method. Of course, the obvious question is, "Why not?"

Consider what kinds of hash functions could be provided for lists.

If lists hashed by id, this would certainly be valid given Python's definition of a hash function -- lists with different hash values would have different ids. But lists are containers, and most other operations on them deal with them as such. So hashing lists by their id instead would produce unexpected behavior such as:

  1. Looking up different lists with the same contents would produce different results, even though comparing lists with the same contents would indicate them as equivalent.

  2. Using a list literal in a dictionary lookup would be pointless -- it would always produce a KeyError.

User Defined Types as Dictionary Keys

What about instances of user defined types?

By default, all user defined types are usable as dictionary keys with hash(object) defaulting to id(object), and cmp(object1, object2) defaulting to cmp(id(object1), id(object2)). This same suggestion was discussed above for lists and found unsatisfactory. Why are user defined types different?

  1. In the cases where an object must be placed in a mapping, object identity is often much more important than object contents.

  2. In the cases where object content really is important, the default settings can be redefined by overridding __hash__ and __cmp__ or __eq__.

Note that it is often better practice, when an object is to be associated with a value, to simply assign that value as one of the object's attributes.

Upvotes: 5

Related Questions