Why does id({}) == id({}) and id([]) == id([]) in CPython?

Question

Why does CPython (no clue about other Python implementations) have the following behavior?

tuple1 = ()
tuple2 = ()                                                                                                   
dict1 = {}
dict2 = {}
list1 = []
list2 = []
# makes sense, tuples are immutable
assert(id(tuple1) == id(tuple2))
# also makes sense dicts are mutable
assert(id(dict1) != id(dict2))
# lists are mutable too
assert(id(list1) != id(list2))
assert(id(()) == id(()))
# why no assertion error on this?
assert(id({}) == id({}))
# or this?
assert(id([]) == id([]))

I have a few ideas why it may, but can't find a concrete reason why.

EDIT

To further prove Glenn's and Thomas' point:

[1] id([])
4330909912
[2] x = []
[3] id(x)
4330909912
[4] id([])
4334243440

Answer 1

CPython is garbage collecting objects as soon as they go out of scope, so the second [] is created after the first [] is collected. So, most of the time it ends up in the same memory location.

This shows what's happening very clearly (the output is likely to be different in other implementations of Python):

class A(object):
    def __init__(self): print "a",
    def __del__(self): print "b",

# a a b b False
print A() is A()
# a b a b True
print id(A()) == id(A())

Answer 2

When you call id({}), Python creates a dict and passes it to the id function. The id function takes its id (its memory location), and throws away the dict. The dict is destroyed. When you do it twice in quick succession (without any other dicts being created in the mean time), the dict Python creates the second time happens to use the same block of memory as the first time. (CPython's memory allocator makes that a lot more likely than it sounds.) Since (in CPython) id uses the memory location as the object id, the id of the two objects is the same. This obviously doesn't happen if you assign the dict to a variable and then get its id(), because the dicts are alive at the same time, so their id has to be different.

Mutability does not directly come into play, but code objects caching tuples and strings do. In the same code object (function or class body or module body) the same literals (integers, strings and certain tuples) will be re-used. Mutable objects can never be re-used, they're always created at runtime.

In short, an object's id is only unique for the lifetime of the object. After the object is destroyed, or before it is created, something else can have the same id.

Answer 3

it doesn't work the same way in Jython...

>>> id({})
1
>>> id([])
2

Could there be an optimization going on where commonly used (i.e. empty) containers are "interned" to save on allocation costs?

This (in CPython) suggests not:

>>> def mutateid(obj):
...   obj.append('x')
...   print obj
...   print id(obj)
... 
>>> mutateid([])
['x']
4299590472
>>> id([])
4299590472
>>> 

Answer 4

The == operator on lists and dicts do not compare the object IDs to see if they the same object - use obj1 is obj2 for that.

Instead the == operator compares the members of the list of dict to see if they are the same.