home changes contents help options

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)]

__cmp__ メソッド

__cmp__(self, other) メソッドはオブジェクト同士が「同値」であるか比較するために用いられてます。 self のほうが小さければ負の整数を、大きければ正の整数を、等しければ 0 を返すべきメソッドです。

__hash__ メソッド

__hash__(self) メソッドは辞書が内部でオブジェクトのハッシュ値を求めるため用いられています。同値のオブジェクトは同じ整数値を、同値でないオブジェクトはなるべく異なる整数値を返すべきメソッドです。「同値のオブジェクトは同じ整数値を」を言い換えると、「a == b が真であるオブジェクト a, b があるならば a.__hash__() == b.__hash__() となる」となります。

詳しくは Python リファレンスマニュアル 3.4 特殊メソッド名 の __cmp__, __hash__ 、ライブラリリファレンス 2.1 組み込み関数 の hash, id を参照してください。