2

ハッシュ テーブルは高パフォーマンスのマッピングであると想定されており、Python dict はハッシュ テーブルで実装されているため、高パフォーマンスでもあります。しかし、負の整数のハッシュ値を見ると、奇妙な結果に遭遇しました。

>>> for i in range(7):
...     print hash(i-4)
...     
-4
-3
-2
-2
0
1
2

しかし、これは明らかに辞書には影響しません:

>>> d = dict()
>>> d[-1] = 'foo'
>>> d[-2] = 'bar'
>>> d
{-2: 'bar', -1: 'foo'}

なぜこれが起こるのですか? また、辞書を使用しても影響を受けないのはなぜですか?

4

4 に答える 4

3

xとは異なるハッシュ値を持つという事実はy、x != y. しかし、その逆は正しくありません。したがって、xハッシュ値が等しい場合yでも、明示的に等しいかどうかがチェックされます。

と がハッシュ関数のコンテキストで衝突と呼ばれる状況でhash(x) == hash(y)あり、時々発生する可能性が高いものです。できるだけ避けたいと思いますが、一般的には避けられません。ハッシュ関数と衝突の詳細については、こちらを参照してください。x != y

于 2013-11-22T22:59:45.993 に答える
1

なぜ dicts が繰り返されるハッシュ値の影響を受けないのかを尋ねているのは、ハッシュテーブルが機能するためにハッシュ値が一意である必要がないからです。

Python は、整数のハッシュ値がそれ自体に解決される、整数の単純なハッシュを実装しています。-1 はハッシュ値の生成に失敗したことを知らせるために内部的に使用されるため、値 -1 は暗黙のうちに -2 に置き換えられます。これは同様に機能します。

于 2013-11-22T22:58:48.663 に答える
1

-1は C コードのエラー コードであり、代わりに C コード エラーを通知しないようにするため、ハッシュ関数はそれを返すことができません。C には例外がないため、Python 開発者はエラーを通知するために1 つの戻り値を確保する必要がありました。

辞書はハッシュだけを使用するわけではありません。また、等しいかどうかもテストします。ハッシュ テーブルは、可能なハッシュ値の数に比べて小さいことに注意してください。ハッシュ値が等しくない場合でも、同じスロットにマッピングされる可能性があります。ハッシュ値が同じスロットにマップされ、キーが等しくない場合、ハッシュは摂動され、新しいスロットが見つかります。

なぜなら-1 != -2、Python はまだ両方のキーを別々に保持しているからです。

ディクショナリでの Python のハッシュ関数のオーバーライドおよびディクショナリとセットの順序が任意である理由を参照してください。Python の辞書がハッシュを使用する方法の詳細については、 を参照してください。

于 2013-11-22T22:58:51.850 に答える
1

ハッシュ テーブルは、ハッシュ値が異なる場合にパフォーマンスが向上しますが、等しいハッシュ値を処理できます。これらはハッシュ衝突と呼ばれ、それらを処理する方法は、ハッシュ テーブルが最適化および調整される主要な方法の 1 つです。

hash(-1) == -2-1 は、C 実装でエラーを通知するために使用される特別な値であるためです。ハッシュ コードはその値を取ることができません。-1 のハッシュを与えるクラスを定義しようとすると、Python はそれを検出し、代わりに -2 を使用します。

于 2013-11-22T23:00:28.333 に答える