tuple.__hash__()

Mike C. Fletcher mcfletch at rogers.com
Tue Jan 6 10:04:01 CET 2004


Just wrote:

>In article <pan.2004.01.06.08.17.30.910345 at thomas-guettler.de>,
> "Thomas Guettler" <guettli at thomas-guettler.de> wrote:
>
>  
>
>>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?
>  
>
Yes, but the OP is probably worried about whether the dictionary class 
can differentiate between objects which hash equal and equal objects:

 >>> class x:
...     def __hash__( self ):
...         return 32
...    
 >>> a = x()
 >>> b = x()
 >>> d = {}
 >>> d[a] = 1
 >>> d[b] = 1
 >>> d
{<__main__.x instance at 0x0129F828>: 1, <__main__.x instance at 
0x01523BA0>: 1}
 >>> 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[s] = 1
 >>> d[t] = 1
 >>> d
{<__main__.y instance at 0x011FCF08>: 1}
 >>>

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.

>>Is there a dictionary type which uses __cmp__() like
>>btrees in the standard library?
>>    
>>
>
>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/







More information about the Python-list mailing list