0

I've created a class containing several members.

I would like to create hash table, containing 'objects' of this class and to be able to search (use the hashmap :) )

As I know I should overload the __eq__ operator

what should I go from there?

I wasn't able to find any references for creating an hash table in python ... especially not for 'my class'

1
  • 1
    It is called a python dict. Commented Mar 20, 2013 at 17:41

1 Answer 1

5

You need to implement the .__hash__() method as well as the .__eq__() method.

The method should return an integer, and for any two objects where .__eq__() returns True, .__hash__() must return the same integer value.

The easiest way to accomplish this is to use the built-in hash() function on each and every attribute of your instance that makes it unique, and return the XORed result of those values.

Example:

class Foo(object):
    def __init__(self, bar, baz):
        self.bar = bar
        self.baz = baz

    def __eq__(self, other):
        if isinstance(other, type(self)):
            return self.bar == other.bar and self.baz == other.baz
        return False

    def __hash__(self):
        return hash(self.bar) ^ hash(self.baz)

Demo:

>>> foo1 = Foo('ham', 'eggs')
>>> foo2 = Foo('ham', 'eggs')
>>> foo3 = Foo('spam', 'vikings')
>>> foo1 == foo2
True
>>> foo1 == foo3
False
>>> hash(foo1)
1838536788654183919
>>> hash(foo1) == hash(foo2)
True
>>> hash(foo1) == hash(foo3)
False
>>> mapping = {}
>>> mapping[foo1] = 'Monty Python'
>>> foo1 in mapping
True
>>> foo2 in mapping
True
>>> foo3 in mapping
False
>>> mapping[foo2]
'Monty Python'
Sign up to request clarification or add additional context in comments.

1 Comment

@SagiLow: The python dict is a hashmap under the hood and insertion and lookup on those has O(1) complexity. All __hash__ does is make it possible for you to use your custom type as a key. We did not create the hash table itself here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.