Re: Fast union/intersection of two sequences?

Jim Roskind (jar@infoseek.com)
Tue, 24 Jan 1995 11:25:40 -0800

> Date: Tue, 24 Jan 1995 13:06:22 -0500
> From: Skip Montanaro <skip@automatrix.com>
> Reply-To: skip@automatrix.com (Skip Montanaro)
>
> Thanks for the reply. Dictionaries had occurred to me but I was worried
> about the inability to use classes as keys. Can the __hash__ function for
> the class return the class's address:
>
> <MusicDB instance at f81c0>
> ?

To return the address, you need to use the "id" function. The method
would look like:

def __hash__(self):
return id(self)

Keep in mind that comparing by IDs will not reveal that stuff that
"compares equal" (re: the innards of the instance) will match. Often
what you want is a pair of matching hash and cmp methods. IF you want
to use the address (`cause you make one-and-only-one object for each
"thing" in the list) then you'd use:

def __hash__(self):
return id(self)

def __cmp__(self, other):
return id(self) - id(other)

If the object has some real innards (like a string and an index), then
you would probably want something like:

def __init__(self, str, val):
self.str = str
self.val = val

def __hash__(self):
return hash(self.str) + hash(self.val)

def __cmp__(self, other):
diff = cmp(self.val,other.val) # primary compare key
if diff:
return diff
return cmp(self.str, other.str) # secondary compare key

The "rule" is that whenever two objects "compare" equal, it must be
the case that the hash values compare equal. Note how this was
achieved with each of the methods I listed. If you break this "rule,"
then the dictionary may "mess up" and allow multiple keys that compare
equal, but hash differently. If the consequences I mentioned are
confusing, just consider abiding by the "rule" ;-), and you'll be very
safe.

I hope this helps.

Jim

-- 
Jim Roskind
InfoSeek Corporation
voice: 408.982.4469
fax: 408.986.1889
jar@infoseek.com
----------------------------------------------------------------------------
PGP 2.6.1 Key fingerprint =  0E 2A B2 35 01 9B 5C 58  2D 52 05 9A 3D 9B 84 DB 
To get my PGP 2.6 Public Key, "finger -l jar@infoseek.com | pgp -kaf"