git コミット ID の衝突確率 - 2011-12-28 - はてなるせだいありgit はコミットを SHA1 で管理していることは、こんな場末の日記を好きこのんでご覧になられている皆さんならよくご存じかと思いますが、最近メイドガチャピン先生の「革命の日々！ git のsha1は何桁あれば安全か」など、Linux において Git デフォルトの 7 桁表示のコミット ID が被りまくっていると話題のようですので、これについて考えてみましょう。 さて、ハッシュ関数については昔まとめたことがありますが、ようするに Radium Software Development さんの記事が素晴らしいという話です。それによると、Bob Jenkins 曰く「2^n 個のキーに関して，衝突の可能性を 1/(2^m) 程度に抑えたいならば， 2(n+m) ビットのハッシュ値を用いる必要があります」だそうな。 Linuxのコミット数は 220k=~262144=2^18 なので、衝突確率
