等しいとは何か — == とハッシュの約束 — どの言語にもある仕組み — 値・型・数・文字・エラー・メモリ・並行

リクエストがアプリケーションに届くまで

ブラウザURL入力
DNS名前→IP
ルータ経路選択
ロードバランサ振り分け
Nginx受け口
アプリ処理今ここ
DB保存

同じ書き方でも、何が起きるかはその言語が約束した分しか決まっていません。今回は「等しい」の約束と、それに頼る集合・辞書を見ます。

まず結論

集合や辞書は、鍵をまずハッシュ値で探す場所を決め、その場所で == で比べます。だから Python と Rust の文書は「等しいものは同じハッシュ値を持つ」を、鍵に使う型の要件として書いています。

この約束は型の作り手が守るものです。Python の set と Go の map で破ってみると例外は出ず、ハッシュ値が途中で変わった鍵や自分自身と等しくない NaN が、入っているのに見つからなくなりました。

? 読む前に予測

Python で、属性 x からハッシュ値を計算するクラスのオブジェクト q を set に入れ、そのあと q.x を書き換えました。同じ q について `q in s` はどうなるでしょうか。

当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。

抽象原理

集合は、2段階で鍵を探している

集合や辞書で x in s と書くと、処理系は全要素を1つずつ比べてはいません。第11期『平均O(1)が置いている仮定 — ハッシュ表は魔法ではない』で見たとおり、鍵のハッシュ値からバケットを決め、そのバケットの中だけで比べます。

ここから、2つの操作の間に約束が要ります。等しい2つの鍵が別々のハッシュ値を持てば、比べる前に別のバケットへ行ってしまうからです。Python の Data model はこう書きます。

The only required property is that objects which compare equal have the same hash value

Rust の std も同じ性質を式で書き、依存している側を名指しします。

k1 == k2 -> hash(k1) == hash(k2)

In other words, if two keys are equal, their hashes must also be equal. HashMap and HashSet both rely on this behavior.

HashMap の文書は、破ったときの扱いも書きます。Violating this property is a logic error. に続けて、結果をこう定めます。

The behavior resulting from either logic error is not specified, but will be encapsulated to the HashMap that observed the logic error and not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.

もう1つ、時間の条件があります。Python の用語集は hashable を a hash value which never changes during its lifetime を持つもの、と定義します。入れたときと探すときでハッシュ値が違えば、行き先のバケットも違います。

鍵を探す2段階と、それぞれが頼っている約束

探したい鍵 kx in s / m[k]

1段目: ハッシュ値で場所を決める

バケット等しい鍵は同じハッシュ値、の約束に頼る

2段目: その場所で比べる

== で一致を判定自分と等しい(a == a)、の約束に頼る

・どちらの約束も型の作り手が守るもの。Python の set と Go の map は、破られても例外を出さなかった(実測)
・破れると、入っているのに見つからない、同じ鍵が2件入る、が起きる

Python は、片方だけ定義する事故は防ぎます。__eq__ を定義して __hash__ を定義しないクラスは、__hash__ が None になります。

A class that overrides eq() and does not define hash() will have its hash() implicitly set to None.

実測でも print(P.__hash__) は None で、文書はハッシュ値を求めると TypeError になると書きます。防げないのは、両方を定義したうえで約束を破る場合です。

具体実物

入れたあとに鍵を書き換える

x からハッシュ値を作るクラスを、集合に入れてから書き換えます。以下の実演はすべて Docker 上の aarch64 コンテナで、Python 3.14.7 / Node v24.21.0 / Go 1.27.1 / rustc 1.98.1 を使い、2回実行して同じ出力でした。

class Q:
    def __init__(self, x): self.x = x
    def __eq__(self, o): return self.x == o.x
    def __hash__(self): return hash(self.x)
q = Q(1); s = {q}; q.x = 2
print(Q(2) in s, Q(1) in s, q in s, len(s))

Python 3.14.7 の出力(上のコードを含む実演全体。3行目がこのコードの行)コマンド出力

False True False True True
None
False False False 1
{1: 'bool'}

3行目は左から Q(2) in s・Q(1) in s・q in s・len(s) です。同じオブジェクト q が見つかりません。 要素数は 1 のままです。

Python の in は x in y is equivalent to any(x is e or x == e for e in y) と定義され、同一なら等価を問わず真のはずです。それでも False になるのは、同一かどうかを比べる前に、ハッシュ値で別の場所へ行っているからです。「等価だが見つからない」のではなく**「同一なのに見つからない」**のです。

追加の実験で x を 1 に戻すと、また見つかりました。

Python 3.14.7 の追加実験の出力(該当2行)コマンド出力

after q.x=2: q in s -> False
after q.x=1 again: q in s -> True

これは set の不具合ではありません。Data model はこの場合をはっきり書いています。

If a class defines mutable objects and implements an eq() method, it should not implement hash(), since the implementation of hashable collections requires that a key’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket).

Q はこの助言に反した型です。約束を破った結果が、この実演では例外ではなく「見つからない」という形で出た、と読みます。

✓ ここまでの確認

書き換えで見つからなくなった q について、x を元の値 1 に戻すと `q in s` は True に戻りました。ここから言えることはどれですか。

抽象原理

「自分と等しい」が成り立たない値

もう片方の約束は、== そのものが「等しい」らしく振る舞うことです。Rust は Eq の条件に reflexive: a == a を挙げ、続けてこう書きます。

Floating point types such as f32 and f64 implement only PartialEq but not Eq because NaN != NaN.

Python の文書は not-a-number values are not equal to themselves と書いてこれを compliant with IEEE 754 とし、Go の仕様も浮動小数点を compared as defined by the IEEE 754 standard とします。つまり NaN は、2段目の比較で自分自身に一致しない鍵です。

言語はこれに別々の答えを出しています。Rust は f64 を鍵の型として受け付けません。JavaScript は「等しい」を複数用意しました。ECMA-262 の === (IsStrictlyEqual)は NaN なら false を返し、SameValue は treating all NaN values as equivalent and by differentiating +0𝔽 from -0𝔽、つまり NaN どうしを等しく、+0 と -0 を別に扱います。SameValueZero は +0 と -0 を同じに扱います。includes は SameValueZero を使うと明記されています。

具体実物

NaN を鍵にした4言語

同じ「NaN を鍵にする」を4言語で並べます。まず JavaScript です。

console.log(NaN === NaN, Object.is(NaN, NaN), 0 === -0, Object.is(0, -0));
console.log([NaN].includes(NaN), [NaN].indexOf(NaN));
const m = new Map([[NaN, "n"]]); console.log(m.get(NaN), new Set([0, -0]).size);

Node v24.21.0 の出力(実演の4行のうち上の3行ぶん)コマンド出力

false true true false
true -1
n 1

includes と indexOf で答えが割れるのは、仕様が includes に using the SameValueZero algorithm、indexOf に using the IsStrictlyEqual algorithm を指定しているからで、実装の癖ではありません。実測では Map は NaN の鍵を引け、Set は 0 と -0 を1件にまとめます。1行目の 0 === -0 は true、Object.is(0, -0) は false です。よく言われる「=== は型と値が一致すれば真」は、NaN と +0/-0 の扱いを除けばそのまま成り立ちます。

Python の dict では、同じ NaN オブジェクトなら見つかり、別に作った NaN は見つかりません。in が同一性で先に真になるためです。

Python 3.14.7 の追加実験の出力(d = {nan: 1} で検索)コマンド出力

nan in {nan:1}: True | float('nan') in d: False

Go では、同じ変数 n で引いても見つかりません。

m := map[float64]int{}
n := math.NaN()
m[n] = 1; m[n] = 2

Go 1.27.1 の出力(len・参照・delete・range を足した追加実験)コマンド出力

len 2 m[n] 0 n==n false
lookup ok false
after delete len 2
range: NaN 1
range: NaN 2

同じ変数 n で2回代入して 2件。引けば 0、delete も効かず、range で回すと2件とも見えます(range の順序は仕様上決まっていません)。Rust で HashSet に f64 を入れようとすると、実行する前に止まります。

rustc 1.98.1 の出力(エラー見出しの行だけを抜粋)コマンド出力

error[E0277]: the trait bound `f64: Eq` is not satisfied
error[E0277]: the trait bound `f64: Hash` is not satisfied
error: aborting due to 2 previous errors

✓ ここまでの確認

Go 1.27.1 で map[float64]int に NaN を鍵として2回代入すると、len は 2 になり、m[n] は 0、delete しても 2 件のままでした。この結果の根拠として言えるのはどれですか。

⇄ 2つを見比べる

具体例 A

Python: 入れたあとにハッシュ値が変わる

1段目が崩れた例。q はずっと集合の中にあるが、書き換え後のハッシュ値は別の場所を指すので、同じオブジェクトでも見つからない。値を戻せば見つかる。

Python 3.14.7コマンド出力

after q.x=2: q in s -> False
after q.x=1 again: q in s -> True

具体例 B

Go: 自分と等しくない鍵

2段目が崩れた例。同じ n で代入しても既存の鍵と一致しないので2件目が入り、引いても消しても当たらない。仕様に NaN 鍵の明文は無く、== の定義から出る結果。

Go 1.27.1コマンド出力

len 2 m[n] 0 n==n false
after delete len 2

壊れ方は違うのに、どちらも黙っています。2つに共通する原因は何でしょうか。

図の2段階のうち、どちらの段で食い違ったかを当てはめてみてください。

実務の場面エージェントが『キャッシュの鍵にするため __hash__ を追加しました』と報告してくる

生成された差分が、注文クラスに __eq__ と __hash__ を足し、ハッシュ値を id と status から計算していたとします。報告は「辞書の鍵に使えるようになり、テストも通過」。

テストが通るのは、入れた直後に引いているからかもしれません。確かめるのは、status が鍵として辞書に入ったあとで書き換わるかです。書き換わるなら、今回の Q と同じく「入っているのに見つからない」が起き、キャッシュは静かに当たらなくなります。例外は出ないので、ログにも残りません。

ハッシュ値の計算には、鍵として使っている間に変わらない属性だけを使っているか。差分を読むときはそこを見ます。

この章のまとめ

集合・辞書は ハッシュ値で場所を決め、そこで == で比べる。2つの約束に頼っている。
1つ目は 等しいなら同じハッシュ値で、生存中に変わらないこと。Python と Rust の文書が要件として書く。
Python の Q は入れたあとの書き換えで 同一なのに見つからない。戻せば見つかる。
2つ目は a == a。NaN はこれを満たさない。Go は NaN 鍵が2件になり、引けも消せもしない。
JavaScript は「等しい」を複数持ち、includes と indexOf で答えが違うのは仕様の指定。Rust は f64 を鍵に取らずコンパイル時に止める。
Python の set と Go の map では、約束の破れは 例外ではなく「見つからない」 で現れた。Rust の HashMap 文書は結果を未規定とし、panic も含みうると書く。

自分の現場で確かめる

読んだだけでは身につきません。手元の環境で実際に見てみてください。

環境:

自分のコードで、ハッシュ値を自前で定義しているクラスを探し、その計算に後から書き換わる属性が入っていないか見るWindowsでは確認できません。この項目はLinux/WSLで試してください。
浮動小数点数を辞書や集合の鍵にしている箇所を探し、NaN が入りうる経路(割り算・外部入力の変換)が無いかを確かめる

理解度チェック

読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。

問題 1 / 3正解: 0

JavaScript で `[NaN].includes(NaN)` は true、`[NaN].indexOf(NaN)` は -1 になります。この違いの説明として正しいのはどれですか。

用語集(4語)

等価と同一性: 等価は == が真になること、同一性は同じオブジェクトであること(Python の is)。Python の in は「同一か、または等価」で判定する。
ハッシュ値: 値から計算する整数で、集合や辞書が探す場所を決めるのに使う。等しい値は同じハッシュ値を持たねばならず、生存期間中に変わってはならない。
反射律: どの a についても a == a が成り立つこと。Rust の Eq はこれを求める。IEEE 754 の NaN はこれを満たさない。
SameValueZero: ECMA-262 の比較アルゴリズムの1つ。NaN どうしを等しいとみなし、+0 と -0 も等しいとみなす。includes や Map・Set の鍵の実測結果と合う。

等しいとは何か — == とハッシュの約束