「キーを使用して呼び出すとどうなるのですか」

Question

私は、__hash__と__eq__の両方を実装するクラス（myClassと呼ぶ）を持っています。また、myClassオブジェクトをある値にマップするdictがあります。計算には時間がかかります。

多くの（数百万のオーダーの）myClassオブジェクトがインスタンス化されています。これが私がdictを使用してそれらの値を追跡する理由です。

ただし、新しいmyClassオブジェクトは、古いオブジェクト（__eq__メソッドで定義されているもの）と同等であることがあります。だから、そのオブジェクトの値を再び計算するのではなく、dictの古いmyClassオブジェクトの値を参照するだけです。これを達成するために、私はif myNewMyClassObj in dictをします。

は、ここに私の質問です：呼び出されるものを

私はin句ことを使用し、__hash__または__eq__？ dictを使用するポイントは、O（1）検索時間です。したがって、__hash__を呼び出す必要があります。しかし、__hash__と__eq__が同等の方法でない場合はどうなりますか？その場合、if myNewMyClassObj in dictに対して偽陽性が表示されますか？

は質問をフォローアップ：

私は私のdict内のエントリの数を最小限にしたいので、私は理想的dictの等価myClassオブジェクトのセットの一つだけ維持したいと思います。だから、再び、dictのO（1）Oへの検索時間（n）の検索時間

Answer 1

まず、__hash__(myNewMyClassObj)が呼び出されます。同じハッシュを持つオブジェクトが辞書に見つからない場合、PythonはmyNewMyClassObjが辞書にないとみなします。 （Pythonは__eq__は、2つのオブジェクトの場合と同等と評価するたびに、その__hash__が同一でなければならないことを必要とすることに注意してください。）

同じ__hash__といくつかのオブジェクトは辞書に載っている場合、__eq__は、それらのそれぞれの上に呼び出されます。 __eq__が等しいと評価された場合、myNewMyClassObj in dict_はTrueを返します。

したがって、__eq__と__hash__の両方が高速であることを確認するだけで済みます。

ご連絡先：dict_には、MyClassのオブジェクト（__eq__で定義）の1つだけが保存されています。

同じハッシュを持ち同じバケットに割り当てられたオブジェクトに対してのみ、__eq__が呼び出されることに注意してください。そのようなオブジェクトの数は、通常は非常に少ない数です（dictの実装はそれを確認します）。だからあなたはまだ（約）O(1)ルックアップのパフォーマンスがあります。

Answer 2

__hash__が常に呼び出されますを汚すことになる、if myNewClassObj in dictを計算するとき__eq__ニーズが呼び出されるようです。オブジェクトが実際に辞書にある場合、または同じハッシュを持つ別のオブジェクトが辞書に含まれている場合は、__eq__が呼び出されます。ハッシュ値は、可能なキーの選択を絞り込むために使用されます。キーはハッシュ値でバケツに分類されますが、ルックアップのためには、バケット内の各キーをルックアップキーと同じかどうかチェックする必要があります。 http://wiki.python.org/moin/DictionaryKeysを参照してください。これらの例を見てください：

>>> class Foo(object): 
...  def __init__(self, x): 
...   self.x = x 
...  
...  def __hash__(self): 
...   print "Hash" 
...   return hash(self.x) 
... 
...  def __eq__(self, other): 
...   print "Eq" 
...   return self.x == other.x 
>>> Foo(1) in d 
Hash 
Eq 
10: True 
>>> Foo(2) in d 
Hash 
Eq 
11: True 
>>> Foo(3) in d 
Hash 
Eq 
12: True 
>>> Foo(4) in d 
Hash 
13: False 

その例では、__hash__が常に呼ばれて見ることができます。 __eq__は、オブジェクトがdict内にあるときにルックアップごとに1回呼び出されます。それらはすべて個別のハッシュ値を持つため、そのハッシュ値を持つオブジェクトが実際に照会されるものであることを検証するのに十分です。 __eq__は、最後のケースでは呼び出されません。ディクショナリ内のオブジェクトのどれもがFoo(4)と同じハッシュ値を持たないため、Pythonは__eq__を続ける必要はありません。

>>> class Foo(object): 
...  def __init__(self, x): 
...   self.x = x 
...  
...  def __hash__(self): 
...   print "Hash" 
...   return 1 
... 
...  def __eq__(self, other): 
...   print "Eq" 
...   return self.x == other.x 
>>> d = {Foo(1): 2, Foo(2): 3, Foo(3): 4} 
Hash 
Hash 
Eq 
Hash 
Eq 
Eq 
>>> Foo(1) in d 
Hash 
Eq 
18: True 
>>> Foo(2) in d 
Hash 
Eq 
Eq 
19: True 
>>> Foo(3) in d 
Hash 
Eq 
Eq 
Eq 
20: True 
>>> Foo(4) in d 
Hash 
Eq 
Eq 
Eq 
21: False 

このバージョンでは、すべてのオブジェクトのハッシュ値が同じです。この場合、__eq__は、ハッシュが値を区別しないため、常に複数回呼び出されることがあるので、Pythonは等しい値を見つけるまで明示的に等価性をチェックする必要がありますそれが探しているもの）。場合によっては最初の試行（上記のFoo(1) in dict）でそれを見つけることがありますが、時にはすべての値をチェックする必要があります。

Answer 3

__hash__は、オブジェクトが格納されるバケットを定義します。__eq__は、オブジェクトが同じバケット内にある場合にのみ呼び出されます。