Python Tech 辞書

Python 辞書 dictで使われるハッシュとは?キーから値を検索するハッシュテーブル

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 ドキュメント

 

  • この記事を書いた人

次世代ペンギン

長いのでペンギンとお呼びください。システム開発・プログラミングのお仕事をしています。甘味とコーヒーは生命線。多くの人に役立つ情報のシェアが目標です。

人気の記事

1

会社員でプログラマーとして働いている人、インフラやネットワークのエンジニアとして働いている人の中には、フリーランスのプログラマーとして独立、もしくは転向したい人もいるので ...

2

キャリアアップのため、または高収入を目指して、しっかりプログラミングを学びたいという人が増えてきましたね。 この記事では現役のエンジニアである私が、実際に仕事で稼げるよう ...

3

フリーランスのプログラマーにとって収入の向上に最も直結するのはスキルです。 必要なスキル、スキルの獲得方法が気になる人も多いでしょう。 また、これからフリーランスを目指す ...

4

Vuetifyの v-progress-circular コンポーネントは、数値データや処理状況を環状(円状)のデザインで教えてくれるUIデザインです。 ローディングのス ...

5

Vuexのstore(ストア)を使うと、各コンポーネント間で個別にデータのやり取りすることなく、データを一元的に管理できます。Vueでは欠かせない機能といえるでしょう。 ...

-Python, Tech, 辞書
-, , ,

© 2021 ペンギンのーと