tuple.__hash__()

[Thomas Guettler]

Hi!

Can someone point me to the documentation
of tuples __hash__ method?

I want to unique a list of tuples. Since
__hash__ returns a 32 bit integer, there
could be a situtation where two different tupples
return the same value.
-821448277

Is there a dictionary type which uses __cmp__() like
btrees in the standard library?

thomas

 

[Just]

Can someone point me to the documentation
of tuples __hash__ method?

I want to unique a list of tuples. Since
__hash__ returns a 32 bit integer, there
could be a situtation where two different tupples
return the same value.

That's a basic propery of hashing in general, no?

-821448277

Not sure what your point is here: you're showing that two _equal_ tuples
have the same hash value.

Is there a dictionary type which uses __cmp__() like
btrees in the standard library?

I don't think so.

Just

 

[Mike C. Fletcher]

That's a basic propery of hashing in general, no?

Yes, but the OP is probably worried about whether the dictionary class
can differentiate between objects which hash equal and equal objects:
.... def __hash__( self ):
.... return 32
....

>>> a = x()
>>> b = x()
>>> d = {}
>>> d[a] = 1
>>> d = 1
>>> d

>>> class y:

.... def __hash__( self ):
.... return 32
.... def __eq__( self, other ):
.... if isinstance( other, self.__class__):
.... return 1
.... return 0
....

>>> s = y()
>>> t = y()
>>> d = {}
>>> d = 1
>>> d[t] = 1
>>> d

>>>

AFAIK, the dictionary class simply uses the hash to sort into buckets,
providing fast indexing, before using equality to check whether the two
keys are equal. IOW, hashes are an optimisation for lookup, not an
identity as far as the dictionary is concerned, so the impact of
key-collisions is pretty low. The type must guarantee that equal values
hash equal, but it doesn't have to guarantee that only equal values hash
equal.

I don't think so.

Hmm, not in the same way (i.e. not for a binary-search lookup), but
there does appear to be something going on in the dictionary class that
does what the OP is probably looking for wrt comparisons.

Happy hashing,
Mike

_______________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://members.rogers.com/mcfletch/

 

[Peter Otten]

I want to unique a list of tuples. Since
__hash__ returns a 32 bit integer, there
could be a situtation where two different tupples
return the same value.

Maybe you can decorate/uniquify/undecorate?

items = [t1, t2, t1, t1]
di = [(id(i), i) for i in items]
from sets import Set
si = Set(di)
ui = [i[1] for i in si]
ui

[(1, 2, 3), (1, 2, 3)]

Is there a dictionary type which uses __cmp__() like
btrees in the standard library?

I don't understand. For the above example an algorithm based on __cmp__()
would return a list with a single item which does not seem to be what you
want.

Peter

 

[Thomas Guettler]

Am Tue, 06 Jan 2004 04:04:01 -0500 schrieb Mike C. Fletcher:

Just wrote:
AFAIK, the dictionary class simply uses the hash to sort into buckets,
providing fast indexing, before using equality to check whether the two
keys are equal.

Thank you, that what I was asking for.

Here is a sample script which checks this:

from types import *

class MyHash:
def __init__(self, id):
assert(type(id)==IntType)
self.id=id

def __hash__(self):
# All objects have the same hash value
return 1

def __cmp__(self, b):
return cmp(self.id, b.id)

def __repr__(self):
return "<MyHash id=%s>" % self.id

def main():
d={}
i1=MyHash(1)
d[i1]=1
i2=MyHash(2)
d[i2]=1
i3=MyHash(3)
d[i3]=1
print d.items()

# id=1 twice
d[MyHash(1)]=1

print d.items()
# All right there are only three elements in the dict
# Dictionaries use __cmp__ if __hash__ is equal.

if __name__=="__main__":
main()