Pythonのラムダ関数のハッシュ

Question

ラムダ関数のハッシュを取得しようとしています。なぜ2つの値（8746164008739と-9223363290690767077）が得られますか？ラムダ関数のハッシュが必ずしも1つの値ではないのはなぜですか？

>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 
>>> fn = lambda: 1 
>>> hash(fn) 
8746164008739 
>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 
>>> fn = lambda: 1 
>>> hash(fn) 
8746164008739 
>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 

Answer 1

2つのオブジェクトは、等しい[1]を比較しない限り、同じ値にハッシュすることは保証されません。

Python関数（lambdaを含む）は、同じコード[2]を持っていても等しいとは限りません。例：

>>> (lambda: 1) == (lambda: 1) 
False 

実装上、この動作は、関数オブジェクトが独自の等価演算子を提供しないためです。代わりに、オブジェクトのアイデンティティ、すなわちそのアドレスを使用するデフォルトのものを継承します。 documentationから：NO __cmp__()、__eq__()又は__ne__()操作が定義されていない場合

、クラス インスタンスは、オブジェクトアイデンティティ（「アドレス」）によって比較されます。

ここでは、あなたの特定の例では何が起こるかです：アドレスAは常に一つの値、および別のアドレスBにハッシュされているので

fn = lambda: 1 # New function is allocated at address A and stored in fn. 
fn = lambda: 1 # New function is allocated at address B and stored in fn. 
       # The function at address A is garbage collected. 
fn = lambda: 1 # New function is allocated at address A and stored in fn. 
       # The function at address B is garbage collected. 
fn = lambda: 1 # New function is allocated at address B and stored in fn. 
       # The function at address A is garbage collected. 
... 

、次の2つの値の間hash(fn)交互に見ています。しかし、この交互の動作は実装のアーチファクトであり、たとえばガベージコレクタがわずかに異なるように動作するようにすると、ある日に変更される可能性があります。

次洞察に満ちたノートは@ruakhによって寄与されました：

それはそれは2つの機能が等価であるかどうかを決定するための一般的なプロセス を書くことは可能ではないことは注目に値します。 （これは、halting problemのundecidabilityの 結果である。）（これらは 異なる、しかし、同じ名前の変数を参照するクロージャであってもよいので） さらに、2つのPythonの機能は、それら コードが同一であっても異なって振る舞うことができます。したがって、 Python関数は等価演算子をオーバーロードしません。 は、デフォルトのオブジェクトIDよりも優れたものを実装する方法はありません 比較。

[1]逆は同じではない2つのオブジェクトは、同じハッシュ値を持つことができます。これはhash collisionと呼ばれます。

>>> (lambda: 1)() == (lambda: 1)() 
True 

Answer 2

がlambda関数オブジェクトのハッシュは、次のとおりです。

[2] hash(1)は、常に1つのプログラム内で同じであるので、もちろん常に同じ値を与える結果をハッシュそしてあなたのラムダを呼び出すと、そのメモリアドレスに基づいて（CPythonでこれはid関数が返すものです）。つまり、関数に同じコードが含まれていても、2つの関数オブジェクトは異なるハッシュ（ハッシュの衝突がないと仮定します）を持つことになります。

質問で何が起きているのかを説明するために、最初に、fn = lambda: 1を書くとメモリに新しい関数オブジェクトが作成され、fnという名前がバインドされます。したがって、この新しい関数は、既存の関数とは異なるハッシュ値を持ちます。

fn以前こと、fnが新しく作成した関数オブジェクトにバインドされている場合ので、あなたはハッシュの値を交互に取得し、機能をfn = lambda: 1を繰り返すには、Pythonで収集ごみであると指摘しました。これは、（fnの名前が別のオブジェクトを指しているため）参照がなくなったためです。

次に、Pythonインタプリタは、この古いメモリアドレスを、fn = lambda: 1を書き込んで作成された次の新しい関数オブジェクトに再利用します。

この動作は、システムとPythonの実装によって異なります。

Answer 3

fn = lambda: 1を実行するたびに、新しい関数オブジェクトが作成され、名前がfnにバインドされた古いオブジェクトが削除対象としてマークされます。しかし、Pythonはオブジェクトを単に割り当て解除するだけでなく、メモリをOSに戻します。メモリ割り当てのシステムコールを最小限に抑え、メモリの断片化を最小限に抑えるために、Pythonはできるだけメモリをリサイクルしようとします。そして、fn = lambda: 1を作成すると、インタープリタは、新しい関数オブジェクトに十分な大きさのRAMブロックを用意しているので、そのブロックを使用します。したがって、あなたの第3のfnはそのRAMのブロックで終わり、したがって、最初のfnと同じIDを持ちます。なぜなら、CPythonオブジェクトのidはそのメモリアドレスだからです。

（他は __hash__の特定の実装はCPythonの中のIDに基づいて提供されていません。クラスは __cmp__又は __eq__方法を定義していない場合、それは定義するべきではない任意のオブジェクトタイプのハッシュを述べたように __hash__操作）。

Answer 4

停止問題のスーパーセットであるため、2つの関数が等しいかどうかを判断することは不可能です。

関数を比較する（したがってハッシュする）のが理想的な世界では、型エラーが発生します。 Pythonは明らかにこれを好まず、代わりに関数のアイデンティティを使用してそれらを比較（したがってハッシュ）することを選択します。