[Python] ハッシュ可能、不変


Answers

技術的には、ハッシュ可能とは、クラスが__hash __()を定義することを意味します。 ドキュメントによると:

__hash __()は整数を返さなければなりません。 唯一必要なプロパティは、equalを比較するオブジェクトが同じハッシュ値を持つことです。 何らかの形で、(例えば、排他的またはを使用して)オブジェクトの構成要素のハッシュ値を混在させて、オブジェクトの比較において部分的に再生することが推奨される。

私は、Pythonの組み込み型では、すべてのハッシュ可能な型も不変であると思います。 それにもかかわらず、__hash __()を定義する可変オブジェクトを持つことは困難ですが、おそらく不可能ではありません。

Question

最近のSOの質問( リストで索引付けされているPythonで辞書作成するを参照)から、私はおそらく、Pythonでハッシュ可能で不変なオブジェクトの意味について間違った概念があることに気付きました。

  • 実際にハッシュ可能な意味は何ですか?
  • ハッシュ可能と不可能の関係は何ですか?
  • ハッシュ可能な可変オブジェクトや、ハッシュ可能でない不変オブジェクトがありますか?



Pythonの用語集から:

オブジェクトは、生存期間中に決して変更されないハッシュ値(ハッシュ値は__hash __hash__()メソッドが必要)を持ち、他のオブジェクト( __eq__()または__cmp__()メソッドが必要)と比較することができます。 等しいを比較するハッシュ可能オブジェクトは、同じハッシュ値を持たなければなりません。

Hashabilityは、オブジェクトが辞書キーとセットメンバーとして使用できるようにします。これらのデータ構造はハッシュ値を内部的に使用するためです。

Pythonの不変の組み込みオブジェクトはすべてハッシュ可能ですが、変更可能なコンテナ(リストや辞書など)はありません。 ユーザ定義のクラスのインスタンスであるオブジェクトは、デフォルトでハッシュ可能です。 それらはすべて不等価であり、ハッシュ値はid()です。

Dictsとセットは、ハッシュテーブルの効率的な検索のためにハッシュを使用する必要があります。 ハッシュを変更するとデータ構造が壊れ、dictやsetが失敗するため、ハッシュ値は不変でなければなりません。 ハッシュ値を不変にする最も簡単な方法は、オブジェクト全体を不変にすることです。そのため、2つをよく一緒に言及する理由があります。

組み込みの変更可能なオブジェクトのどれもハッシュ可能ではありませんが、可変ではないハッシュ値を持つ変更可能なオブジェクトを作成することは可能です。 オブジェクトの一部だけがそのアイデンティティを表現するのは一般的ですが、オブジェクトの残りの部分は自由に変更できるプロパティを含んでいます。 ハッシュ値と比較関数がアイデンティティに基づいていて、変更可能なプロパティではなく、アイデンティティが決して変更されない限り、要件を満たしています。




変更不可能とは、オブジェクトが存続期間中に重要な形で変化しないことを意味します。 プログラミング言語ではあいまいだが一般的な考えです。

ハッシュ能力はわずかに異なり、比較を指しています。

ハッシュ可能オブジェクトは、生存期間中に変更されない__eq__() __cmp__()メソッドが必要です)ハッシュ値を持ち、他のオブジェクトと比較できます( __cmp__()メソッドまたは__cmp__()メソッドが必要)。 等しいを比較するハッシュ可能オブジェクトは、同じハッシュ値を持たなければなりません。

すべてのユーザー定義クラスには__hash__メソッドがあり、デフォルトではオブジェクトIDだけが返されます。 したがって、ハッシュ可能性の基準を満たすオブジェクトは必ずしも不変ではありません。

あなたが宣言した新しいクラスのオブジェクトは、たとえば__hash__から__hash__などしない限り、辞書キーとして使うことができます

オブジェクトの存続期間中にハッシュが変更された場合、オブジェクトが変更されたことを意味するため、すべての不変オブジェクトはハッシュ可能であると言うことができます。

しかし、それほどではない。 リスト(変更可能)を持つタプルを考えてみましょう。 タプルは不変であると言う人もいますが、同時にハッシュ可能ではありません(スロー)。

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

ハッシュ能力と不変性は、タイプではなくオブジェクトのインスタンスを参照します。 例えば、タプル型のオブジェクトは、ハッシュ可能であるかどうかを問わない。




Pythonでは、ほとんど互換性があります。 ハッシュは内容を表現することになっているので、オブジェクトと同じように変更可能であり、オブジェクトがハッシュ値を変更すると、dictキーとして使用できなくなります。

他の言語では、ハッシュ値はオブジェクトの「アイデンティティ」に関連しており、必ずしもその値には関係しません。 したがって、可変オブジェクトの場合、ポインタを使用してハッシングを開始することができます。 もちろん、オブジェクトがメモリ内で移動しないと仮定すると(GCのように)。 これは、例えばLuaで使用されるアプローチです。 これは、可変オブジェクトをテーブルキーとして使用可能にします。 初心者のためにいくつかの(不愉快な)驚きを作り出します。

最終的に、不変なシーケンス型(タプル)を持つことは、 '多値キー'にとってより良いものになります。