Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Hashability?

Reply
Thread Tools

Hashability?

 
 
Chris S.
Guest
Posts: n/a
 
      07-19-2004
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.
 
Reply With Quote
 
 
 
 
Fernando Perez
Guest
Posts: n/a
 
      07-19-2004
Chris S. wrote:

> 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
 
Reply With Quote
 
 
 
 
Tim Daneliuk
Guest
Posts: n/a
 
      07-19-2004
Chris S. wrote:

> 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?

--
----------------------------------------------------------------------------
Tim Daneliuk http://www.velocityreviews.com/forums/(E-Mail Removed)
PGP Key: http://www.tundraware.com/PGP/
 
Reply With Quote
 
Dan Bishop
Guest
Posts: n/a
 
      07-19-2004
"Chris S." <(E-Mail Removed)> wrote in message news:<cdfd0p$ls9$(E-Mail Removed)>...
> 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.

>>> x = object()
>>> hash(x)

1075889080
>>> id(x)

1075889080
>>> {x: 0}

{<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.
 
Reply With Quote
 
James Henderson
Guest
Posts: n/a
 
      07-19-2004
On Monday 19 July 2004 3:50 am, Chris S. wrote:
> 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/re...omization.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.

>>> class MyList(list):

.... 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
--
James Henderson, Logical Progression Ltd
http://www.logicalprogression.net
http://mailmanager.sourceforge.net

 
Reply With Quote
 
Chris S.
Guest
Posts: n/a
 
      07-19-2004
Chris S. wrote:

> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments