Pythonではキー・バリュー型の変数として辞書(Dict)が提供されています。他の言語では連想配列などと呼ばれるものです。
辞書型ではキーを与えると、非常に高速に該当する値を検索できます。これは内部でハッシュ(Hash)という仕組みを使うことで可能になっています。
今回はハッシュとはどんなものか、Pythonの辞書でハッシュを使っている背景について解説しています。Python使いは必ず知っておくべき内容なので、ぜひ参考にしてみてください。
Pythonの辞書(ハッシュテーブル)の基本
Pythonの辞書型(dict)の変数を定義するには、次のように初期化します。
d = {'foo': 10, 'bar': 20, 'baz': 30}
この場合例えばキー'foo'に対応する値は10です。
キー'bar'に対応する値を取り出すには、キーをブラケット [ ]
で囲んで指定します。
print(d['bar'])
# 20
存在しないキーを指定すると KeyError
になります。
print(d['qux'])
# KeyError: 'qux'
ハッシュ関数の理解
Pythonの辞書で、あるキーに対応する値を取得するときに、内部ではハッシュを使って検索しています。
ハッシュ関数は、あるデータから一定の長さの要約値(ハッシュ、ハッシュ値とも)を計算するもの。
簡単にハッシュの特徴を挙げると、
- どんな長さのデータでも一定の長さのハッシュ値になる
- 少しでも違うデータは、まったく異なるハッシュ値になる
- あるハッシュ値になる元データを探すのがほぼ無理(極めて難しい)
- 2つの元データが同じハッシュ値になるような組み合わせを探すのがほぼ無理
ハッシュ関数として使われているアルゴリズム(手続き)は様々なものがありますが、どれも上の条件を満たしています(強度の差はあります)。本来ハッシュは、こうした特性を活かして、暗号化通信や電子署名、改ざん防止、ブロックチェーンなどにも使われています。
Pythonの辞書では、わずかでも異なるデータから全く違うハッシュ値が得られるというハッシュ関数の特性を生かして、キーの検索に活用されています。膨大なキーセットがあるときには、純粋に全件が完全に一致するか検査していると非常に時間がかかってしまいます。そこで、キーの一致を検索するにあたり、まずハッシュ値の一致を確認するという手続きにすれば、膨大なデータがあっても検索時間を短くできます。多少簡単化していますが、Pythonの辞書はこのような仕組みでキーを検索します。
実際のハッシュ関数の働きを見てみましょう。
組み込み関数 hash()
にデータを渡せば、キーに対応するハッシュ値が取得できます。
print(hash('foo'))
# 5372323968714251564
print(hash('bar'))
# 361402331357956622
※ハッシュ値は実行するインタープリタにより異なる値になります。
もちろん、文字列が異なればハッシュ値も全く違うものになります。
print(hash('hello, world'))
# -8271668633989926866
print(hash('hello, world!'))
# 1506371952106975238
また数値データの場合、異なる変数型でも同値ならハッシュも等しくなります。
a = 10
print(type(a))
# <class 'int'>
print(hash(a))
# 10
b = 10.0
print(type(b))
# <class 'float'>
print(hash(b))
# 10
そのため、辞書でキーとしてint型を指定してもfloat型を指定しても、同値(1==1.0
)ならキーも同じものとして扱われます。
d = {1.0: 'a'}
print(d[1])
# a
また、listやdictなどは辞書のキーとしては使えません。
これらのオブジェクトはハッシュ不能(unhashable)です。リストや辞書は要素を自由に変更可能(mutable)ですから、固有のハッシュ値を得ることができません。そのためlistやdictは辞書のキーとして使えないのです。
ハッシュ値を求めようと hash()
に渡してもTypeError
となります。
l = [1, 2, 3]
# hash(l)
# TypeError: unhashable type: 'list'
d = {'a': 1, 'b': 2}
# hash(d)
# TypeError: unhashable type: 'dict'
一方、タプル(tuple)型はハッシュ可能オブジェクトです(ハッシュ値が取得できる)
そのため、辞書のキーとしても使えるのです。
t = (1, 2, 3)
print(hash(t))
# 529344067295497451
PythonでMD5/SHAハッシュを取得
Pythonの辞書型のキーを求める組み込み関数 hash()
がハッシュ値を算出するアルゴリズムは実装を見てみないと分かりません。
よく使われているハッシュアルゴリズム SHA-2 や MD5 で計算するにはどうしたらいいでしょうか?
これらの有名なアルゴリズムでハッシュを計算するには hashlib を用います。
別途インポートは必要ですが、標準ライブラリなのでインストールは不要。
import hashlib
各アルゴリズムを利用するには、まずデータをバイト列に変換(str.encode()
メソッドなど)します。その値をhashlib.md5()
、hashlib.sha256()
などに渡してHashオブジェクトを取得します。
取得したハッシュ値を文字列で取得するには Hash.hexdigest()
を呼び出します。
s = 'hoge'
h = hashlib.md5(s.encode())
print(h.hexdigest())
# ea703e7aa1efda0064eaa507d9e8ab7e
h = hashlib.sha256(s.encode())
print(h.hexdigest())
# ecb666d778725ec97307044d642bf4d160aabb76f56c0069c71ea25b1e926825
hashlib で利用できるハッシュアルゴリズムの一覧を取得するには、 hashlib.algorithms_guaranteed
にアクセスします。
# すべてのプラットフォームでサポートされていることが保証されるハッシュアルゴリズムの名称セット
print(hashlib.algorithms_guaranteed)
# {'blake2b', 'sha3_256', 'sha256', 'sha3_224', 'sha512', 'sha3_512', 'shake_256', 'sha3_384', 'shake_128', 'sha1', 'sha384', 'sha224', 'blake2s', 'md5'}
# 実行中の Python インタープリタで利用可能なハッシュアルゴリズムの名称セット
print(hashlib.algorithms_available)
# {'sha3_512', 'shake_256', 'sha3_384', 'sha256', 'sha512_224', 'sha512', 'whirlpool', 'sha512_256', 'sha3_224', 'sha224', 'ripemd160', 'blake2b', 'sha3_256', 'sm3', 'md4', 'sha1', 'sha384', 'md5-sha1', 'shake_128', 'blake2s', 'md5'}
Pythonの学習法について
Python の勉強が辛くなっていませんか?
Pythonは比較的取り組みやすい言語と言われていますが、プログラミング初心者にとっては分からないことだらけ。
ゼロから独学で勉強するのは厳しい道のりです。
今回、様々な現場、システム、言語を経験してきた現役エンジニアの立場から、初心者でも挫折しない学習方法を解説する記事を書きました。もちろん、お金をかけずに習得できる方法も解説しています。
できるだけストレスがかからない勉強法を解説しているので、ぜひ参考にしてみてくださいね。
今回参考にしたページ・資料
組み込み関数 — Python 3.10.0b2 ドキュメント
hashlib --- セキュアハッシュおよびメッセージダイジェスト — Python 3.10.0b2 ドキュメント