Pythonのset型について勉強しております。

Question

set型について勉強しています。下記の文章で分からない事がありますので教えてください。

setの注意点 「TypeError unhashable type」
また、格納するオブジェクトはハッシュ化可能(≒イミュータブル)でなければなりません。これは、setは要素のユニークさを判定する際にハッシュ値を利用するためです。例えばlistはハッシュ化可能ではないためセットに挿入することはできません。TypeError unhashable typeが発生します。

s = {'A', [1, 2, 3]}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

ハッシュ化可能なタプルを利用すれば解決します。

s = {'A', (1, 2, 3)}
print(s) # {'A', (1, 2, 3)}

【質問】

「ハッシュ化」や「ハッシュ値」という言葉が出てきますが、「ハッシュ」とはどのような意味でしょうか？

Answer 1

任意のデータから一意に計算される数値のことです。

ハッシュ関数さえ定義してしまえばリストのハッシュ値を求めることも可能ですが、
可変(ミュータブル)なオブジェクトのハッシュ値は扱いづらいので避けられています。

集合ではなく辞書についてのFAQですが、次のページも参考になるでしょう。
デザインと歴史 FAQ - なぜ辞書のキーはイミュータブルでなくてはならないのですか？

---

集合の実装の文脈で解釈するなら、『粗く分ける』ためにハッシュ値を使っています。

例えばトランプを整理するとき、スート(マーク)別に分けたりしますよね。それと似ています。
一つ一つ値をチェックするより、まず粗くアタリを付けた方が効率的です。(註)

註記

前段の説明には説明の為のウソがあります。

トランプをスートで分類するときは、四値(+1)に分かれるハッシュ値を扱うことになりますが、
普通はこんなに狭い表現力しか無いようなハッシュ関数は使いません。

実際にはハッシュは衝突しないように扱うのが理想的であり、
また少数のデータを扱ったときに衝突することはあまりありません。

Answer 2

概念的には「同じ値なら（別のオブジェクトでも）同じhash値を持つ」ものだと思ってください。

>>> a = (1,2,3)
>>> b = (1,2,3)
>>> c = (2,3,4)
>>> id(a)
139975907796672
>>> id(b)
139975907839144
>>> id(c)
139975907839216
>>> hash(a)
2528502973977326415
>>> hash(b)
2528502973977326415
>>> hash(c)
3789705017596477050

https://docs.python.org/ja/3/library/functions.html#hash

Answer 3

「ハッシュ」ってどんな意味？