Python の場合、なぜ-1と-2両方が同じ番号にハッシュするのですか?
では、Python はこれら 2 つの数値をどのように区別するのでしょうか?
>>> -1 is -2
False
>>> hash(-1) is hash(-2)
True
>>> hash(-1)
-2
>>> hash(-2)
-2
質問する
3105 次
1 に答える
47
-1は、ハッシュ関数が のハッシュ値を生成できないようにする、CPython の C レベルでの予約値です-1。DSM で指摘されているように、同じことは IronPython と PyPy では当てはまりませんhash(-1) != hash(-2)。
このQuoraの回答を参照してください：
C 拡張モジュールで型を記述して
tp_hashメソッドを提供する場合は、回避する必要があり-1ます — を返す-1と、Python はエラーをスローするつもりであると見なします。純粋な Python でクラスを作成して
__hash__メソッドを提供する場合、ありがたいことに、そのような要件はありません。しかし、それはメソッドを呼び出す C コードがそれ__hash__を行うため です。__hash__-1hash()-2
これは本当にeffbotからの情報を再パッケージ化するだけです:
ハッシュ値
-1は予約されています (C 実装でエラーのフラグを立てるために使用されます)。ハッシュ アルゴリズムがこの値を生成する場合は、単に-2代わりに使用します。
これもソースで確認できます。たとえば、Python 3 のintオブジェクトの場合、これはハッシュ実装の最後にあります。
if (x == (Py_uhash_t)-1)
x = (Py_uhash_t)-2;
return (Py_hash_t)x;
では、Python はこれら 2 つの数値をどのように区別するのでしょうか?
すべてのハッシュ関数は大きな入力空間を小さな入力空間にマップするため、ハッシュ関数がどれほど優れていても、常に衝突が予想されます。たとえば、文字列のハッシュについて考えてみましょう。ハッシュ コードが 32 ビット整数の場合、2^32 (40 億強) のハッシュ コードがあります。長さ 6 のすべての ASCII 文字列を考慮すると、入力スペースには (2^7)^6 (4.4 兆弱) の異なる項目があります。このセットだけで、どんなに上手でも、たくさんの衝突が保証されます。これに Unicode 文字と無制限の長さの文字列を追加してください!
したがって、ハッシュコードはオブジェクトの場所を示唆するだけであり、同等性テストが続いて候補キーをテストします。ハッシュ テーブル セットにメンバーシップ テストを実装するために、ハッシュ コードは、値を検索するための「バケット」番号を提供します。ただし、ハッシュコードが同じ設定項目はすべてバケット内にあります。このためには、バケット内のすべての候補を区別するための等価テストも必要です。
このハッシュ コードと等価性の二重性は、CPython のドキュメント on hashable objectsで示唆されています。他の言語/フレームワークでは、カスタム ハッシュ コード関数を提供する場合は、カスタム等価テスト (ハッシュ コード関数と同じフィールドで実行) も提供する必要があるというガイドライン/ルールがあります。
実際、今日の Python リリースはまさにこれに対処しており、サービス拒否攻撃としてこれ (同一のハッシュ値ですが、大規模に) が使用された場合の効率性の問題に対処するセキュリティ パッチがあります - http://mail.python.org /pipermail/python-list/2012-April/1290792.html
于 2012-04-12T19:34:23.837 に答える