[Tutor] Hashing

[Roeland Rengelink]

charlie derr wrote:
> 
> +-----Original Message-----
> +From: tutor-admin@python.org [mailto:tutor-admin@python.org]On Behalf Of
> +Allan Crooks
> +Sent: Friday, August 10, 2001 8:09 PM
> +To: tutor@python.org
> +Subject: [Tutor] Hashing
> +
> +
> +Hi,
> +
> +Does anyone know exactly how the hash method derives a hash
> +for tuples? Or strings?
> +
> +>>> a, b, c, d = (1,), (2,), (3,), (4,)
> +>>> map (hash, [a, b, c, d])
> +[-1660579480, -1660579477, -1660579478, -1660579475]
> +
> +The above code does seem slightly bewildering to me, anyone got
> +any ideas?
> 
> no ideas, but i found something strange while playing around
> 
> >>> hash((0,))
> -1660579479
> >>> hash((-1,))
> 1660579479
> >>> hash((-2,))
> 1660579479
> 
> aren't these values supposed to be unique?
> 

Nope,

They couldn't be. hash() should be (is) able map a potentially infinite
number of objects to the finite set of integers. Note that integers
(except -1, see Danny's reply) are their own hashes, which already uses
the set of all possible hash numbers once.

Note:

hash(hash(x)) == hash(x) for all python objects x

When python compares hashes for two objects, and finds they are the
same, it will compare objects to determine if they are really the same
object.

This leads to an interesting result:

class A:
    def __hash__(self):
        return 1 # instances always the same hash value
    def __cmp__(self, other):
        return 0 # instances always compare equal

a, b = A(), A()

d = {a:'a', b:'b'}
print a, b
-> <__main__.A instance at 0x814741c> <__main__.A instance at 0x814ba54>
print d
-> {<__main__.A instance at 0x814741c>: 'b'}

and (big surprise):

d = {a:'a', 1:'c'}
print d
-> {<__main__.A instance at 0x814741c>: 'c'}

While:

class A:
    def __hash__(self):
        return 1 # instances always the same hash value
    def __cmp__(self, other):
        return 1 # instances always compare unequal

a, b = A(), A()

d = {a:'a', b:'b'}
print a, b
-> (<__main__.A instance at 0x81494bc>, <__main__.A instance at
0x81476ac>)
print d
-> {<__main__.A instance at 0x81494bc>: 'a', <__main__.A instance at
0x81476ac>: 'b'}

Have fun,

Roeland
-- 
r.b.rigilink@chello.nl

"Half of what I say is nonsense. Unfortunately I don't know which half"