> I have found many cases where my python code would have been simpler and easier if I could use arbitrary objects as keys

You can use pretty much anything as a dictionary key

That's really not true[1]. You can only use hashable types, which excludes dicts, lists and sets.

For example (tested on both python 2.7 and 3.4):

    >>> {{'a': 1}: 2}
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'dict'
    >>> {[1,2,3]: 4}
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'list'
    >>> {{1,2,3}: 4}
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'set'

Objects inheriting from object are hashable by default, but the hash is based on the objects instance such that each instance will return a unique value for that instance:

    >>> class A(object):
    ...     def __init__(self):
    ...         self.x = 1
    ...
    >>> a = A()
    >>> b = A()
    >>> d = {a: 1, b: 2}
    >>> a.x = 10
    >>> b.x = 10
    >>> d[a]
    1
    >>> d[b]
    2

While this makes sense for the instance stored in the dict (because mutability would otherwise mean that they key changes values), I don't think this is particularly useful. I rarely look up dicts by instance, but rather by value. That is, I would construct another object with the same attributes and look up by that.

You can, of course, implement your own __hash__ to make it work, but you have to do it manually for any object you want it and most third-party objects won't have implemented it so you'd have to monkey patch them.

Contrast that with Clojure, where all built-in data structures (maps, sets, lists, dicts etc) work as keys out of the box.

[1] I guess its true in the sense that you can implement __hash__ to make it work. But its not particularly easy or idiomatic.