プログラムのダウンロード
「ダウンロード」から、JupyterLab で実行できるサンプルプログラムがダウンロードできます。ファイルは、ESET Endpoint Securityでウイルスチェックをしておりますが、ダウンロードとプログラムの実行は自己責任でお願いいたします。
ハッシュの計算
ハッシュの計算は、Pythonのデータ構造―特に集合や辞書―が高速な探索や操作を実現するための重要な仕組みです。これらのデータ構造は、各要素に対してハッシュ関数を適用し、その結果得られるハッシュ値をもとに専用のハッシュテーブル内に格納されます。ここでは、ハッシュがどのように計算されるか、どのような値がハッシュ可能（hashable）であるか、またハッシュ計算が利用される具体例について、図や表を交えて分かりやすく解説していきます。
１．ハッシュ計算の基本
Pythonでは、hash() 関数を使って、与えられた値からハッシュ値を計算することができます。ハッシュ値は整数で表され、主に集合や辞書のキーとして使われる値が一意に管理されるための目印となります。
1.1. ハッシュ可能な値と不可能な値
集合や辞書のキーとして使えるのは、ハッシュが計算できる―つまりイミュータブルな―値だけです。たとえば、数値、文字列、タプルなどはハッシュ可能ですが、リストや辞書などのミュータブルなオブジェクトはハッシュ計算ができません。
| オブジェクト | 例 | ハッシュ計算可能か |
|---|---|---|
| 数値 | 42 | 可能 |
| 文字列 | 'violet' | 可能 |
| タプル | (10, 20, 30) | 可能 |
| リスト | [10, 20, 30] | 不可能 |
| 辞書 | {'a': 1, 'b': 2} | 不可能 |
解説
- ハッシュ可能な値は不変であり、計算されたハッシュ値がオブジェクトの同一性の判定に利用されます。
- 例えば、タプル
(10, 20, 30)は変更不可能なため、hash((10, 20, 30))は整数を返しますが、リスト[10, 20, 30]に対してはTypeErrorが発生します。
1.2. hash() 関数の使用例
実際に hash() 関数を使って、さまざまな値のハッシュ値を計算してみましょう。
サンプルプログラム
# 文字列 'violet' のハッシュを計算
hash_violet = hash('violet')
print("hash('violet') =", hash_violet)
# 出力例: hash('violet') = 2826558983392317966 ※実行ごとに変わる可能性があります
# タプル (10, 20, 30) のハッシュを計算
hash_tuple = hash((10, 20, 30))
print("hash((10, 20, 30)) =", hash_tuple)
# 出力例: hash((10, 20, 30)) = 3952409569436607343
# リスト [10, 20, 30] のハッシュを計算（エラーになる）
try:
hash_list = hash([10, 20, 30])
except TypeError as e:
print("hash([10, 20, 30]) エラー:", e)
# 出力例: hash([10, 20, 30]) エラー: unhashable type: 'list'実行結果
hash('violet') = 2826558983392317966
hash((10, 20, 30)) = 3952409569436607343
hash([10, 20, 30]) エラー: unhashable type: 'list'解説
- 文字列
'violet'はイミュータブルなため、hash()関数でハッシュ値が計算されます。 - タプル
(10, 20, 30)も不変であるため、ハッシュ値が返されます。 - リストは変更可能なオブジェクトであるため、ハッシュ計算はサポートされず、エラーが発生します。
２．ハッシュ計算の利用例とその意義
ハッシュ計算は、集合や辞書が高速に要素の存在確認や検索を行うための基盤となっています。ここでは、ハッシュ計算が実際にどのように利用されるか、リストとの格納方法の違いとともに解説します。
2.1. リストと集合における格納方法の比較
値をリストに格納する場合、追加した順番に要素が格納されます。一方、集合はハッシュ関数により値のハッシュ値を計算し、その結果をもとにハッシュテーブル内の適切な位置に格納されます。たとえば、以下はリストとハッシュ法による集合への格納例です。
リストへの格納例
| [0] | [1] | [2] | [3] |
|---|---|---|---|
| violet | indigo | cyan | magenta |
集合への格納例
ここでは、ハッシュ関数として「文字列の文字数」を用い、ハッシュテーブルの領域を8個（0～7）と仮定します。
- "violet" は6文字 → ハッシュ値 6
- "indigo" は6文字 → ハッシュ値 6
- "cyan" は4文字 → ハッシュ値 4
- "magenta" は7文字 → ハッシュ値 7
図で表すと、
ハッシュテーブル（領域番号: 0～7）
-------------------------------------------------
領域0:
領域1:
領域2:
領域3:
領域4: 'cyan'
領域5:
領域6: 'violet', 'indigo'
領域7: 'magenta'
-------------------------------------------------解説
- リストは要素が順序通りに格納されるのに対し、集合はハッシュ値に基づいて格納先が決定されます。
- このため、集合では値の存在確認が直接ハッシュ値から領域を特定するため、ほぼ定数時間で行われます。
2.2. ハッシュ計算の意義と集合の制約
集合に値を格納するためには、値のハッシュが計算できなければなりません。したがって、変更可能なオブジェクト（リスト、辞書など）は集合に格納できず、タプルや文字列、数値などの不変オブジェクトのみが格納対象となります。また、ハッシュ関数によって算出されるハッシュ値は、プログラムの実行環境や再起動ごとに変化する場合があるため、その値自体を直接利用することはあまりありませんが、集合や辞書内部では重要な役割を果たしています。
解説
- 集合は高速な探索を可能にするためにハッシュ法を利用しており、ハッシュ計算ができる値のみが格納されます。
- そのため、集合や辞書のキーとして使用できるのは、変更不可能なデータ型に限られます。
まとめ
hash() 関数を利用して計算されるハッシュ値は、Pythonの集合や辞書が高速に要素を管理するための根幹をなす仕組みです。
- 基本概念： ハッシュ関数は、与えられた値から整数のハッシュ値を計算し、これをもとにハッシュテーブル内の格納先を決定します。
- ハッシュ可能な値： 不変なデータ型（数値、文字列、タプルなど）はハッシュ計算が可能ですが、リストなどのミュータブルな型は計算できません。
- 利用例： 集合はハッシュ値を利用して要素を格納し、探索時にほぼ定数時間で目的の値を見つけることができるため、リストと比較して非常に高速です。
このようなハッシュ計算の仕組みを理解することで、Pythonのみならず、他の多くのプログラミング言語におけるデータ構造の内部動作やパフォーマンス向上のための工夫についても深く理解できるようになります。