I found that the following are all valid:
>>> d = {}
>>> d[None] = 'foo'
>>> d[(1, 3)] = 'baz'
Even a module can be used as a dict key:
>>> import sys
>>> d[sys] = 'bar'
However, a list cannot, and neither can a tuple that contains a list:
>>> d[[2]] = 'spam'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> d[(1, [3])] = 'qux'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
Why does storing a list inside the tuple mean it can't be a dict key any more? After all, I could just as easily "hide" a list inside a module (and indeed, e.g. sys.path is a list already).
I had some vague idea that that the key has to be "hashable" but I don't have a detailed understanding of what this means, or why there is such a limitation. What would go wrong if Python allowed using lists as keys, say, using their memory location as the hash?
There's a good article on the topic in the Python wiki: Why Lists Can't Be Dictionary Keys. As explained there:
What would go wrong if Python allowed using lists as keys, say, using their memory location as the hash?
It would cause some unexpected behavior. Lists are generally treated as if their value was derived from their content's values, for instance when checking (in-)equality. Many would - understandably - expect that you can use any list [1, 2] to get the same key, where you'd have to keep around exactly the same list object. But lookup by value breaks as soon as a list used as a key is modified, and lookup by identity requires keeping track of that exact list object - which isn't an ordinary requirement for working with lists.
Other objects, such as modules and object, make a much bigger deal out of their object identity anyway (when was the last time you had two distinct module objects called sys?), and are compared by that anyway. Therefore, it's less surprising - or even expected - that they, when used as dict keys, compare by identity in that case as well.