見出し画像

Python 3: Deep Dive (Part 3 - Dictionaries, Sets, JSON): カスタムクラスのハッシュ化 (セクション3-4/12)

Hafnium

  • Pythonの辞書でカスタムクラスをキーとして使用するには、`__eq__`メソッドと`__hash__`メソッドを適切に実装する必要があります。

  • キーとして使用されるカスタムクラスは不変（イミュータブル）である必要があり、属性の変更はハッシュ値の一貫性を損なう可能性があります。

  • 効率的な辞書の実装には、ハッシュ値が均一に分散され、等しいオブジェクトは同じハッシュ値を持つように設計することが重要です。

Pythonの辞書は、キーと値のペアを使用してデータを効率的に保存および取得できる強力なデータ構造です。デフォルトでは、辞書のキーは文字列、数値、または不変要素のタプルなど、ハッシュ可能で不変な型である必要があります。しかし、カスタムオブジェクトを辞書のキーとして使用したい場合はどうすればよいでしょうか？

このブログ記事では、カスタムクラスをハッシュ可能にし、辞書のキーとして使用する方法を探ります。`__eq__`メソッドと`__hash__`メソッドを正しく実装することの重要性について掘り下げ、ハッシュの衝突や可変キーなどの潜在的な落とし穴について説明します。

辞書の仕組みを理解する

カスタムクラスとハッシュ化について掘り下げる前に、Pythonの辞書が内部でどのように動作するかを簡単に確認しましょう。

キーと値のペアの挿入

辞書にキーと値のペアを挿入する際：

  1. ハッシュ値の計算: Pythonは`hash(key)`を使用してキーのハッシュ値を計算します。

  2. インデックスの決定: 辞書のサイズでハッシュ値を剰余演算することで、ハッシュテーブル内のインデックスを計算します（`hash(key) % dict_size`）。

  3. プローブシーケンス: 計算されたインデックスが既に使用されている場合、Pythonは次の利用可能なスロットを見つけるためのプローブシーケンスを生成します。

  4. アイテムの保存: 空きスロットが見つかると、そのインデックスに`(hash, key, value)`のタプルを保存します。

値の取得

キーを使用して値を取得する際：

  1. ハッシュ値の計算: Pythonはキーのハッシュ値を計算します。

  2. インデックスの決定: 挿入時と同じ方法で開始インデックスを計算します。

  3. プローブシーケンス: そのインデックスにあるキーが探しているキーと一致するかどうかを確認します。一致しない場合は、挿入時と同じプローブシーケンスに従います。

  4. キーの比較: ハッシュ値を比較し、その後`==`を使用してキーの等価性を比較します。

  5. 値の返却: 一致が見つかった場合、関連する値を返します。

重要な注意点: このメカニズムが正しく機能するためには、辞書内でのキーの寿命中、キーのハッシュ値が一定である必要があります。

カスタムクラスのデフォルトの動作

デフォルトでは、Pythonのカスタムクラスはベースとなる`object`クラスからデフォルトの`__hash__`メソッドを継承するため、ハッシュ可能です。このデフォルトのハッシュはオブジェクトの`id`（メモリアドレス）に基づいており、各インスタンスが一意であることを保証します。

ただし、カスタムオブジェクトは同じインスタンス（つまり、`a is b`）である場合にのみ等しい（`==`）とみなされます。

例

class Person:
    def __init__(self, name):
        self.name = name

p1 = Person('Alice')
p2 = Person('Alice')

print(p1 == p2)  # False
print(hash(p1), hash(p2))  # 異なるハッシュ値

説明

  • `p1`と`p2`は異なるインスタンスなので、等しくありません。

  • それぞれの一意の`id`に基づいているため、ハッシュ値は異なります。

等価性とハッシュ化の実装

辞書のキーとして使用する際に期待通りの動作をさせるには、カスタムオブジェクトにeqとhashメソッドを定義する必要があります。

等価性の定義 `__eq__`

eqメソッドにより、クラスの2つのインスタンスがいつ等しいとみなされるかを定義できます。

class Person:
    def __init__(self, name):
        self.name = name

    def __eq__(self, other):
        if isinstance(other, Person):
            return self.name == other.name
        return False

ハッシュ値の定義 `__hash__`

`__eq__`を定義すると、Pythonは自動的に`__hash__`を`None`に設定し、オブジェクトをハッシュ不可能にします。これは矛盾した動作を防ぐためです。したがって、`__hash__`も定義する必要があります。

class Person:
    def __init__(self, name):
        self.name = name

    def __eq__(self, other):
        if isinstance(other, Person):
            return self.name == other.name
        return False

    def __hash__(self):
        return hash(self.name)

重要なルール:

  • 一貫性: 2つのオブジェクトが等しい（`__eq__`が`True`を返す）場合、それらのハッシュ値（`__hash__`）も等しくなければなりません。

  • 不変性: `__eq__`と`__hash__`で使用される属性は不変であるべきです。変更すると、辞書内でオブジェクトにアクセスできなくなる可能性があります。

例

p1 = Person('Alice')
p2 = Person('Alice')

print(p1 == p2)  # True
print(hash(p1) == hash(p2))  # True

# 辞書のキーとして使用
people = {p1: 'Person 1'}
print(people[p2])  # 'Person 1'

ハッシュの衝突を避ける

ハッシュの衝突は、等しくない2つのオブジェクトが同じハッシュ値を持つ場合に発生します。衝突は許容され、避けられません（鳩の巣原理による）が、過度の衝突は辞書のパフォーマンスを低下させる可能性があります。

悪いハッシュ関数の例:

class BadHashPerson:
    def __init__(self, name):
        self.name = name

    def __eq__(self, other):
        return isinstance(other, BadHashPerson) and self.name == other.name

    def __hash__(self):
        return 42  # 悪い考え：定数のハッシュ値

定数のハッシュ値を使用すると、辞書は完全な等価性チェックを使用してすべてのキーを解決する必要があり、パフォーマンスに深刻な影響を与えます。

タイミングの比較:

import timeit

good_person_dict = {Person(f'Person {i}'): i for i in range(1000)}
bad_person_dict = {BadHashPerson(f'Person {i}'): i for i in range(1000)}

good_time = timeit.timeit(lambda: good_person_dict[Person('Person 500')], number=10000)
bad_time = timeit.timeit(lambda: bad_person_dict[BadHashPerson('Person 500')], number=10000)

print(f"良いハッシュの時間: {good_time}")
print(f"悪いハッシュの時間: {bad_time}")

結果:

良いハッシュの時間: 0.02秒
悪いハッシュの時間: 1.5秒

結論:

  • `__hash__`関数が常にハッシュ値を均一に分散するようにしてください。

  • オブジェクトを一意に識別する不変な属性を使用してください。

実践的な例：カスタムクラスを辞書のキーとして使用する

2D空間の座標を表す`Point`クラスを作成し、それを辞書のキーとして使用してみましょう。

Pointクラスの実装

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

    # 文字列表現
    def __repr__(self):
        return f"Point({self.x}, {self.y})"

    # 等価性の比較
    def __eq__(self, other):
        if isinstance(other, Point):
            return self.x == other.x and self.y == other.y
        elif isinstance(other, tuple) and len(other) == 2:
            return (self.x, self.y) == other
        return False

    # ハッシュ関数
    def __hash__(self):
        return hash((self.x, self.y))

Pointを辞書のキーとして使用

# いくつかのPointインスタンスを作成
p1 = Point(0, 0)
p2 = Point(1, 1)

# Pointをキーとする辞書を作成
points_dict = {
    p1: "原点",
    p2: "単位点",
}

# Pointインスタンスを使用して値にアクセス
print(points_dict[Point(0, 0)])  # 出力: 原点

# タプルを使用して値にアクセス
print(points_dict[(1, 1)])  # 出力: 単位点

説明

  • `__eq__`メソッド: `Point`インスタンスとタプル間の比較を可能にします。

  • `__hash__`メソッド: `(self.x, self.y)`のタプルをハッシュ化し、`eq`との一貫性を確保します。

可変キーの問題

可変オブジェクトは状態を変更できるため、辞書のキーとして使用すると不整合な動作につながる可能性があります。

例

p = Point(0, 0)
points_dict = {p: "原点"}

# Pointインスタンスを変更
p.x = 10

# 値の取得を試みる
print(points_dict[p])  # KeyErrorが発生

説明:

  • `p.x`を変更した後、`p`のハッシュ値が変更されます。

  • 異なるインデックスにハッシュされるため、辞書はキーを見つけることができません。

  • これは、辞書のキーが不変である必要がある理由を示しています。

不変性の確保

可変キーの問題を防ぐため、クラスを不変に設計することができます。

Pointを不変にする

class ImmutablePoint:
    def __init__(self, x, y):
        self._x = x
        self._y = y
        self._hash = hash((self._x, self._y))  # ハッシュ値を事前計算

    @property
    def x(self):
        return self._x

    @property
    def y(self):
        return self._y

    def __repr__(self):
        return f"ImmutablePoint({self.x}, {self.y})"

    def __eq__(self, other):
        if isinstance(other, ImmutablePoint):
            return self.x == other.x and self.y == other.y
        elif isinstance(other, tuple) and len(other) == 2:
            return (self.x, self.y) == other
        return False

    def __hash__(self):
        return self._hash

説明:

  • プライベート属性: `_x`と`_y`を使用し、読み取り専用のプロパティ`x`と`y`を提供します。

  • 事前計算されたハッシュ値: 初期化時にハッシュ値を計算して保存します。属性は変更できないため、ハッシュ値は一貫性を保ちます。

  • 不変性: クラスのユーザーは`x`と`y`を変更できず、辞書内でキーの一貫性が保たれます。

ImmutablePointの使用

p = ImmutablePoint(0, 0)
points_dict = {p: "原点"}

# 変更を試みる（AttributeErrorが発生します）
# p.x = 10  # プロパティに代入できません

# 値へのアクセス
print(points_dict[p])  # 出力: 原点

結論

Pythonで辞書のキーとしてカスタムクラスを使用するには、`__eq__`メソッドと`__hash__`メソッドを慎重に実装する必要があります。覚えておくべき重要なポイント：

  • 一貫性: 2つのオブジェクトが等しい場合、それらのハッシュ値も等しくなければなりません。

  • 不変性: `__eq__`と`__hash__`で使用される属性は、予期しない動作を防ぐため不変である必要があります。

  • ハッシュの衝突を回避: ハッシュ値を均一に分散させる良いハッシュ関数を実装してください。

これらのガイドラインに従うことで、カスタムオブジェクトを辞書のキーとして効果的に使用し、Pythonアプリケーションでより高度で効率的なデータ構造を実現できます。

ハッピーコーディング！

「超本当にドラゴン」へ

いいなと思ったら応援しよう！