69

私は辞書のキーとしてファンキーなものを頻繁に使用しているので、それを行う正しい方法は何か疑問に思っています。これは、オブジェクトに適切なハッシュメソッドを実装することで実現します。ハッシュを実装する良い方法のようにここで尋ねられる他の質問を知っています__hash__が、カスタムオブジェクトに対してデフォルトがどのように機能するか、そしてそれを信頼できる かどうかを理解したいと思います。

エラーが発生するため、可変変数は明示的にハッシュ不可であることに気付きhash({})ました...しかし、奇妙なことに、カスタムクラスはハッシュ可能です：

>>> class Object(object): pass
>>> o = Object()
>>> hash(o)

それで、このデフォルトのハッシュ関数がどのように機能するかを誰かが知っていますか？これを理解することで、私は知りたいです：

辞書のキーと同じタイプのオブジェクトを配置する場合、このデフォルトのハッシュを信頼できますか？例：

key1 = MyObject()
key2 = MyObject()
key3 = MyObject()
{key1: 1, key2: 'blabla', key3: 456}

辞書のキーとしてさまざまなタイプのオブジェクトを使用する場合、それを信頼できますか？例えば

{int: 123, MyObject(10): 'bla', 'plo': 890}

そして最後のケースでも、カスタムハッシュが組み込みハッシュと衝突しないようにするにはどうすればよいですか？例：

{int: 123, MyObject(10): 'bla', MyObjectWithCustomHash(123): 890}
4

6 に答える 6

39

信頼できるもの：カスタムオブジェクトにはhash()、オブジェクトのIDに何らかの方法で基づくデフォルトがあります。つまり、デフォルトのハッシュを使用するオブジェクトは、その存続期間中そのハッシュに対して一定の値を持ち、異なるオブジェクトは異なるハッシュ値を持つ場合と持たない場合があります。

id()によって返される値とによって返される値の間の特定の関係に依存することはできませんhash()。Python 2.6以前の標準C実装では、Python 2.7〜3.2でも同じでしhash(x)==id(x)/16た。

編集：元々、リリース3.2.3以降または2.7.3以降ではハッシュ値がランダム化される可能性があり、Python3.3では関係が常にランダム化されると書いています。実際、現在のところランダム化はハッシュ文字列にのみ適用されるため、実際には16による除算の関係は今のところ維持される可能性がありますが、それに頼らないでください。

ハッシュの衝突は通常重要ではありません。オブジェクトを見つけるための辞書ルックアップでは、同じハッシュを持ち、同等に比較する必要があります。衝突が問題になるのは、サービス拒否攻撃など、最近のバージョンのPythonがハッシュ計算をランダム化できるようになった衝突の割合が非常に高い場合のみです。

于 2012-07-04T07:57:11.817 に答える
13

ドキュメントには、カスタムオブジェクトが実装id()として依存していると記載されています。hash()

CPython実装の詳細：これは、メモリ内のオブジェクトのアドレスです。

カスタムオブジェクトをそのような組み込み型と混合する場合int、それらはハッシュ衝突である可能性がありますが、それらが均等に分散されていれば、それはまったく問題ありません。パフォーマンスの問題が実際に発生しない限り、あまり調査しないでください。

于 2012-07-04T07:33:56.183 に答える
13

Python 3では、次の関数がオブジェクトのobjectに対してのサブクラスで使用されid()ます（からpyhash.c）

Py_hash_t
_Py_HashPointer(void *p)
{
    Py_hash_t x;
    size_t y = (size_t)p;
    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
       excessive hash collisions for dicts and sets */
    y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));
    x = (Py_hash_t)y;
    if (x == -1)
        x = -2;
    return x;
}

SIZEOF_VOID_P64ビットPythonの場合は8、32ビットPythonの場合は4です。

>>> class test: pass
...
>>> a = test()
>>> id(a)
4325845928
>>> hash(a)
-9223372036584410438

ハッシュは、符号付き整数に対してビット演算が実行されるid(a)式を使用して計算されていることがわかります。たとえば、上記で定義されている場合：(id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4))Ca

>>> import numpy
>>> y = numpy.array([4325845928], dtype='int64')
>>> SIZEOF_VOID_P = 8
>>> (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4))
array([-9223372036584410438])

ビット単位の演算がCの場合と同じように動作するように使用していることに注意してくださいnumpy.array(dtype='int64')（Python intで同じ演算を実行すると、オーバーフローしないため、異なる動作が得られます）。https://stackoverflow.com/a/5994397/161801を参照してください。

于 2015-11-06T17:31:19.613 に答える
9

ユーザー定義クラスのデフォルトのハッシュは、IDを返すだけです。これにより、多くの場合役立つ動作が得られます。ユーザー定義クラスのインスタンスをディクショナリキーとして使用すると、値を検索するためにまったく同じオブジェクトが再度提供されたときに、関連付けられた値を取得できます。例えば：

>>> class Foo(object):
    def __init__(self, foo):
        self.foo = foo


>>> f = Foo(10)
>>> d = {f: 10}
>>> d[f]
10

これは、ユーザー定義クラスのデフォルトの同等性と一致します。

>>> g = Foo(10)
>>> f == g
False
>>> d[g]

Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    d[g]
KeyError: <__main__.Foo object at 0x0000000002D69390>

fとgの属性の値が同じであっても、それらは等しくなく、で検索gしdても、の下に格納されている値が見つからないことに注意してくださいf。さらに、の値を変更しても、をf.foo検索fするdと次の値が見つかります。

>>> f.foo = 11
>>> d[f]
10

プログラマーがとを定義することによって2つのインスタンスが同等として扱われるための条件を明確に宣言しない限り、任意の新しいクラスのインスタンスは非同等として扱われるべきであるという前提があり__eq__ます__hash__。

そして、これはほとんど機能します。クラスを定義する場合Car、おそらく、同じ属性を持つ2台の車が2台の異なる車を表していると見なします。車を登録所有者にマッピングする辞書を持っている場合、アリスとボブが同じ車を所有している場合でも、ボブの車を検索するときにアリスを見つけたくありません。OTOH、郵便番号を表すクラスを定義する場合、同じコードを持つ2つの異なるオブジェクトを「同じ」ものの交換可能な表現と見なしたいと思うでしょう。この場合、郵便番号を州にマッピングする辞書があれば、同じ郵便番号を表す2つの異なるオブジェクトで同じ状態を見つけられるようにしたいと思います。

これを「値型」と「オブジェクト型」の違いと呼んでいます。値型はある値を表します。それは私が気にする値であり、個々のオブジェクトのIDではありません。同じ値を考え出す2つの異なる方法は同じように優れており、値型を渡すコードの「コントラクト」は通常、特定のオブジェクトを指定せずに、何らかの値を持つオブジェクトを提供することを約束します。オブジェクトタイプOTOHの場合、別のインスタンスとまったく同じデータが含まれている場合でも、個々のインスタンスには独自のIDがあります。オブジェクトタイプを渡すコードの「コントラクト」は、通常、正確な個々のオブジェクトを追跡することを約束します。

では、組み込みの可変クラスがIDをハッシュとして使用しないのはなぜですか？これは、それらがすべてコンテナーであるためです。通常、コンテナーは値型に似ていると見なされ、その値は含まれている要素によって決定されます。

>>> [1, 2, 3] == [1, 2, 3]
True
>>> {f: 10} == {f: 10}
True

ただし、可変コンテナの値は一時的です。一部の特定のリストには現在値がありますが、値[1, 2, 3]をに変更することができます[4, 5, 6]。リストを辞書キーとして使用できる場合は、ルックアップでリストの（現在の）値を使用するか、そのIDを使用するかを決定する必要があります。いずれにせよ、現在辞書キーとして使用されているオブジェクトの値が変更されて変更された場合、（非常に）驚かされる可能性があります。オブジェクトを辞書キーとして使用することは、オブジェクトの値がそのIDである場合、またはオブジェクトのIDがその値と無関係である場合にのみうまく機能します。したがって、Pythonが選択した答えは、可変コンテナをハッシュ不可と宣言することです。

さて、あなたの直接の質問に答えるためのより具体的な詳細：

1）CPythonのこのデフォルトハッシュ（他の回答/コメントによると明らかに<2.6のみ）はオブジェクトのメモリアドレスにマップされるため、CPythonでは、両方が同時にライブであるデフォルトハッシュを使用する2つのオブジェクトが衝突する可能性はありません関係するクラスに関係なく、ハッシュ値（および、辞書キーとして格納されている場合はライブ）。また、ハッシュとしてメモリアドレスを使用しない他のPython実装では、デフォルトのハッシュを使用してオブジェクト間で細かいハッシュ分散を行う必要があることも期待します。そうです、あなたはそれに頼ることができます。

2）カスタムハッシュとして、既存のオブジェクトのハッシュとまったく同じ結果を返さない限り、比較的問題はありません。私の理解では、Pythonのハッシュベースのコンテナーは、完全に縮退していない限り、次善のハッシュ関数に対して比較的寛容です。

于 2012-07-04T08:05:53.483 に答える
4 
>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
True

関数IDを参照してください

于 2012-07-04T07:30:18.263 に答える
-3 
>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
False
>>> hash(c) == id(c)/16
True

16で割るとTrueになります

于 2015-08-27T09:17:30.433 に答える