CODEWITHSUNDEEP
pythondictionarytuplesimmutability
Qiong Liu
Qiong Liu

Reputation: 39

Why python allows tuple as key for dictionary

tuples in python can have elements of different type. For example:

tup1 = ('physics', 'chemistry', 1997, 2000);
tup2 = (1, 2, 3, 4 );

When used for keys in dictionary, how does python decide the size of key when the element size are varied?

Upvotes: 2

Views: 4195

Answers (3)

Antti Haapala -- Слава Україні
Antti Haapala -- Слава Україні

Reputation: 133889

Python dictionaries need not know the size of the key. Python dictionaries accept any object as a key if it provides the __hash__ and __eq__ special methods. Python finds the matching key by key == another, which internally calls key.__eq__(another). This also means, that you can have one dictionary that has strings, integers, tuples of 1 and 100 elements as keys at the same time.

To speed things up, a dictionary organizes these keys into a hash table, that uses a hash code calculated with hash(key) to divide keys; internally hash(key) calls key.__hash__(); a hash code is a simple integer that satisfies two rules:

  1. it must be that hash(key) == hash(another) if key == another
  2. the hash key should be chosen so that if key != another then preferably (but not in every case) hash(key) != hash(another)

In addition in Python hash(x) must be constant to the lifetime of x, which means that the equality of x with regards to other objects must not change either.

A tuple has both __eq__ and __hash__:

>>> t = ('physics', 'chemistry', 1997, 2000)
>>> hash(t)
1710411284653490310
>>> u = ('physics', 'chemistry', 1997, 2000) # another tuple
>>> t is u  # they are not the same object
False
>>> hash(t) == hash(u)
True
>>> t == u
True

Now, Python need not even use the hash code at all to find an object in a dictionary, all it would need is to find an element with matching key, comparing each and every to the given key with ==. But this would mean that on a dictionary having n keys, on average n / 2 comparisons would have to be made to find a key. With the hashing trick we can narrow the set of keys to compare to ideally always 1 or handful at maximum, thus a lookup in dictionary should be equally fast were it small or large.

Now, unlike a tuple, a list in Python is a mutable value, and for it it is impossible to provide a unchanging hash code that would also in future satisfy the 2 rules given above. Thus Python does not define it at all:

>>> [].__hash__ is None
True

likewise you get an exception if using it as a dictionary key:

>>> {[]: 42}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Upvotes: 6

NPE
NPE

Reputation: 500257

how does python decide the size of key when the element size are varied?

The simple answer is that it doesn't: Python allows dictionaries with heterogenous keys. This is much broader than different-sized tuples:

In [15]: d = {}

In [16]: d[42] = 'foo'

In [17]: d['bar'] = -1

In [18]: d[(1, 2, 3)] = {}

In [19]: d
Out[19]: {42: 'foo', 'bar': -1, (1, 2, 3): {}}

Any hashable object, irrespective of its type, can be used as a key into any dictionary.

Upvotes: 5

Aswin Murugesh
Aswin Murugesh

Reputation: 11070

The size of the key does not matter for a dictionary.

Dictionary keys must be immutable. Since a tuple is immutable, you can use a tuple as a key to a dict.

Source

Upvotes: 1

Related Questions