113_ハッシュのキーになるクラスを作る

（Ruby のハッシュの役割をする Python の型は 辞書 です。）

辞書のキーになるクラスには、「同値のインスタンスは同じハッシュ値をもつ」という特性があることが必要です。このためには「同値」の定義がいるので「インスタンス間の大小関係が一意に決まること」という特性も必要になります。とはいえ、同値の定義を行っていない自作クラスの場合、代わりに「同一」かどうかをつかさどるアイデンティティ値（CPython ではアドレス）によって大小関係、ハッシュ値がむりやり定義されるので、なにもしなくとも辞書のキーにすることはできます。

class Rect(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return '%s(x=%d, y=%d)' % (self.__class__.__name__, self.x, self.y)

a = Rect(1, 3)
b = Rect(2, 1)
c = Rect(1, 2)
d = Rect(1, 3)
dict_ = {}
dict_[a] = 1
dict_[b] = 2
dict_[c] = 3
dict_[d] = 4
print dict_

この実行結果は次のようになります。

{Rect(x=1, y=3): 1, Rect(x=2, y=1): 2, Rect(x=1, y=2): 3, Rect(x=1, y=3): 4}

ここで気になるのは a と d が別物扱いされていることですが、実のところこのままで十分であることが多いです。問題なければ以下の説明は不要となります。

この a と d を同じものとして扱いたい、といった場合は、「インスタンス間の大小関係を決めるメソッド」および「同値のインスタンスからはいつでも同じハッシュ値を生成するメソッド」をきっちり定義する必要があります。 具体的には __cmp__ メソッド 、 __hash__ メソッドが必要です。たとえば、次のようになります。 （属性 x, y に整数以外が入ると動作が破綻する、 __hash__ メソッドの実装がずさんである、そもそも矩形（？）同士に大小関係を持ち出すとはなんぞや、といった問題は残っています。もっとよい例があれば置き換えていただけると幸いです。）

class Rect(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return self.x << 16 + self.y

    def __cmp__(self, other):
        x = self.x - other.x
        if x:
            return x
        return self.y - other.y

    def __repr__(self):
        return '%s(x=%d, y=%d)' % (self.__class__.__name__, self.x, self.y)

a = Rect(1, 3)
b = Rect(2, 1)
c = Rect(1, 2)
d = Rect(1, 3)
dict_ = {}
dict_[a] = 1
dict_[b] = 2
dict_[c] = 3
dict_[d] = 4
print d

print
print hash(a), hash(b), hash(c), hash(d)
print sorted([a, b, c, d])

この実行結果の例は次のようになります。

{Rect(x=1, y=3): 4, Rect(x=2, y=1): 2, Rect(x=1, y=2): 3}

524288 262144 262144 524288
[Rect(x=1, y=2), Rect(x=1, y=3), Rect(x=1, y=3), Rect(x=2, y=1)]