Hashability?

[Chris S.]

Perhaps this is obvious to some, but why are dictionary keys constrained
to hashable objects? why not use the object's id for the hash value.
Wouldn't this allow typically non-hashable objects to be used as keys?
I've done this in several instances and I've never encountered a problem.

 

[Fernando Perez]

Perhaps this is obvious to some, but why are dictionary keys constrained
to hashable objects? why not use the object's id for the hash value.
Wouldn't this allow typically non-hashable objects to be used as keys?
I've done this in several instances and I've never encountered a problem.

Bad idea: objects which compare to equality may have different ids

In [1]: a=(1,2,3)

In [2]: b=(1,2,3)

In [3]: a is b
Out[3]: 0

Also, if you pickle such a dict and later restore it, all keys now hold bogus
memory addresses of non-existent stuff.

What you suggest may work in limited, highly constrained situations. Not a good
idea for a general purpose tool like dicts.

Cheers,

f

 

[Tim Daneliuk]

Perhaps this is obvious to some, but why are dictionary keys constrained
to hashable objects? why not use the object's id for the hash value.
Wouldn't this allow typically non-hashable objects to be used as keys?
I've done this in several instances and I've never encountered a problem.

I am interested in the answer to this as well, but it seems to me that
the objid _is_ itself a hashable item, hence it works... right?

 

[Dan Bishop]

Perhaps this is obvious to some, but why are dictionary keys constrained
to hashable objects?

Because dictionaries are implemented as hash tables. But that's not
helpful, because your real question is "Why were lists and
dictionaries made unhashable?"

Well, what do you expect their hash value to be? It can't be based on
their contents, because those can change. It can't be based on object
ID, either, because different (in id) lists can be equal (in
contents), and that violates the principle that x == y implies hash(x)
== hash(y).

I suppose the hash code of a mutable type could be defined as always
zero, which would be consistent, but horrible in terms of efficiency.

So the only reasonable thing to do is make these types non-hashable.

why not use the object's id for the hash value.

That *is* done by default.
{<object object at 0x4020c3b8>: 0}

This is acceptable because the default implementation of the "=="
operator is the same as the "is" operator, so x == y implies id(x) ==
id(y) implies hash(x) == hash(y), so it's a consistent hash function.

 

[James Henderson]

Perhaps this is obvious to some, but why are dictionary keys constrained
to hashable objects?

I'm not sure exactly what you mean here. My definition of a "hashable object"
would be one that can serve as a dictionary key. This is basically all
classes whose instances, when they compare equal, have the same hash value.

why not use the object's id for the hash value.
Wouldn't this allow typically non-hashable objects to be used as keys?
I've done this in several instances and I've never encountered a problem.

By default user-defined class do use their ID as their hash value and this is
fine because by default instances of user-defined classes do not compare
equal. If you go and define a __cmp__() method for your class and there is a
danger of instances comparing equal then you need to define the __hash__()
method too. See the sections on __cmp__() and __hash__() in:

http://www.python.org/doc/current/ref/customization.html

Note that Python doesn't even stop you using an immutable type (say a subclass
of the built-in list type) as a dictionary key if you give it a __hash__()
method. See the following very bad code.
.... def __hash__(self): return 1
....

l1 = MyList(range(10))
l1 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
l2 = MyList(range(10, 20))
d = {l1: 1, l2: 2}
d

{[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]: 1, [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]:
2}

James

 

[Chris S.]

Perhaps this is obvious to some, but why are dictionary keys constrained
to hashable objects? why not use the object's id for the hash value.
Wouldn't this allow typically non-hashable objects to be used as keys?
I've done this in several instances and I've never encountered a problem.

I understand the issue now. My thanks to everyone who responded.