この記事を書くきっかけ
放送大学で「データ構造の基礎」という講義を受講しています。第10回、第11回のハッシュに関する講義を視聴したところ、内容は分かりやすかったのですが、ハッシュというものについてよくわからない部分もあったので、自分の理解のために記事にしてみました。ハッシュについて、できるだけ分かりやすくまとめたつもりです。
こちらの書籍もおすすめです→Pythonで学ぶアルゴリズムの教科書
なぜハッシュを学ぶのか
ハッシュを用いるとデータに高速にアクセスしたり、データを保持する領域やメモリを少なく抑えることができます。データ構造としての利用だけでなく、ハッシュは情報セキュリティの分野やブロックチェーン技術でも利用されています。
ハッシュ値を求める理由
1. データの高速な検索・挿入・削除
ハッシュテーブルは、データのキーをハッシュ値に変換し、そのハッシュ値を使ってデータを格納します。これにより、データの検索、挿入、削除の操作が平均してO(1)の計算量で実行できます。特に大量のデータを扱う際に非常に効率的です。
2. データの整合性確認
ハッシュ値は、データが変更されていないか確認するために使用されます。例えば、ファイルの内容が正しいかを確認するために、そのファイルのハッシュ値を計算し、予め計算しておいたハッシュ値と比較することができます。ハッシュ値が一致すれば、ファイルが改ざんされていないことが確認できます。
3. 暗号化と情報セキュリティ
ハッシュ関数は、暗号学的ハッシュ関数として、パスワードの保存やデジタル署名に使用されます。パスワードをそのまま保存するのではなく、そのハッシュ値を保存することで、万が一データベースが侵害された場合でも、元のパスワードが漏洩しにくくなります。
4. デジタル署名
デジタル署名では、メッセージのハッシュ値を計算し、そのハッシュ値を秘密鍵で暗号化することで署名を生成します。受信者は、送信者の公開鍵を使って署名を検証し、メッセージが改ざんされていないことを確認できます。
5. ブロックチェーン技術
ブロックチェーンでは、各ブロックのデータを一意に識別するためにハッシュ関数が使用されます。各ブロックのハッシュ値は、そのブロック内の全データに基づいて計算されるため、一部でもデータが変更されるとハッシュ値が変わります。これにより、ブロックチェーン全体のデータの整合性と一貫性が保証されます。
6. 重複排除
ハッシュ関数は、データの重複を検出するためにも使用されます。同じデータは同じハッシュ値を持つため、ハッシュ値を使って効率的にデータの重複を排除することができます。
エンジニアであれば、今後ますますハッシュへの理解が必要となるため、知識を習得しておくことは重要です。
ハッシュとは何か
ハッシュとは、あるデータを特定の計算手順（ハッシュ関数）に基づいて計算し、その結果得られる値（ハッシュ値）を求めることです。ハッシュ値はデータの格納に使用されたり、ファイルが改ざんされていないか確認したり、いろんな用途で使用されます。ハッシュ値は元のデータよりも小さなサイズで表現されることが多く、データの数に関係なく、探索、挿入、削除を効率的に行うことができます。
用語
- 入力されたデータをキーといいます。
- キーの値をハッシュ値へ変換する関数は、ハッシュ関数といいます。
- キーの値を関数へ与えたときに計算されて返される関数の値をハッシュ値をいいます。
- データを格納する配列は、ハッシュテーブルといいます。
- ハッシュテーブルの要素はバケットと呼ばれます。
つまり、「キー」を「ハッシュ関数」で計算し、変換された値を「ハッシュ値」といい、「ハッシュテーブル」というテーブルに、「ハッシュ値」:「キー」という形でバケットに格納するというのが、ハッシュにおける一連の流れです。
キー: 12345
↓
ハッシュ関数: キー % 10
↓
ハッシュ値: 5
↓
ハッシュテーブル:
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
↓
バケット5に格納
ハッシュの名前の由来
ハッシュとは、「細かく切る」とか「寄せ集め」などの意味を持つ単語です。ハッシュポテトという食べ物は、じゃがいもを細かく切り刻んで丸めて油で揚げた料理です。「細かく切り刻む」というイメージを持つと、ハッシュの概念も理解しやすくなります。
いろんなハッシュ関数
ハッシュ関数にはさまざまな種類があります。ここでは、代表的なものとして除算法、中央積算法、折り畳み法について説明します。
除算法
除算法は非常に単純なハッシュ関数です。キーを特定の数値で割り、その余りをハッシュ値とする方法です。モジュロ演算を使用します。
例えば
キー：123456
ハッシュ関数：キー % 100
計算：123456 % 100 = 56
この場合、ハッシュ値は56になります。
中央積算法
中央積算法は、キーとなる数値自身をかけ算し、その結果の中央付近の桁をハッシュ値とする方法です。ハッシュ値はキーとなる数値と同じ桁数の値を取り出す場合が多いです。
例えば
キー：1234
ハッシュ関数：キー × キー の中央4桁
計算：1234 × 1234 = 1522756
この結果の中央4桁（1522756の中央の「2275」）を選びます。この場合、ハッシュ値は2275になります。
折り畳み法
折り畳み法は、キーとなる数値を複数の部分に分け、それらをすべて足し合わせた後、必要な桁数分の数値をハッシュ値とする方法です。
例えば
キー：123456789
分割：123、456、789
計算：123 + 456 + 789 = 1368
求める桁数：ハッシュ値の末尾4桁（1368）
この場合、ハッシュ値は1368になります。
ハッシュの衝突と対策
ハッシュ関数を使うと、異なるデータが同じハッシュ値を持つことがあり、これをハッシュの衝突といいます。衝突を処理するための一般的な方法には、連鎖法（別のリストを使って同じハッシュ値を持つ要素を格納する方法）やオープンアドレス法（空いている他のバケットにデータを格納する方法）などがあります。
ハッシュ値の衝突例
ハッシュ関数：キー % 10
| キー | ハッシュ値 |
|---|---|
| 15 | 5 |
| 25 | 5 |
| 35 | 5 |
キーが15、25、35のデータは、いずれもハッシュ関数を通すと同じハッシュ値5になります。このように、異なるキーが同じハッシュ値を持つことが衝突です。
衝突対策
連鎖法（チェイン法）
連鎖法では、同じハッシュ値を持つデータをリストや他のデータ構造に格納します。例えば、以下のようにリストを使用します。
| ハッシュ値 | データ |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | [15, 25, 35] |
| 6 |
オープンアドレス法
オープンアドレス法では、衝突が発生した場合に空いている他のバケットにデータを格納します。例えば、次のように隣接するバケットに格納します（線形探査の場合）。
| ハッシュ値 | データ |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 15 |
| 6 | 25 |
| 7 | 35 |
| 8 |
オープンアドレス法の再ハッシュ
オープンアドレス法の一環として、別のバケットを探すための操作を「再ハッシュ」といいます。再ハッシュにはさまざまな方法があります。
線形探査
線形探査では、衝突が発生した場合、次のバケットを順に探します。例えば、キーがハッシュ値5のバケットに格納される場合、次のバケットを順にチェックします。
例えば
キー：15, 25, 35
ハッシュ関数：キー % 10
- 15 → 15 % 10 = 5 (ハッシュ値5のバケットが空いているので格納)
- 25 → 25 % 10 = 5 (ハッシュ値5のバケットが埋まっているので次のバケットをチェック)
- 25 → ハッシュ値6のバケットに格納
- 35 → 35 % 10 = 5 (ハッシュ値5のバケットが埋まっているので次のバケットをチェック)
- 35 → ハッシュ値6のバケットが埋まっているので次のバケットをチェック)
- 35 → ハッシュ値7のバケットに格納
| ハッシュ値 | データ |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 15 |
| 6 | 25 |
| 7 | 35 |
| 8 | |
| 9 |
平方探査
平方探査では、衝突が発生した場合、次のバケットを探すために平方のインクリメントを使用します。「インクリメント」とは、数値を一定の量だけ増やす操作のことを指します。平方のインクリメントとは1の2乗、2の2乗...と数値を一定の量だけ増やし、かつその数値を２乗することを指します。
例えば
キー：15, 25, 35
ハッシュ関数：キー % 10
- 15 → 15 % 10 = 5 (ハッシュ値5のバケットが空いているので格納)
- 25 → 25 % 10 = 5 (ハッシュ値5のバケットが埋まっているので次の平方バケットをチェック)
- 25 → ハッシュ値(5 + 1**2) = 6のバケットに格納
- 35 → 35 % 10 = 5 (ハッシュ値5のバケットが埋まっているので次の平方バケットをチェック)
- 35 → ハッシュ値(5 + 1**2) = 6のバケットが埋まっているので次の平方バケットをチェック)
- 35 → ハッシュ値(5 + 2**2) = 9のバケットに格納
- 1つ目の衝突後は元の位置から1の2乗 = 1バケット目をチェック。
- 2つ目の衝突後は元の位置から2の2乗 = 4バケット目をチェック。
- 3つ目の衝突後は元の位置から3の2乗 = 9バケット目をチェック。
このように、平方探査では次の格納先のステップが1, 4, 9,...と増加していくため、連続した位置にデータが集中しにくくなり、衝突の影響を緩和できます。
| ハッシュ値 | データ |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 15 |
| 6 | 25 |
| 7 | |
| 8 | |
| 9 | 35 |
ダブルハッシング
ダブルハッシングでは、2つのハッシュ関数を使用し、衝突が発生した場合に別のハッシュ関数を使って次のバケットを探します。
例えば
キー：15, 25, 35
ハッシュ関数1：キー % 10
ハッシュ関数2：7 - (キー % 7)
- 15 → 15 % 10 = 5 (ハッシュ値5のバケットが空いているので格納)
- 25 → 25 % 10 = 5 (ハッシュ値5のバケットが埋まっているのでハッシュ関数2を使用)
- 25 → 7 - (25 % 7) = 7 - 4 = 3 → ハッシュ値(5 + 3) = 8のバケットに格納
- 35 → 35 % 10 = 5 (ハッシュ値5のバケットが埋まっているのでハッシュ関数2を使用)
- 35 → 7 - (35 % 7) = 7 - 0 = 7 → ハッシュ値(5 + 7) = 2のバケットに格納
| ハッシュ値 | データ |
|---|---|
| 1 | |
| 2 | 35 |
| 3 | |
| 4 | |
| 5 | 15 |
| 6 | |
| 7 | |
| 8 | 25 |
| 9 |
文字列からハッシュ値を計算する方法
文字列の各文字のASCII値の合計を取る方法
各文字のASCIIコードの値を合計し、それをテーブルのサイズで割った余りを使用してハッシュ値を計算します。
ASCII（American Standard Code for Information Interchange）値とは、文字や記号をコンピュータで表現するために使用される標準的なコード体系です。ASCIIコードは、7ビットの整数値（0から127）で文字を表現し、各文字に一意の数値を割り当てています。これにより、文字データを数値データとして扱うことができます。
主なASCIIコードの例
数字
'0' = 48
'1' = 49
'2' = 50
...
'9' = 57
アルファベット（大文字）
'A' = 65
'B' = 66
'C' = 67
...
'Z' = 90
アルファベット（小文字）
'a' = 97
'b' = 98
'c' = 99
...
'z' = 122
記号
' ' (スペース) = 32
'!' = 33
'"' = 34
...
'~' = 126
具体例
キー： "apple"
- 各文字のASCII値を求めます
'a' = 97
'p' = 112
'p' = 112
'l' = 108
'e' = 101 - これらの合計を計算します
97 + 112 + 112 + 108 + 101 = 530 - 合計をテーブルサイズ(10とする)で割った余りを計算します
530 % 10 = 0
したがって、"apple" のハッシュ値は 0 です。
ダイジェスト関数を利用する方法
Pythonの標準ライブラリで提供されているハッシュ関数を使用する方法です。例えば、hash() 関数や hashlib モジュールを使用する方法があります。
hashlibを使ったハッシュ関数の例
import hashlib
def hash_function(key):
# SHA-256を使用してハッシュ値を計算
hash_object = hashlib.sha256(key.encode())
# ハッシュ値を16進数の文字列として取得
hash_hex = hash_object.hexdigest()
return hash_hex
key = "apple"
hash_value = hash_function(key)
print(f"Key: {key}, Hash Value: {hash_value}")
# 実際の出力
Key: apple, Hash Value: 3a7bd3e2360a3d50c41f76d713c07ad87409b2b3b1e3f8d5bb9f8e3fdb2b705f
hashlib.sha256()で、SHA-256ハッシュ関数を作成します。
key.encode()で、文字列をバイト形式に変換します。hashlibはバイトデータを必要とします。
hash_object.hexdigest()で、ハッシュ値を16進数の文字列として取得します。
まとめ
ハッシュとは、データを特定の計算手順（ハッシュ関数）に基づいて計算し、その結果得られる値（ハッシュ値）を求めること。
Q. ハッシュ値を求める計算手順は何がある？
除算法：キーをある数で割った余りを使う方法
中央積算法：キー同士を掛け算した値の真ん中の部分を使う方法
折り畳み法：キーを分解して足し算した値を使う方法
Q. ハッシュ値が被ったら（衝突したら）どうする？
連鎖法：同じハッシュ値同士でリストに格納する
オープンアドレス法：空いているところに格納する
Q. オープンアドレス法の具体的な手法は？
線形探査：すぐ次の空きを探して格納する方法
平方探査：格納先が隣り合わないように遠くに配置しようとする方法
ダブルハッシング：衝突が発生したときに別のハッシュ関数を使う方法
文字列もハッシュ値の計算ができる。例えばPythonのhashlibモジュールを使ってSHA-256などのハッシュ関数を利用する方法がある。
これで、ざっくりとハッシュのことを知ることができました。