Take the 2-minute tour ×

How do __hash__ and __eq__ use in identification in sets? For example some code that should help to solve some domino puzzle:

class foo(object):
    def __init__(self, one, two):
        self.one = one
        self.two = two
    def __eq__(self,other):
        if (self.one == other.one) and (self.two == other.two): return True
        if (self.two == other.one) and (self.one == other.two): return True
        return False
    def __hash__(self):
        return hash(self.one + self.two)

s = set()

for i in range(7):
    for j in range(7):
len(s) // returns 28 Why?

If i use only __eq__() len(s) equals 49. Its ok because as i understand objects (1-2 and 2-1 for example) not same, but represent same domino. So I have added hash function.
Now it works the way i want, but i did not understand one thing: hash of 1-3 and 2-2 should be same so they should counted like same object and shouldn't added to set. But they do! Im stuck.

share|improve this question
add comment

4 Answers

up vote 2 down vote accepted

Equality for dict/set purposes depends on equality as defined by __eq__. However, it is required that objects that compare equal have the same hash value, and that is why you need __hash__. See this question for some similar discussion.

The hash itself does not determine whether two objects count as the same in dictionaries. The hash is like a "shortcut" that only works one way: if two objects have different hashes, they are definitely not equal; but if they have the same hash, they still might not be equal.

In your example, you defined __hash__ and __eq__ to do different things. The hash depends only on the sum of the numbers on the domino, but the equality depends on both individual numbers (in order). This is legal, since it is still the case that equal dominoes have equal hashes. However, like I said above, it doesn't mean that equal-sum dominoes will be considered equal. Some unequal dominoes will still have equal hashes. But equality is still determined by __eq__, and __eq__ still looks at both numbers, in order, so that's what determines whether they are equal.

It seems to me that the appropriate thing to do in your case is to define both __hash__ and __eq__ to depend on the ordered pair --- that is, first compare the greater of the two numbers, then compare the lesser. This will mean that 2-1 and 1-2 will be considered the same.

share|improve this answer
Still not all clear. It stop work if i comment __hash__ or __eq__. And I still dont know why it works now. Is it uses both __eq__ and __hash__ to determin in? I hoped someone can tell me how this comparison works. Something about if hash1 == hash2 and if (eq) and so on... –  Александр Зотов Jan 16 '13 at 7:52
@Александр Зотов: You'll need to be more specific than that. Did you read the question I linked to? What is it that remains unclear? –  BrenBarn Jan 16 '13 at 7:53
add comment

The hash is only a hint to help Python arrange the objects. When looking for some object foo in a set, it still has to check each object in the set with the same hash as foo.

It's like having a bookshelf for every letter of the alphabet. Say you want to add a new book to your collection, only if you don't have a copy of it already; you'd first go to the shelf for the appropriate letter. But then you have to look at each book on the shelf and compare it to the one in your hand, to see if it's the same. You wouldn't discard the new book just because there's something already on the shelf.

If you want to use some other value to filter out "duplicates", then use a dict that maps the domino's total value to the first domino you saw. Don't subvert builtin Python behavior to mean something entirely different. (As you've discovered, it doesn't work in this case, anyway.)

share|improve this answer
add comment

You can read about this in the Python data model documentation, but the short answer is that you can rewrite your hash function as:

def __hash__(self):
    return hash(tuple(sorted((self.one, self.two))))
share|improve this answer
this would get him further from what he wants; 1 2 and 2 1 would once again count as the same domino. but he should be doing this anyway, yes. :) –  Eevee Jan 16 '13 at 6:35
@Eevee - thanks fixed –  Andrew Walker Jan 16 '13 at 6:37
add comment

The requirement for hash functions is that if x == y for two values, then hash(x) == hash(y). The reverse need not be true.

You can easily see why this is the case by considering hashing of strings. Lets say that hash(str) returns a 32-bit number, and we are hashing strings longer than 4 characters long (i.e. contain more than 32 bits). There are more possible strings than there are possible hash values, so some non-equal strings must share the same hash (this is an application of the pigeonhole principle).

Python sets are implemented as hash tables. When checking whether an object is a member of the set, it will call its hash function and use the result to pick a bucket, and then use the equality operator to see if it matches any of the items in the bucket.

With your implementation, the 2-2 and 1-3 dominoes will end up in the hash bucket, but they don't compare equal. Therefore, the both can be added to the set.

share|improve this answer
add comment

Your Answer


