teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

1

ハッシュについて

2021/09/11 19:11

投稿

nobonobo
nobonobo

スコア3367

answer CHANGED
@@ -80,4 +80,28 @@
80
80
  }
81
81
  }
82
82
 
83
- ```
83
+ ```
84
+
85
+ # ハッシュについて
86
+
87
+ Gitのコミットハッシュはご存じですか?
88
+ ある「ハッシュ値」はリポジトリに「過去のすべての積み上げられた変更の履歴」の「一意性」を天文学的な確率で保証するものです。
89
+
90
+ つまりコミットハッシュは大まかに以下の手順で作られます
91
+ - ファイル名でソートされた初期投入コードのテキストを
92
+ - その後は変更差分を
93
+ - 順番を守って
94
+ - ハッシュ計算を積み上げたもの
95
+
96
+ つまりある「ハッシュ値」は最終的なソースコードセットの状態が「一意」であることが期待できるということです。
97
+
98
+ そして、ある別のソースと履歴をハッシュ値に計算した結果が同じ「ハッシュ値」になることを「コンフリクト」といいます。
99
+
100
+ ハッシュアルゴリズムはこの「コンフリクト」を意図的に起こすのを困難にすることを目標に改良されてきました。実際に古いハッシュアルゴリズムではコンフリクトする複数のデータ列が発見されたりしています。最新のハッシュアルゴリズムにもコンフリクトを起こすデータ列がきっとあるだろうと探すような研究を行っているところもあります。
101
+
102
+ 要するに、「一定のオーダーで一定の長さのデータ列Aに対し計算されたハッシュ値」は
103
+ 別のところで「一定のオーダーで一定の長さのデータ列Bに対し計算されたハッシュ値」と一致するとき、「データ列Aとデータ列Bは同じであることがほぼほぼ保証される」ということです。
104
+
105
+ つまり離れた場所でデータ列そのものを送らなくてもハッシュだけ送って元データが同じかどうか比較できるのが「ハッシュ」です。
106
+
107
+ 元のコードではハッシュ積算用のインスタンス一つにあるデータ列を投入しこの時点のハッシュ値Aと、さらにそのデータ列のオーダーを入れ替えたものを投入した結果のハッシュ値Bを比較しようとしています。これはGitハッシュでいうと変更を積み上げた前と後のソースコードセットを比較しているようなものなのでハッシュが異なるのは自然というか当たり前なのです。