Why can I not use a list as a dictionary key?

Question

Why can I not use a list as a dictionary key?

hlst is a list. memo is a dict.

if not hlst in memo:
    # do something
else:
    configurations = memo[hlst]

When I try it python tells me that hlist is unhashable.

Answer 1

Your problem is lack of undesrtanding of "hashable" concept.

We call object "hashable", if you are able to calculate hashcode for it.

Hashcode (a.k.a. hash function) is function that takes objects and returns some value that USUALLY should be enough to differentiate it from other object. It means, that hashcode to some point should be usable as ID. Of course, there will be so called "hash conflicts" (when two objects have the same hashcode), because there is way more possible objects than hashcodes.

More important (than "different objects have different hashcodes") constraint on hashing function (function that is used to get haschode for object) is that it should be the same through the whole lifecycle of object.

Look: we have object a, which have attributes/properties x and y. For hashing function to work properly you need to be sure, that hash of a will NOT depend on x and y.

Lists have hashcode dependent on its values hashcodes, so they themselves are unhashable. Why? Because if you change one element of list (or add one, or remove, etc), its hashcode changes (because it depends on this element).

Now, back to dictionary. Dictionary is a hash table, which can be described as "simple in-memory array of pairs, that under index (X modulo (array size)) has value, which first item has hashode X" (it is quite a simplification, but main concept sticks through languages and implementations; first value of pair is called "key", and second "value", or "item"). If you want to insert list [A, B] with hashcode 1234 and value V to hash table of size 10, and then you change value of this list to [A, C] (which means change of haschode to 5678), then at the moment of insertion pair ([A, B], V) will go at index 1234 modulo 10 = 4, but after change it should be at index 5678 modulo 10 = 8.

To make it work properly, we would need to inform hash table every time key object changes (which is ugly, hard to implement, and eats a lot of resources), or be sure that key's hashcode won't change as long, as it is in hash table. Python creators chose second option, as it is widely used, proved to work well and be stable.

This is one of reasons why python has two ordered collection types - lists and tuples. As you probably know, tuples are immutable, so its hashcode shoudln't change - ergo, it may be used as dictionary keys.

PS. Text above is quite a simplification. Dependency of lists hashcode on its elements is kinda tricky. Also, implementation of dictionary as hashmap is not defined in language reference - it says only that keys should be hashable, doesn't explain why. It is possible for some implementations to work well with unhashable objects, but to force hashable keys obly for compliance with reference.

Answer 2

You cannot use a list as a key because lists are mutable. Since they are mutable, they cannot be hashable (like strings and tuples) are. Suppose hlist = ['a']. Think what would happen if you changed the contents of hlist to ['b']. What would memo[['a']] return?

To overcome this, you can turn your list into a tuple tuple(hlist), as per darkryder's comment.