CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Object-Oriented Programming (OOP), Part 4
The __hash__ method



  1. Using in Sets and Dictionaries (__hash__ and __eq__)
    The problem:
    Objects do not seem to hash right by default:
    class A(object): def __init__(self, x): self.x = x a = A(5) b = A(5) print(hash(a) == hash(b)) # False (this is surprising)

    And that produces this unfortunate situation:
    class A(object): def __init__(self, x): self.x = x s = set() s.add(A(5)) print(A(5) in s) # False d = dict() d[A(5)] = 42 print(d[A(5)]) # crashes

    The solution: __hash__ and __eq__
    The __hash__ method tells Python how to hash the object. The properties you choose to hash on should be immutable types and should never change (so hash(obj) is immutable).
    class A(object): def __init__(self, x): self.x = x def __hash__(self): return hash(self.x) def __eq__(self, other): return (isinstance(other, A) and (self.x == other.x)) s = set() s.add(A(5)) print(A(5) in s) # True (whew!) d = dict() d[A(5)] = 42 print(d[A(5)]) # works!

    A better (more generalizable) solution
    You can define the method getHashables that packages the things you want to hash into a tuple, and then you can use a more generic approach to __hash__:
    # Your getHashables method should return the values upon which # your hash method depends, that is, the values that your __eq__ # method requires to test for equality. # CAVEAT: a proper hash function should only test values that will not change! class A(object): def __init__(self, x): self.x = x def getHashables(self): return (self.x, ) # return a tuple of hashables def __hash__(self): return hash(self.getHashables()) def __eq__(self, other): return (isinstance(other, A) and (self.x == other.x)) s = set() s.add(A(5)) print(A(5) in s) # True (still works!) d = dict() d[A(5)] = 42 print(d[A(5)]) # works!

  2. Fraction Example
    # Very simple, partly-implemented Fraction class # to demonstrate the OOP ideas from above. # Note that Python actually has a full Fraction class that # you would use instead (from fractions import Fraction), # so this is purely for demonstrational purposes. def gcd(x, y): if (y == 0): return x else: return gcd(y, x%y) class Fraction(object): def __init__(self, num, den): # Partial implementation -- does not deal with 0 or negatives, etc g = gcd(num, den) self.num = num // g self.den = den // g def __repr__(self): return '%d/%d' % (self.num, self.den) def __eq__(self, other): return (isinstance(other, Fraction) and ((self.num == other.num) and (self.den == other.den))) def times(self, other): if (isinstance(other, int)): return Fraction(self.num * other, self.den) else: return Fraction(self.num * other.num, self.den * other.den) def __hash__(self): return hash((self.num, self.den)) def testFractionClass(): print('Testing Fraction class...', end='') assert(str(Fraction(2, 3)) == '2/3') assert(str([Fraction(2, 3)]) == '[2/3]') assert(Fraction(2,3) == Fraction(2,3)) assert(Fraction(2,3) != Fraction(2,5)) assert(Fraction(2,3) != "Don't crash here!") assert(Fraction(2,3).times(Fraction(3,4)) == Fraction(1,2)) assert(Fraction(2,3).times(5) == Fraction(10,3)) s = set() assert(Fraction(1, 2) not in s) s.add(Fraction(1, 2)) assert(Fraction(1, 2) in s) s.remove(Fraction(1, 2)) assert(Fraction(1, 2) not in s) print('Passed.') if (__name__ == '__main__'): testFractionClass()